The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Clustering data streams
Abstract
We study clustering under the data stream model of computation where: given a sequence of points, the objective is to maintain a consistently good clustering of the sequence observed so far, using a small amount of memory and time. The data stream model is relevant to new classes of applications involving massive data sets, such as Web click stream analysis and multimedia data analysis. We give constant-factor approximation algorithms for the k-median problem in the data stream model of computation in a single pass. We also show negative results implying that our algorithms cannot be improved in a certain sense.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
BIRCH: an efficient data clustering method for very large databases
Zhang, T., Ramakrishnan, R., & Livny, M. (1996) · Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96 · doi:10.1145/233269.233324 · Cited by 3,935
(2011) · SpringerReference · doi:10.1007/springerreference_57547 · Cited by 3,190
CURE: an efficient clustering algorithm for large databases
Guha, S., Rastogi, R., & Shim, K. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276312 · Cited by 1,907
Self-citationClustering to minimize the maximum intercluster distance
Gonzalez, T. F. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90224-5 · Cited by 1,717
Clustering by means of medoids
Kaufman, L., & Rousseeuw, P. J. (1987) · Lirias · Cited by 1,311
Scaling clustering algorithms to large databases
Bradley, P., Fayyad, U. M., & Reina, C. (1998) · Cited by 716
Optimal algorithms for approximate clustering
Feder, T., & Greene, D. (1988) · doi:10.1145/62212.62255 · Cited by 437
Henzinger, M., Raghavan, P., & Rajagopalan, S. (1999) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/050/05 · Cited by 418
Selection and sorting with limited storage
Munro, J. I., & Paterson, M. S. (1980) · Theoretical Computer Science · doi:10.1016/0304-3975(80)90061-4 · Cited by 414
Incremental clustering and dynamic information retrieval
Charikar, M., Chekuri, C., Feder, T., & Motwani, R. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258657 · Cited by 354
Self-citation
Cited by
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
Models and issues in data stream systems
Babcock, B., Babu, S., Datar, M., Motwani, R., & Widom, J. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543615 · Cited by 2,495
Self-citationSimilarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
A Comprehensive Survey of Clustering Algorithms
Xu, D., & Tian, Y. (2015) · Annals of Data Science · doi:10.1007/s40745-015-0040-1 · Cited by 1,939
A Framework for Clustering Evolving Data Streams
Aggarwal, C. C., Yu, P. S., Han, J., & Wang, J. (2003) · Proceedings 2003 VLDB Conference · doi:10.1016/b978-012722442-8/50016-1 · Cited by 1,808
A symbolic representation of time series, with implications for streaming algorithms
Lin, J., Keogh, E., Lonardi, S., & Chiu, B. (2003) · Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery · doi:10.1145/882082.882086 · Cited by 1,799
Schaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,639
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
Mining concept-drifting data streams using ensemble classifiers
Wang, H., Fan, W., Yu, P. S., & Han, J. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956778 · Cited by 1,256
Density-Based Clustering over an Evolving Data Stream with Noise
Cao, F., Estert, M., Qian, W., & Zhou, A. (2006) · Proceedings of the 2006 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972764.29 · Cited by 1,016
Gaber, M. M., Zaslavsky, A., & Krishnaswamy, S. (2005) · ACM SIGMOD Record · doi:10.1145/1083784.1083789 · Cited by 886
Clustering data streams: theory and practice
Guha, S., Meyerson, A., Mishra, N., Motwani, R., & O'Callaghan, L. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1198387 · Cited by 882
Self-citationMaintaining Stream Statistics over Sliding Windows
Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539701398363 · Cited by 835
Self-citationAdaptive random forests for evolving data stream classification
Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017) · Machine Learning · doi:10.1007/s10994-017-5642-8 · Cited by 805
Online learning: A comprehensive survey
Hoi, S. C. H., Sahoo, D., Lu, J., & Zhao, P. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.04.112 · Cited by 746
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000002 · Cited by 718
Chakrabarti, D., Kumar, R., & Tomkins, A. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150467 · Cited by 661
Zhu, Y., & Shasha, D. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50039-1 · Cited by 656
An information statistics approach to data stream and communication complexity
Bar-Yossef, Z., Jayram, T. S., Kumar, R., & Sivakumar, D. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2003.11.006 · Cited by 606
Streaming-data algorithms for high-quality clustering
O'Callaghan, L., Mishra, N., Meyerson, A., Guha, S., & Motwani, R. (2003) · Proceedings 18th International Conference on Data Engineering · doi:10.1109/icde.2002.994785 · Cited by 577
Self-citationDensity-based clustering for real-time stream data
Chen, Y., & Tu, L. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281210 · Cited by 572
A Framework for Projected Clustering of High Dimensional Data Streams
Aggarwal, C. C., Han, J., Wang, J., & Yu, P. S. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50075-9 · Cited by 519
Data stream clustering: A survey
Silva, J. A., Faria, E. R., Barros, R. C., Hruschka, E. R., Carvalho, A. C. P. L. F. D., & Gama, J. (2013) · ACM Computing Surveys · doi:10.1145/2522968.2522981 · Cited by 508
Hierarchical Document Clustering Using Frequent Itemsets
Fung, B. C. M., Wang, K., & Ester, M. (2003) · Proceedings of the 2003 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972733.6 · Cited by 471
Clustering of time-series subsequences is meaningless: implications for previous and future research
Keogh, E., & Lin, J. (2005) · Knowledge and Information Systems · doi:10.1007/s10115-004-0172-7 · Cited by 464
A survey on data stream clustering and classification
Nguyen, H.-L., Woon, Y.-K., & Ng, W.-K. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-014-0808-1 · Cited by 321
Processing complex aggregate queries over data streams
Dobra, A., Garofalakis, M., Gehrke, J., & Rastogi, R. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564699 · Cited by 319
StreamKM++: A clustering algorithm for data streams
Ackermann, M. R., Märtens, M., Raupach, C., Swierkot, K., Lammersen, C., & Sohler, C. (2012) · ACM Journal of Experimental Algorithmics · doi:10.1145/2133803.2184450 · Cited by 294
On computing correlated aggregates over continual data streams
Gehrke, J., Korn, F., & Srivastava, D. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375665 · Cited by 278
Maintaining stream statistics over sliding windows: (extended abstract)
Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002) · doi:10.5555/545381.545466 · Cited by 253
Self-citation
Metadata
- Authors
- Guha, S., Mishra, N., Motwani, R., & O'Callaghan, L.
- Venue
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-07
- Pages
- 359-366
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2100369465
- Cited by
- 623
- References
- 18
- FWCI
- 41.86
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.