97 citations · 438 across the 36 of their papers we have counts for
19 papers · 1 filter
Differential Privacy from Locally Adjustable Graph Algorithms: -Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova +3
Differentially private algorithms allow large-scale data analytics while preserving user privacy. Designing such algorithms for graph data is gaining importance with the growth of…
Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering
Tom Tseng, Laxman Dhulipala, Julian Shun
Hierarchical agglomerative clustering (HAC) is a popular algorithm for clustering data, but despite its importance, no dynamic algorithms for HAC with good theoretical guarantees e…
Parallel Batch-Dynamic d-Trees
Rahul Yesantharao, Yiqiu Wang, Laxman Dhulipala +1
d-trees are widely used in parallel databases to support efficient neighborhood/similarity queries. Supporting parallel updates to d-trees is therefore an important operation…
ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
Shangdi Yu, Yiqiu Wang, Yan Gu +2
This paper studies the hierarchical clustering problem, where the goal is to produce a dendrogram that represents clusters at varying scales of a data set. We propose the ParChain…
Parallel Batch-Dynamic Algorithms for -Core Decomposition and Related Graph Problems
Quanquan C. Liu, Jessica Shi, Shangdi Yu +2
Maintaining a -core decomposition quickly in a dynamic graph has important applications in network analysis. The main challenge for designing efficient exact algorithms is that…
Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
Yiqiu Wang, Shangdi Yu, Yan Gu +1
This paper presents new parallel algorithms for generating Euclidean minimum spanning trees and spatial clustering hierarchies (known as HDBSCAN). Our approach is based on gene…
A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem
Yiqiu Wang, Shangdi Yu, Yan Gu +1
We propose a theoretically-efficient and practical parallel batch-dynamic data structure for the closest pair problem. Our solution is based on a serial dynamic closest pair data s…
Parallel Batch-Dynamic -Clique Counting
Laxman Dhulipala, Quanquan C. Liu, Julian Shun +1
In this paper, we study new batch-dynamic algorithms for the -clique counting problem, which are dynamic algorithms where the updates are batches of edge insertions and deletion…
Parallel Clique Counting and Peeling Algorithms
Jessica Shi, Laxman Dhulipala, Julian Shun
We present a new parallel algorithm for -clique counting/listing that has polylogarithmic span (parallel time) and is work-efficient (matches the work of the best sequential alg…
Theoretically-Efficient and Practical Parallel DBSCAN
Yiqiu Wang, Yan Gu, Julian Shun
The DBSCAN method for spatial clustering has received significant attention due to its applicability in a variety of data analysis tasks. There are fast sequential algorithms for D…
Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun +1
In this paper we show that many sequential randomized incremental algorithms are in fact parallel. We consider algorithms for several problems including Delaunay triangulation, lin…
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
Guy E. Blelloch, Yan Gu, Yihan Sun +1
In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by…
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Laxman Dhulipala, Guy E. Blelloch, Julian Shun
There has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for…
Implicit Decomposition for Write-Efficient Connectivity Algorithms
Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman +4
The future of main memory appears to lie in the direction of new technologies that provide strong capacity-to-performance ratios, but have write operations that are much more expen…
Sorting with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons +2
Emerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models a…
Efficient Algorithms with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons +2
In several emerging technologies for computer memory (main memory), the cost of reading is significantly cheaper than the cost of writing. Such asymmetry in memory costs poses a fu…
Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm
Niklas Baumstark, Guy Blelloch, Julian Shun
Motivated by the observation that FIFO-based push-relabel algorithms are able to outperform highest label-based variants on modern, large maximum flow problem instances, we introdu…
Parallel Wavelet Tree Construction
Julian Shun
We present parallel algorithms for wavelet tree construction with polylogarithmic depth, improving upon the linear depth of the recent parallel algorithms by Fuentes-Sepulveda et a…
Greedy Sequential Maximal Independent Set and Matching are Parallel on Average
Guy Blelloch, Jeremy Fineman, Julian Shun
The greedy sequential algorithm for maximal independent set (MIS) loops over the vertices in arbitrary order adding a vertex to the resulting set if and only if no previous neighbo…