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-citationApproximation schemes for Euclidean k-medians and related problems
Arora, S., Raghavan, P., & Rao, S. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276718 · Cited by 341
Algorithms for facility location problems with outliers
Charikar, M., Khuller, S., Mount, D. M., et al. (2001) · Symposium on Discrete Algorithms · doi:10.5555/365411.365555 · Cited by 332
Approximate medians and other quantiles in one pass and with limited memory
Manku, G. S., Rajagopalan, S., & Lindsay, B. G. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276342 · Cited by 261
Sublinear time algorithms for metric space problems
Indyk, P. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301366 · Cited by 192
Flajolet, P., & Martin, G. N. (1983) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1983.46 · Cited by 155
A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem
Kolliopoulos, S. G., & Rao, S. B. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48481-7_33 · Cited by 91
Randomized Query Processing in Robot Path Planning
Kavraki, L. E., Latombe, J., Motwani, R., & Raghavan, P. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1578 · Cited by 75
Self-citationQuick k-Median, k-Center, and Facility Location for Sparse Graphs
Thorup, M. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_21 · Cited by 54
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
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.