Publications
Detailed Information
DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows
Cited 0 time in
Web of Science
Cited 1 time in Scopus
- Authors
- Issue Date
- 2022-06
- Publisher
- Association for Computing Machinery
- Citation
- Proceedings of the ACM SIGMOD International Conference on Management of Data, pp.296-309
- Abstract
- © 2022 ACM.The density-based clustering is utilized for various applications such as hot spot detection or segmentation. To serve those applications in real time, it is desired to update clusters incrementally by capturing only the recent data. The previous incremental density-based clustering algorithms often represent clusters as a graph and suffer serious performance degradation. This is because a costly graph traversal is required to check whether a cluster is still connected whenever a point is removed. In order to address the problem of slow deletion, this paper proposes a novel incremental density-based clustering algorithm called DenForest. By maintaining clusters as a group of spanning trees instead of a graph, DenForest can determine efficiently and accurately whether a cluster is to be split by a point removed from the window in logarithmic time. With extensive evaluations, it is demonstrated that DenForest outperforms the state-of-the-art density-based clustering algorithms significantly and achieves the clustering quality comparable with that of DBSCAN.
- ISSN
- 0730-8078
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.