PECANN: Parallel Efficient Clustering With Graph-based Approximate Nearest Neighbor Search

Abstract

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyu2023pecann

Related papers

• A Memory-efficient Distributed Algorithm For Approximate Nearest Neighbour Search With Arbitrary Distances (2024)0.00
• Parlayann: Scalable And Deterministic Parallel Graph-based Approximate Nearest Neighbor Search Algorithms (2023)10.35
• CAGRA: Highly Parallel Graph Construction And Approximate Nearest Neighbor Search For Gpus (2023)12.17
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
• Efficient And Effective Retrieval Of Dense-sparse Hybrid Vectors Using Graph-based Approximate Nearest Neighbor Search (2024)0.00
• Probabilistic Routing For Graph-based Approximate Nearest Neighbor Search (2024)0.00
• A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35