# Fast Density-Peaks Clustering: Multicore-based Parallelization Approach

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2022.

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

- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [GBSK: Skeleton Clustering via Granular-ball Computing and Multi-Sampling for Large-Scale Data](https://mlsanity.com/paper/2509.23742/) (2025)
- [Learned k-NN Distance Estimation](https://mlsanity.com/paper/2208.14210/) (2022)
- [Faithful Density-Peaks Clustering via Matrix Computations on MPI Parallelization System](https://mlsanity.com/paper/2406.12297/) (2024)
- [Distributed Clustering based on Distributional Kernel](https://mlsanity.com/paper/2409.09418/) (2024)
- [Scalable Varied-Density Clustering via Graph Propagation](https://mlsanity.com/paper/2508.02989/) (2025)
- [Towards Robust and Scalable Density-based Clustering via Graph Propagation](https://mlsanity.com/paper/2605.00390/) (2026)

## Abstract (arXiv)

Clustering multi-dimensional points is a fundamental task in many fields, and density-based clustering supports many applications as it can discover clusters of arbitrary shapes. This paper addresses the problem of Density-Peaks Clustering (DPC), a recently proposed density-based clustering framework. Although DPC already has many applications, its straightforward implementation incurs a quadratic time computation to the number of points in a given dataset, thereby does not scale to large datasets. To enable DPC on large datasets, we propose efficient algorithms for DPC. Specifically, we propose an exact algorithm, Ex-DPC, and two approximation algorithms, Approx-DPC and S-Approx-DPC. Under a reasonable assumption about a DPC parameter, our algorithms are sub-quadratic, i.e., break the quadratic barrier. Besides, Approx-DPC does not require any additional parameters and can return the same cluster centers as those of Ex-DPC, rendering an accurate clustering result. S-Approx-DPC requires an approximation parameter but can speed up its computational efficiency. We further present that their efficiencies can be accelerated by leveraging multicore processing. We conduct extensive experiments using synthetic and real datasets, and our experimental results demonstrate that our algorithms are efficient, scalable, and accurate.