# The K-SCAN Clustering Algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 33 references that are in the map.
- First posted on arXiv 27 Jul 2026.

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

- [Rough Sets for Explainability of Spectral Graph Clustering](https://mlsanity.com/paper/2512.12436/) (2025)

## Abstract (arXiv)

In the Big Data era, the scalability of clustering algorithms constitutes a key challenge. Traditional density-based methods (e.g., DBSCAN) offer robustness to noise and the ability to detect non-linear clusters, yet their quadratic time complexity O(N2) drastically limits their applicability. Conversely, partitional algorithms (e.g., K-Means), with their linear complexity O(N), impose sphericity on the resulting groups and fail in the presence of outliers. This paper presents K-SCAN -- a novel hybrid algorithm that optimizes this trade-off. The method integrates preliminary vector quantization (stochastic Mini-Batch K-Means) to extract a reduced set of weighted micro-clusters, followed by a subsequent density-based structural analysis. Empirical evaluation on datasets of up to 106 samples confirms the linear computational complexity of the proposed solution. K-SCAN achieves more than a 3-fold speed-up over the hierarchical BIRCH algorithm, avoiding the costly management of tree-based structures. The method precisely identifies non-linear manifolds while maintaining structural stability (Adjusted Rand Index > 0.99), even with noise levels reaching 55% of the data volume. The main limitation of the proposed algorithm, which could not be fully eliminated in the present study, remains its susceptibility to over-smoothing and its difficulty in separating clusters with highly heterogeneous local density. In complex visual spaces, this can lead to the loss of the finest topological details.