6 papers
JAG: Joint Attribute Graphs for Filtered Nearest Neighbor Search
Haike Xu, Guy Blelloch, Laxman Dhulipala +3
Despite filtered nearest neighbor search being a fundamental task in modern vector search systems, the performance of existing algorithms is highly sensitive to query selectivity a…
Massively Parallel Minimum Spanning Tree in General Metric Spaces
Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram +3
We study the minimum spanning tree (MST) problem in the massively parallel computation (MPC) model. Our focus is particularly on the *strictly sublinear* regime of MPC where the sp…
DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
Shangdi Yu, Laxman Dhulipala, Jakub ÅÄ cki +1
We consider the problem of maintaining a hierarchical agglomerative clustering (HAC) in the dynamic setting, when the input is subject to point insertions and deletions. We introdu…
Towards Scalable and Practical Batch-Dynamic Connectivity
Quinten De Man, Laxman Dhulipala, Adam Karczmarz +3
We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for t…
The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering
Shangdi Yu, Jessica Shi, Jamison Meindl +7
We introduce the ParClusterers Benchmark Suite (PCBS) -- a collection of highly scalable parallel graph clustering algorithms and benchmarking tools that streamline comparing diffe…
Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
Laxman Dhulipala, Michael Dinitz, Jakub ÅÄ cki +1
The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there a…