2 citations · 3 across the 7 of their papers we have counts for
9 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…
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…
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…
BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers
Brian Wheatman, Xiaojun Dong, Zheqi Shen +4
A fundamental building block in any graph algorithm is a graph container - a data structure used to represent the graph. Ideally, a graph container enables efficient access to the…
Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search
Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram +1
We consider the fundamental problem of decomposing a large-scale approximate nearest neighbor search (ANNS) problem into smaller sub-problems. The goal is to partition the input po…
Open Problems in (Hyper)Graph Decomposition
Deepak Ajwani, Rob H. Bisseling, Katrin Casel +26
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gai…