EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-SA 4.0

KNN-DBSCAN: a DBSCAN in high dimensions

Youguang Chen, William Ruys, George Biros

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →