# Scalable Density-based Clustering with Random Projections

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 24 Feb 2024.

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

- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [DBSCAN++: Towards fast and scalable density clustering](https://mlsanity.com/paper/1810.13105/) (2018)
- [Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds](https://mlsanity.com/paper/1706.02803/) (2017)
- [Density Level Set Estimation on Manifolds with DBSCAN](https://mlsanity.com/paper/1703.03503/) (2017)
- [Faster DBSCAN via subsampled similarity queries](https://mlsanity.com/paper/2006.06743/) (2020)
- [Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces](https://mlsanity.com/paper/1702.08607/) (2017)
- [Parameter-free Locality Sensitive Hashing for Spherical Range Reporting](https://mlsanity.com/paper/1605.02673/) (2016)

## Abstract (arXiv)

We present sDBSCAN, a scalable density-based clustering algorithm in high dimensions with cosine distance. Utilizing the neighborhood-preserving property of random projections, sDBSCAN can quickly identify core points and their neighborhoods, the primary hurdle of density-based clustering. Theoretically, sDBSCAN outputs a clustering structure similar to DBSCAN under mild conditions with high probability. To further facilitate sDBSCAN, we present sOPTICS, a scalable OPTICS for interactive exploration of the intrinsic clustering structure. We also extend sDBSCAN and sOPTICS to L2, L1, chi2, and Jensen-Shannon distances via random kernel features. Empirically, sDBSCAN is significantly faster and provides higher accuracy than many other clustering algorithms on real-world million-point data sets. On these data sets, sDBSCAN and sOPTICS run in a few minutes, while the scikit-learn's counterparts demand several hours or cannot run due to memory constraints.