# Fast Density Estimation for Density-based Clustering Methods

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 56 references that are in the map.
- First posted on arXiv 23 Sep 2021.

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

- [DBSCAN++: Towards fast and scalable density clustering](https://mlsanity.com/paper/1810.13105/) (2018)
- [Faster DBSCAN via subsampled similarity queries](https://mlsanity.com/paper/2006.06743/) (2020)
- [Effective Deterministic Initialization for k-Means-Like Methods via Local Density Peaks Searching](https://mlsanity.com/paper/1611.06777/) (2016)

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

- [Learned Accelerator Framework for Angular-Distance-Based High-Dimensional DBSCAN](https://mlsanity.com/paper/2302.03136/) (2023)
- [Careful Seeding for k-Medois Clustering with Incremental k-Means++ Initialization](https://mlsanity.com/paper/2207.02404/) (2022)
- [A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA](https://mlsanity.com/paper/2603.01144/) (2026)

## Abstract (arXiv)

Density-based clustering algorithms are widely used for discovering clusters in pattern recognition and machine learning since they can deal with non-hyperspherical clusters and are robustness to handle outliers. However, the runtime of density-based algorithms are heavily dominated by finding fixed-radius near neighbors and calculating the density, which is time-consuming. Meanwhile, the traditional acceleration methods using indexing technique such as KD tree is not effective in processing high-dimensional data. In this paper, we propose a fast region query algorithm named fast principal component analysis pruning (called FPCAP) with the help of the fast principal component analysis technique in conjunction with geometric information provided by principal attributes of the data, which can process high-dimensional data and be easily applied to density-based methods to prune unnecessary distance calculations when finding neighbors and estimating densities. As an application in density-based clustering methods, FPCAP method was combined with the Density Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm. And then, an improved DBSCAN (called IDBSCAN) is obtained, which preserves the advantage of DBSCAN and meanwhile, greatly reduces the computation of redundant distances. Experiments on seven benchmark datasets demonstrate that the proposed algorithm improves the computational efficiency significantly.