KNN-DBSCAN: a DBSCAN in high dimensions
ACM Transactions on Parallel Computing · 31.03.2025 · 12 (1) · 1-27
DOI: 10.1145/3701624 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, online erschienen am 12.02.2025. Verfasst von Youguang Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 41 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-SA 4.0).
Abstract (Originalsprache)
Clustering is a fundamental task in machine learning. One of the most successful and broadly used algorithms is DBSCAN, a density-based clustering algorithm. DBSCAN requires ϵ-nearest neighbor graphs of the input dataset, which are computed with range-search algorithms and spatial data structures like KD-trees. Despite many efforts to design scalable implementations for DBSCAN, existing work is limited to low-dimensional datasets, as constructing ϵ-nearest neighbor graphs can be expensive in high-dimensions. This article introduces a modified DBSCAN, using k -nearest neighbor ( k NN) graphs to improve efficiency. We outline conditions for k NN-DBSCAN to match DBSCAN’s results and present a parallel implementation using OpenMP and MPI for shared and distributed memory systems. Testing on datasets up to 32 dimensions, we achieve remarkable scalability. Our implementation clusters one billion 3D points in under one second on 28K cores at TACC’s Frontera system. In a larger run, we cluster 65 billion points in 20 dimensions in under 40 seconds using 114,688 cores. Our method is up to 37× faster than state-of-the-art parallel DBSCAN on a 20-dimensional dataset with 4 million points. Code is available at https://github.com/ut-padas/knndbscan .
Zitieren
APA
Chen, Y., Ruys, W., & Biros, G. (2025). KNN-DBSCAN: a DBSCAN in high dimensions. ACM Transactions on Parallel Computing, 12(1), 1-27. https://doi.org/10.1145/3701624
Vancouver
Chen Y, Ruys W, Biros G. KNN-DBSCAN: a DBSCAN in high dimensions. ACM Transactions on Parallel Computing. 2025;12(1):1-27. doi:10.1145/3701624
BibTeX
@article{Chen2025,
author = {Chen, Youguang and Ruys, William and Biros, George},
title = {KNN-DBSCAN: a DBSCAN in high dimensions},
journal = {ACM Transactions on Parallel Computing},
year = {2025},
volume = {12},
number = {1},
pages = {1--27},
doi = {10.1145/3701624}
}
EUVIMED