# Almost Linear Time Consistent Mode Estimation and Quick Shift Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 11 Mar 2025.

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

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [DBSCAN++: Towards fast and scalable density clustering](https://mlsanity.com/paper/1810.13105/) (2018)
- [MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking](https://mlsanity.com/paper/2104.00303/) (2021)
- [On the Consistency of Quick Shift](https://mlsanity.com/paper/1710.10646/) (2017)

## Abstract (arXiv)

In this paper, we propose a method for density-based clustering in high-dimensional spaces that combines Locality-Sensitive Hashing (LSH) with the Quick Shift algorithm. The Quick Shift algorithm, known for its hierarchical clustering capabilities, is extended by integrating approximate Kernel Density Estimation (KDE) using LSH to provide efficient density estimates. The proposed approach achieves almost linear time complexity while preserving the consistency of density-based clustering.