Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
We prove that the sum of the squared Euclidean distances from the n rows of an n × d matrix A to any compact set that is spanned by k vectors in ℝd can be approximated up to (1+ε)-factor, for an arbitrary small ε > 0, using the O(k/ε2)-rank approximation of A and a constant. This implies, for example, that the optimal k-means clustering of the rows of A is (1 + ε)-approximated by an optimal k-means clustering of their projection on the O(k/ε2) first right singular vectors (principle components) of A. A (j, k)-coreset for projective clustering is a small set of points that yields a (1 + ε)-approximation to the sum of squared distances from the n rows of A to any set of k affine subspaces, each of dimension at most j. Our embedding yields (0, k)-coresets of size (k) for handling k-means queries, (j, 1)-coresets of size (j) for PCA queries, and (j, k)-coresets of size (log n) (jk) for any j, k ≥ 1 and constant ε ∊ (0, 1/2). Previous coresets usually have a size which is linearly or even exponentially dependent of d, which makes them useless when d ∼ n. Using our coresets with the merge-and-reduce approach, we obtain embarrassingly parallel streaming algorithms for problems such as k-means, PCA and projective clustering. These algorithms use update time per point and memory that is polynomial in log n and only linear in d. For cost functions other than squared Euclidean distances we suggest a simple recursive coreset construction that produces coresets of size for k-means and a special class of bregman divergences that is less dependent on the properties of the squared Euclidean distance.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
(2003) · Journal of Machine Learning Research · doi:10.5555/944919.944937 · Cited by 32,337
(2007) · doi:10.5555/1283383.1283494 · Cited by 7,364
Singular value decomposition and least squares solutions
Golub, G. H., & Reinsch, C. (1970) · Numerische Mathematik · doi:10.1007/bf02163027 · Cited by 2,929
The World’s Technological Capacity to Store, Communicate, and Compute Information
Hilbert, M., & López, P. (2011) · Science · doi:10.1126/science.1200970 · Cited by 1,643
Cited by
Visual Place Recognition: A Survey
Lowry, S., Sünderhauf, N., Newman, P., Leonard, J. J., Cox, D., Corke, P., & Milford, M. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2015.2496823 · Cited by 1,079
“[59] to segment the environment.”
Machine learning in wireless sensor networks: Algorithms, strategies, and applications
Alsheikh, M. A., Lin, S., Niyato, D., & Tan, H.-P. (2014) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2014.2320099 · Cited by 965
Tsai, C.-W., Lai, C.-F., Chao, H.-C., & Vasilakos, A. V. (2015) · Journal of Big Data · doi:10.1186/s40537-015-0030-3 · Cited by 818
Mining big data: current status, and forecast to the future
Fan, W., & Bifet, A. (2013) · ACM SIGKDD Explorations Newsletter · doi:10.1145/2481244.2481246 · Cited by 677
Big data reduction framework for value creation in sustainable enterprises
Rehman, M. H. U., Chang, V., Batool, A., & Wah, T. Y. (2016) · International Journal of Information Management · doi:10.1016/j.ijinfomgt.2016.05.013 · Cited by 279
Metadata
- Authors
- Feldman, D., Schmidt, M., & Sohler, C.
- Venue
- Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
- Published
- 2013-01-06
- Pages
- 1434-1453
- OpenAlex
- W2949910245
- Cited by
- 151
- References
- 4
- FWCI
- 7.16
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. https://app.cochat.ai/papers/10.1137/1.9781611973105.103
- The paper
- Feldman, D., Schmidt, M., & Sohler, C. (2013). Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. https://doi.org/10.1137/1.9781611973105.103
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.