Browsing by Author "Hajiaghayi, MohammadTaghi"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Location-Sensitive String Problems in MPC
    (Association for Computer Machinery (ACM), 2023-06-17) Gilbert, Jacob; Hajiaghayi, MohammadTaghi; Saleh, Hamed; Seddighin, Saeed
    A suffix tree is a trie-like data structure that stores every suffix of an input string of length 𝑛. Finding the Suffix Tree of a given string is a well-studied and classic problem. A compressed suffix tree is constructible in 𝑂(𝑛) time using the well-known algorithm of McCreight (JACM, 1976) [24]. Suffix trees alongside with hashing are two powerful tools in solving location-sensitive string problems. Many well-studied fundamental string problems such as String Matching, Longest Palindrome Substring (LPS), Longest Common Substring (LCS), and Longest Common Prefix (LCP) queries are location-sensitive and have linear time solutions via reductions to suffix tree. Inspired by suffix trees, we study location-sensitive string problems LCP, LPS, and LCS in the Massively Parallel Computation (MPC) model. Our algorithms extensively utilize a novel data structure for answering 𝑂(𝑛 1+𝜖 ) arbitrary LCP queries, called an LCPQ oracle, in 𝑂(1) rounds and with 𝑂e(𝑛 1+𝜖 ) total memory. Using our LCPQ oracle we are able to give the first 𝑂(1)-round, 𝑂e(𝑛) total memory algorithm in MPC for LPS and an𝑂(1)-round LCS solution using 𝑂e(𝑛 1+𝜖 ) total memory, beating previous state-of-the-art techniques for both problems. Furthermore, we give an 𝑂(1/𝜖)-round MPC algorithm for constructing suffix arrays and suffix trees utilizing our LCPQ oracle, and demonstrate reductions for LPS and LCS to suffix tree in 𝑂(1) rounds of MPC. Finally, we show that in the Adaptive Massively Parallel Computation (AMPC) model, we can build a fully-functional suffix tree for a given input string in 𝑂(1) rounds and with 𝑂e(𝑛) total memory for any constant 𝜖 > 0.
  • Thumbnail Image
    Item
    Massively Parallel Tree Embeddings for High Dimensional Spaces
    (Association for Computer Machinery (ACM), 2023-06-17) Ahanchi, Amirmohsen; Andoni, Alexandr; Hajiaghayi, MohammadTaghi; Knittel, Marina; Zhong, Peilin
    Efficient computation on massive high-dimensional data greatly benefits from efficient embedding techniques into simpler metrics. Perhaps the most celebrated technique is the dimension reduction à-la Johnson and Lindenstrauss [46]. Another important method embeds the data into a tree metric space, first efficiently achieved by Bartal [14]. Both of these algorithmic tools are among the most general theorems with numerous applications. In this paper, we study these two embedding methods in the Massively Parallel Computation (MPC) model. We develop a new hybrid partitioning algorithm which generalizes both random shifted grid and ball partitioning methods for generating tree embeddings. This leads to an 𝑂(1)-round randomized MPC algorithm for embedding high-dimensional data into a tree while approximating the distance between any two points within a factor of 𝑂e(log1.5 𝑛) (and thus distortion 𝑂e(log1.5 𝑛)) in expectation as long as the aspect ratio is 𝑂(poly(𝑛)). This Euclidean result beats the lower bound of Ω(log𝑛) MPC rounds for tree embeddings of general metric spaces and can extend to a number of problems, including densest ball, minimum spanning tree, and Earth-Mover distance. Along the way, we implement and use Ailon and Chazelle’s Fast Johnson Lindenstrauss Transform [2] with sublinear memory and 𝑂(1) MPC rounds, which is of its own interest.