97 citations · 438 across the 36 of their papers we have counts for
40 papers
Parallel Algorithms for Hierarchical Nucleus Decomposition
Jessica Shi, Laxman Dhulipala, Julian Shun
Nucleus decompositions have been shown to be a useful tool for finding dense subgraphs. The coreness value of a clique represents its density based on the number of other cliques i…
Faster Parallel Exact Density Peaks Clustering
Yihao Huang, Shangdi Yu, Julian Shun
Clustering multidimensional points is a fundamental data mining task, with applications in many fields, such as astronomy, neuroscience, bioinformatics, and computer vision. The go…
Parallel Filtered Graphs for Hierarchical Clustering
Shangdi Yu, Julian Shun
Given all pairwise weights (distances) among a set of objects, filtered graphs provide a sparse representation by only keeping an important subset of weights. Such graphs can be pa…
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…
ParGeo: A Library for Parallel Computational Geometry
Yiqiu Wang, Rahul Yesantharao, Shangdi Yu +3
This paper presents ParGeo, a multicore library for computational geometry. ParGeo contains modules for fundamental tasks including d-tree based spatial search, spatial graph ge…
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…
Theoretically and Practically Efficient Parallel Nucleus Decomposition
Jessica Shi, Laxman Dhulipala, Julian Shun
This paper studies the nucleus decomposition problem, which has been shown to be useful in finding dense substructures in graphs. We present a novel parallel algorithm that is effi…
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…
Parallel In-Place Algorithms: Theory and Practice
Yan Gu, Omar Obeya, Julian Shun
Many parallel algorithms use at least linear auxiliary space in the size of the input to enable computations to be done independently without conflicts. Unfortunately, this extra s…
Compilation Techniques for Graph Algorithms on GPUs
Ajay Brahmakshatriya, Yunming Zhang, Changwan Hong +3
The performance of graph programs depends highly on the algorithm, the size and structure of the input graphs, as well as the features of the underlying hardware. No single set of…
Parallel Index-Based Structural Graph Clustering and Its Approximation
Tom Tseng, Laxman Dhulipala, Julian Shun
SCAN (Structural Clustering Algorithm for Networks) is a well-studied, widely used graph clustering algorithm. For large graphs, however, sequential SCAN variants are prohibitively…
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…
Exploring the Design Space of Static and Incremental Graph Connectivity Algorithms on GPUs
Changwan Hong, Laxman Dhulipala, Julian Shun
Connected components and spanning forest are fundamental graph algorithms due to their use in many important applications, such as graph clustering and image segmentation. GPUs are…
ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms
Laxman Dhulipala, Changwan Hong, Julian Shun
Connected components is a fundamental kernel in graph applications. The fastest existing parallel multicore algorithms for connectivity are based on some form of edge sampling and/…
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…
Optimizing Ordered Graph Algorithms with GraphIt
Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen +4
Many graph problems can be solved using ordered parallel graph algorithms that achieve significant speedup over their unordered counterparts by reducing redundant work. This paper…
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
Laxman Dhulipala, Charlie McGuffey, Hongbo Kang +4
Non-volatile main memory (NVRAM) technologies provide an attractive set of features for large-scale graph analytics, including byte-addressability, low idle power, and improved mem…
Parallel Algorithms for Butterfly Computations
Jessica Shi, Julian Shun
Butterflies are the smallest non-trivial subgraph in bipartite graphs, and therefore having efficient computations for analyzing them is crucial to improving the quality of certain…
Kaskade: Graph Views for Efficient Graph Analytics
Joana M. F. da Trindade, Konstantinos Karanasos, Carlo Curino +2
Graphs are an increasingly popular way to model real-world entities and relationships between them, ranging from social networks to data lineage graphs and biological datasets. Que…