Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search
summary
PECANN implements parallel Density Peaks Clustering for high-dimensional data using graph-based ANN indices and a doubling search that doubles k until a higher-density neighbor is found or switches to brute force at ~300 remaining points. It builds ParlayANN indices (tested with ParlayANN Vamana), computes k-nearest neighbors (k≈16), uses concurrent union‑find, and reports ARI nearly matching exact DPC on image/text embeddings up to 1.28M points and 1,024 dims, scales empirically as n^1.2, and outperforms FASTDP/DBSCAN while matching k‑means in many cases.
AI-written summary · about
chapters (14)
- 0:00PECANN and clustering goals
- 2:37Limitations of DPC algorithms
- 6:33Density Peaks Clustering problem
- 9:01PECANN framework steps
- 12:38Finding dependent points
- 15:14Computing clusters with union-find
- 16:41Experimental setup
- 21:50Graph-based indices performance
- 24:00Scalability with CPU cores
- 25:08Scalability with data size
- 26:14Running time analysis
- 27:16Comparison with other algorithms
- 29:27Hierarchical clustering advantages
- 31:14Conclusion
related talks
49mSpectral Approaches to Nearest Neighbor Search
43mSpectral Approaches to Nearest Neighbor Search
35mClustering: A Guide for the Perplexed
37mPower to the Points: Local Certificates for Clusterings
18mScalable Billion-point Approximate Nearest Neighbor Search Using SmartSSDs
01h 01mNearest Neighbor Methods II
01h 07mThe Pinecone Vector Database System
24mNetworkX - your Unexpected Assistant for Clustering Analysis