Publications (17)
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…
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…
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…
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…
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…
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…
AuthentiGPT: Detecting Machine-Generated Text via Black-Box Language Models Denoising
Zhen Guo, Shangdi Yu
Large language models (LLMs) have opened up enormous opportunities while simultaneously posing ethical dilemmas. One of the major concerns is their ability to create text that clos…
Modeling and Analysis of Tagging Networks in Stack Exchange Communities
Xiang Fu, Shangdi Yu, Austin R. Benson
Large Question-and-Answer (Q&A) platforms support diverse knowledge curation on the Web. While researchers have studied user behavior on the platforms in a variety of contexts, the…
Approximate Nearest Neighbor Search with Window Filters
Joshua Engels, Benjamin Landrum, Shangdi Yu +2
We define and investigate the problem of : approximate nearest neighbor search where each point in the dataset has a numeric label, and the go…
Analyzing the Spotify Top 200 Through a Point Process Lens
Michelangelo Harris, Brian Liu, Cean Park +6
Every generation throws a hero up the pop charts. For the current generation, one of the most relevant pop charts is the Spotify Top 200. Spotify is the world's largest music strea…
PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search
Shangdi Yu, Joshua Engels, Yihao Huang +1
This paper studies density-based clustering of point sets. These methods use dense regions of points to detect clusters of arbitrary shapes. In particular, we study variants of den…
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…
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…
Improving Small Language Models on PubMedQA via Generative Data Augmentation
Zhen Guo, Peiqi Wang, Yanwei Wang +1
Large Language Models (LLMs) have made remarkable advancements in the field of natural language processing. However, their increasing size poses challenges in terms of computationa…