Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
Open Access
- 29 May 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (3) , 1-25
Abstract
DBSCAN is a popular density-based clustering algorithm that has many different applications in practice. However, the running time of DBSCAN in high-dimensional space or general metric space (\em e.g., clustering a set of texts by using edit distance) can be as large as quadratic in the input size. Moreover, most of existing accelerating techniques for DBSCAN are only available for low-dimensional Euclidean space. In this paper, we study the DBSCAN problem under the assumption that the inliers (the core points and border points) have a low intrinsic dimension (which is a realistic assumption for many high-dimensional applications), where the outliers can locate anywhere in the space without any assumption. First, we propose a k-center clustering based algorithm that can reduce the time-consuming labeling and merging tasks of DBSCAN to be linear. Further, we propose a linear time approximate DBSCAN algorithm, where the key idea is building a novel small-size summary for the core points. Also, our algorithm can be efficiently implemented for streaming data and the required memory is independent of the input size. Finally, we conduct our experiments and compare our algorithms with several popular DBSCAN algorithms. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (62272432)
- Natural Science Foundation of Anhui Province (2208085MF163)
- National Key Research and Development Program of China (2021YFA1000900)
This publication has 50 references indexed in Scilit:
- DBSCAN-MS: Distributed Density-Based Clustering in Metric Spaces2019
- Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics2018
- MR-DBSCAN: a scalable MapReduce-based DBSCAN algorithm for heavily skewed dataFrontiers of Computer Science, 2013
- Density‐based clusteringWIREs Data Mining and Knowledge Discovery, 2011
- Dimensions, Embeddings, and Attractors2010
- A supervised machine learning algorithm for arrhythmia analysis2002
- Mean shift: a robust approach toward feature space analysisIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998
- A database for handwritten text recognition researchIEEE Transactions on Pattern Analysis and Machine Intelligence, 1994
- Comparing partitionsJournal of Classification, 1985