112 citations · 370 across the 54 of their papers we have counts for
63 papers
Fast and Theoretically-Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps
Quinten De Man, Laxman Dhulipala
Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic…
Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
Quinten De Man, Gilvir Gill, Michael A. Bender +2
Dynamic connectivity is a fundamental dynamic graph problem, and recent algorithmic breakthroughs on dynamic graph sketching have reshaped what is theoretically possible: by encodi…
Parallel Batch-Dynamic Maximal Independent Set
Guy Blelloch, Andrew Brady, Laxman Dhulipala +2
We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph…
Chamfer-Linkage for Hierarchical Agglomerative Clustering
Kishen N Gowda, Willem Fletcher, MohammadHossein Bateni +4
Hierarchical Agglomerative Clustering (HAC) is a widely-used clustering method based on repeatedly merging the closest pair of clusters, where inter-cluster distances are determine…
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…
PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing
Tobias Rubel, Richard Wen, Laxman Dhulipala +3
The fastest indexes for Approximate Nearest Neighbor Search today are also the slowest to build: graph-based methods like HNSW and Vamana achieve state-of-the-art query performance…
Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
Guy Blelloch, Andrew Brady, Laxman Dhulipala +3
A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can…
UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
Quinten De Man, Atharva Sharma, Kishen N Gowda +1
The dynamic trees problem is to maintain a tree under edge updates while supporting queries like connectivity queries or path queries. Despite the first data structure for this fun…
TD-Orch: Efficient Task-Data Orchestration for Distributed Systems with Application to Graph Processing
Yiwei Zhao, Qiushi Lin, Hongbo Kang +5
We introduce a task-data orchestration abstraction that supports a range of distributed applications. Given a batch of lambda tasks each requesting a data item, where both tasks an…
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li +3
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k…
Parallel Hierarchical Agglomerative Clustering in Low Dimensions
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in based on repeatedly merging the closest p…
Efficiently Constructing Sparse Navigable Graphs
Alex Conway, Laxman Dhulipala, Martin Farach-Colton +6
Graph-based nearest neighbor search methods have seen a surge of popularity in recent years, offering state-of-the-art performance across a wide variety of applications. Central to…
Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering
Quinten De Man, Laxman Dhulipala, Kishen N Gowda
Single-linkage clustering is a popular form of hierarchical agglomerative clustering (HAC) where the distance between two clusters is defined as the minimum distance between any pa…
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…
Results of the Big ANN: NeurIPS'23 competition
Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber +20
The 2023 Big ANN Challenge, held at NeurIPS 2023, focused on advancing the state-of-the-art in indexing data structures and search algorithms for practical variants of Approximate…
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…
Efficient Centroid-Linkage Clustering
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a -approximate clustering in roughly time. We ob…
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…
Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Laxman Dhulipala, Xiaojun Dong, Kishen N Gowda +1
Computing a Single-Linkage Dendrogram (SLD) is a key step in the classic single-linkage hierarchical clustering algorithm. Given an input edge-weighted tree , the SLD of is…
MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings
Laxman Dhulipala, Majid Hadian, Rajesh Jayaram +2
Neural embedding models have become a fundamental component of modern information retrieval (IR) pipelines. These models produce a single embedding per data-po…
It's Hard to HAC with Average Linkage!
MohammadHossein Bateni, Laxman Dhulipala, Kishen N Gowda +3
Average linkage Hierarchical Agglomerative Clustering (HAC) is an extensively studied and applied method for hierarchical clustering. Recent applications to massive datasets have d…
Fine-Grained Privacy Guarantees for Coverage Problems
Laxman Dhulipala, George Z. Li
We introduce a new notion of neighboring databases for coverage problems such as Max Cover and Set Cover under differential privacy. In contrast to the standard privacy notion for…