Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-24
DOI: 10.1145/3802013 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Jian Lin und 3 weiteren Autor:innen. Die Arbeit nennt 45 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a popular unsupervised algorithm that identifies clusters as dense regions separated by sparse areas. It requires no preset number of clusters, can detect arbitrary shapes, and is robust to noise, making it widely adopted. However, exact DBSCAN suffers from efficiency issues, and existing approximate variants often trade accuracy for speed. To address this, we reformulate DBSCAN as a Minimum Connected Dominating Set (MCDS) problem and propose LDBS-KDE, a fast and accurate approximation algorithm. LDBS-KDE selects candidate points via lattice-based density-biased sampling, identifies core points using kernel density estimation, and constructs clusters by grouping cores and assigning remaining points. Extensive experiments on four real-world datasets demonstrate that LDBS -KDE achieves accuracy comparable to, and in some cases surpassing, state-of-the-art methods, while offering an improvement in efficiency by a factor of two up to two orders of magnitude.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Lin, J., Wu, S., Wu, D., & Chan, T. N. (2026). Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation. Proceedings of the ACM on Management of Data, 4(3), 1-24. https://doi.org/10.1145/3802013
Vancouver
Lin J, Wu S, Wu D, Chan TN. Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation. Proceedings of the ACM on Management of Data. 2026;4(3):1-24. doi:10.1145/3802013
BibTeX
@article{Lin2026,
author = {Lin, Jian and Wu, Siyue and Wu, Dingming and Chan, Tsz Nam},
title = {Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--24},
doi = {10.1145/3802013}
}
EUVIMED