research
∙
08/07/2023
TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
We introduce TeraHAC, a (1+ϵ)-approximate hierarchical agglomerative clu...
share
research
∙
07/25/2023
Fully Dynamic Consistent k-Center Clustering
We study the consistent k-center clustering problem. In this problem, th...
research
∙
02/08/2023
Adaptive Massively Parallel Connectivity in Optimal Space
We study the problem of finding connected components in the Adaptive Mas...
research
∙
12/29/2022
Constant Approximation for Normalized Modularity and Associations Clustering
We study the problem of graph clustering under a broad class of objectiv...
research
∙
06/23/2022
Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth
Obtaining scalable algorithms for hierarchical agglomerative clustering ...
research
∙
11/17/2021
Optimal Decremental Connectivity in Non-Sparse Graphs
We present a dynamic algorithm for maintaining the connected and 2-edge-...
research
∙
07/27/2021
Scalable Community Detection via Parallel Correlation Clustering
Graph clustering and community detection are central problems in modern ...
research
∙
06/10/2021
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
We study the widely used hierarchical agglomerative clustering (HAC) alg...
research
∙
09/24/2020
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
We study fundamental graph problems such as graph connectivity, minimum ...
research
∙
09/17/2020
Near-Optimal Decremental Approximate Multi-Source Shortest Paths
We provide new algorithms for maintaining approximate distances in a wei...
research
∙
06/11/2020
Faster DBSCAN via subsampled similarity queries
DBSCAN is a popular density-based clustering algorithm. It computes the ...
research
∙
11/05/2019
Fully Dynamic Matching: Beating 2-Approximation in Δ^ε Update Time
In fully dynamic graphs, we know how to maintain a 2-approximation of ma...
research
∙
10/11/2019
Near-Optimal Massively Parallel Graph Connectivity
Identifying the connected components of a graph, apart from being a fund...
research
∙
07/11/2019
Walking Randomly, Massively, and Efficiently
We introduce an approach that enables for efficiently generating many in...
research
∙
07/04/2019
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
We give new partially-dynamic algorithms for the all-pairs shortest path...
research
∙
05/18/2019
Massively Parallel Computation via Remote Memory Access
We introduce the Adaptive Massively Parallel Computation (AMPC) model, w...
research
∙
07/27/2018
Connected Components at Scale via Local Contractions
As a fundamental tool in hierarchical graph clustering, computing connec...
research
∙
06/28/2018