Data Stream Clustering: An In-depth Empirical Study
Open Access
- 13 June 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (2) , 1-26
Abstract
Data Stream Clustering (DSC) plays an important role in mining continuous and unlabeled data streams in real-world applications. Over the last decades, numerous DSC algorithms have been proposed with promising clustering accuracy and efficiency. Despite the significant differences among existing DSC algorithms, they are commonly built around four key design aspects: summarizing data structure, window model, outlier detection mechanism, and offline refinement strategy. However, there is a lack of empirical studies on these key design aspects in the same codebase using real-world workloads with distinct characteristics. As a result, it is difficult for researchers to improve upon the state-of-the-art. In this paper, we conduct such a study of DSC on its four key design aspects. We implemented state-of-the-art variants of all of these design choices in an open-sourced platform from scratch and evaluated them using both real-world and synthetic workloads. Our analysis identifies the fundamental issues and trade-offs of each design choice in terms of both accuracy and efficiency. We even find that combining flexible design choices led to the development of a new algorithm called Benne, which can be tuned to achieve either better accuracy or better efficiency compared to the state-of-the-art.Keywords
Funding Information
- Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 (MOE-T2EP20122-0010)
- National Research Foundation, Singapore and Infocomm Media Development Authority under its Future Communications Research & Development Programme (FCP-SUTD-RG-2022-006)
- Key R&D Program of Hubei (2020BAA020)
- National Key R&D Program of China (2020AAA0108501)
This publication has 22 references indexed in Scilit:
- The ClusTree: indexing micro-clusters for anytime stream miningKnowledge and Information Systems, 2010
- Density-based clustering of data streams at multiple resolutionsACM Transactions on Knowledge Discovery From Data, 2009
- Density-based clustering for real-time stream data2007
- Density-Based Clustering over an Evolving Data Stream with Noise2006
- Scaling mining algorithms to large databasesCommunications of the ACM, 2002
- Requirements for clustering data streamsACM SIGKDD Explorations Newsletter, 2002
- Online facility location2001
- Scalability for clustering algorithms revisitedACM SIGKDD Explorations Newsletter, 2000
- BIRCHACM SIGMOD Record, 1996
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982