# PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search

arXiv: https://arxiv.org/abs/2312.03940 · HTML: https://mlsanity.com/paper/2312.03940/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 115 references that are in the map.
- First posted on arXiv 6 Dec 2023.

## Builds on (most cited first, 30 of 30)

- [A ConvNet for the 2020s](https://mlsanity.com/paper/2201.03545/) (2022)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [MTEB: Massive Text Embedding Benchmark](https://mlsanity.com/paper/2210.07316/) (2022)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [Automatic topography of high-dimensional data sets by non-parametric Density Peak clustering](https://mlsanity.com/paper/1802.10549/) (2018)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [Theoretically-Efficient and Practical Parallel DBSCAN](https://mlsanity.com/paper/1912.06255/) (2019)
- [A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree](https://mlsanity.com/paper/2111.15478/) (2021)
- [CAPS: A Practical Partition Index for Filtered Similarity Search](https://mlsanity.com/paper/2308.15014/) (2023)
- [Graph-based time-space trade-offs for approximate near neighbors](https://mlsanity.com/paper/1712.03158/) (2017)
- [Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2203.13601/) (2022)
- [Fast Density-Peaks Clustering: Multicore-based Parallelization Approach](https://mlsanity.com/paper/2207.04649/) (2022)
- [Clustering Stream Data by Exploring the Evolution of Density Mountain](https://mlsanity.com/paper/1710.00867/) (2017)
- [Constrained Approximate Similarity Search on Proximity Graph](https://mlsanity.com/paper/2210.14958/) (2022)
- [RECOME: a New Density-Based Clustering Algorithm Using Relative KNN Kernel Density](https://mlsanity.com/paper/1611.00484/) (2016)
- [Graph Reordering for Cache-Efficient Near Neighbor Search](https://mlsanity.com/paper/2104.03221/) (2021)
- [Index-based Solutions for Efficient Density Peak Clustering](https://mlsanity.com/paper/2002.03182/) (2020)
- [Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006](https://mlsanity.com/paper/2208.09447/) (2022)
- [Graph based Nearest Neighbor Search: Promises and Failures](https://mlsanity.com/paper/1904.02077/) (2019)
- [Concurrent Disjoint Set Union](https://mlsanity.com/paper/2003.01203/) (2020)
- [Faster Parallel Exact Density Peaks Clustering](https://mlsanity.com/paper/2305.11335/) (2023)
- [KNN-DBSCAN: a DBSCAN in high dimensions](https://mlsanity.com/paper/2009.04552/) (2020)
- [ParGeo: A Library for Parallel Computational Geometry](https://mlsanity.com/paper/2207.01834/) (2022)
- [DenMune: Density peak based clustering using mutual nearest neighbors](https://mlsanity.com/paper/2309.13420/) (2023)

## Built on by (most cited first, 3 of 3)

- [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)
- [CoreSPECT: Enhancing Clustering Algorithms via an Interplay of Density and Geometry](https://mlsanity.com/paper/2507.08243/) (2025)

## Abstract (arXiv)

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 density peaks clustering, a popular type of algorithm that has been shown to work well in practice. Our goal is to cluster large high-dimensional datasets, which are prevalent in practice. Prior solutions are either sequential, and cannot scale to large data, or are specialized for low-dimensional data. This paper unifies the different variants of density peaks clustering into a single framework, PECANN, by abstracting out several key steps common to this class of algorithms. One such key step is to find nearest neighbors that satisfy a predicate function, and one of the main contributions of this paper is an efficient way to do this predicate search using graph-based approximate nearest neighbor search (ANNS). To provide ample parallelism, we propose a doubling search technique that enables points to find an approximate nearest neighbor satisfying the predicate in a small number of rounds. Our technique can be applied to many existing graph-based ANNS algorithms, which can all be plugged into PECANN. We implement five clustering algorithms with PECANN and evaluate them on synthetic and real-world datasets with up to 1.28 million points and up to 1024 dimensions on a 30-core machine with two-way hyper-threading. Compared to the state-of-the-art FASTDP algorithm for high-dimensional density peaks clustering, which is sequential, our best algorithm is 45x-734x faster while achieving competitive ARI scores. Compared to the state-of-the-art parallel DPC-based algorithm, which is optimized for low dimensions, we show that PECANN is two orders of magnitude faster. As far as we know, our work is the first to evaluate DPC variants on large high-dimensional real-world image and text embedding datasets.