Source-linked AI summary
Coresets and Sketches
Jeff M. Phillips
TL;DR
Large geometric data sets need summaries that support approximate computation without repeatedly processing the full input. The survey organizes coreset and sketch methods across five geometric types and computational models, establishes representative bounds, and identifies limitations such as streaming constraints and projective-clustering hardness.
Problem
Large geometric data sets require summaries that enable approximate algorithms in restricted computational settings such as streaming and distributed computation.
Method
The survey synthesizes coreset and sketch techniques across shape-fitting, density estimation, high-dimensional vectors, matrices, and clustering, including merge-reduce and matrix-sketching approaches.
Results
The survey presents approximation and runtime bounds for geometric summaries, including merge-reduce runtime O(n·g^(c−1)) and discrepancy-based bounds for several range spaces.
Takeaways & Limitations
Coresets and sketches provide a framework for approximate geometric computation in streaming and mergeable models, while some tasks require bicriteria approximations.
Takeaways & Limitations
Some projective clustering instances have no sublinear-size coreset, and related solutions cannot be approximated in polynomial time unless P = NP.
Abstract
from arXiv · showhide
Geometric data summarization has become an essential tool in both geometric approximation algorithms and where geometry intersects with big data problems. In linear or near-linear time large data sets can be compressed into a summary, and then more intricate algorithms can be run on the summaries whose results approximate those of the full data set. Coresets and sketches are the two most important classes of these summaries. We survey five types of coresets and sketches: shape-fitting, density estimation, high-dimensional vectors, high-dimensional point sets / matrices, and clustering.
INTRODUCTION
Coresets and sketches compress large data sets so algorithms can operate on summaries whose results approximate those from the full data. This survey frames their construction across geometric problems and computational models, including streaming and mergeable settings.
- Coresets and sketches: A coreset is a reduced data set used as a proxy for the full data set, with approximate results obtained by running the same algorithm.Coresets may be weighted; weak coresets guarantee errors for selected optimizing queries, whereas strong coresets guarantee errors for all queries.
- Coresets and sketches: A sketch is a compressed mapping into an update-friendly data structure that supports queries approximating those on the full data set.Linear sketches use mappings linear in each data point, enabling additions, subtractions, and modifications.
- Coresets and sketches: Summary size ideally depends on the approximation guarantee rather than the original data-set size, although logarithmic dependence is sometimes acceptable.Coreset and sketch definitions can overlap, and some summaries fit both classes.
- Survey scope: The survey covers shape-fitting, density estimation, high-dimensional vectors, high-dimensional point sets or matrices, and clustering.Other types, including graph and Fourier-transform summaries, are outside the survey’s scope.
- Computational models and primitives: The merge-reduce framework repeatedly merges summaries and reduces them to size g, producing a summary from n data points in logarithmic rounds.If summaries are mergeable, the reduce step is unnecessary.
- Computational models and primitives: O(n·g^(c−1)) is the full runtime when merge or reduce processing costs m^c on sets of at most 2g points.The runtime is dominated by the first round; streaming use incurs an additional log(n/g) space factor for active summaries.
49.1 SHAPE FITTING
Shape-fitting coresets summarize point sets for fitting geometric shapes, including enclosing balls and directional or functional width. The section gives size and construction bounds, while noting streaming and dimensionality constraints.
- Overview: The two central shape-fitting problems are minimum enclosing balls and ε-kernel coresets for directional width.Directional-width kernels approximate the convex hull and can support other problems.
- Minimum enclosing ball: A minimum enclosing ball coreset has size ⌈2/ε⌉ and runs in O(nd/ε + 1/ε^5) time.Its expanded radius (1 + ε)r, with unchanged center, contains the full point set.
- Minimum enclosing ball: MEB coreset algorithms require Ω(1/ε) passes and therefore do not work in the streaming model.A high-probability runtime improvement is O((d/ε + n/ε^2) log(n/ε)).
- Directional width: An ε-kernel for directional width has size O(1/ε^((d−1)/2)) and construction time O(n + 1/ε^(d−3/2)).The construction first applies an affine transform to make the points fat, then selects points in extremal directions.
- Directional width: In streaming, directional-width kernels use O((1/ε^((d−1)/2))·log(1/ε)) space and amortized O(1) update time.In R2, the space becomes O(1/√ε) with O(1) update time.
- Functional width: An ε-kernel for functional width has size O(1/ε^(d/2)) and construction time O(n + 1/ε^(d−1/2)).Related faithful measures include diameter, width, minimum enclosing cylinder, and minimum enclosing box.
49.2 DENSITY ESTIMATION
Density-estimation coresets represent point-set densities over geometric ranges or function families. Random sampling gives VC-dimension-dependent bounds, while discrepancy methods can tighten bounds for selected range spaces and kernels.
- Foundations: Density-estimation coresets are subsets representing a similar density under restricted ways of measuring subsets, such as range spaces.Range spaces consist of a ground set and a family of geometrically defined ranges.
- Foundations: VC-dimension is the largest subset whose every subset can be realized by intersecting it with a range.This dimension controls many sampling bounds.
- Random sampling: A random sample of O((1/ε^2)(ν + log(1/δ))) points is an ε-approximation for VC-dimension ν with probability at least 1 − δ.The corresponding ε-net bound is O((ν/ε) log(1/(εδ))).
- Random sampling: These sampling bounds support learning-theoretic guarantees and have no dependence on the original data-set size n.They can therefore extend from finite point sets to probability distributions over R^d.
- Random sampling: A relative (ρ, ε)-approximation requires O((1/(ρε^2))(ν log(1/ρ) + log(1/δ))) samples with probability at least 1 − δ.This strengthens additive ε approximation to a relative guarantee.
- Discrepancy-based results: Discrepancy methods build colorings that can be inserted into merge-reduce frameworks, with modifications removing extra logarithmic approximation factors.For halfspaces, balls, and axis-aligned rectangles, the resulting bounds depend on the range-space dimension and VC-dimension.
- Discrepancy-based results: For halfspaces in R3 and balls in R2, ε-nets of size O(1/ε) are possible, while axis-aligned rectangles and fat objects admit O((1/ε) log log(1/ε)).The cited results are tight, and similar improvements do not extend to higher dimensions.
- Function families and kernels: For Gaussian and related kernels in R2, discrepancy-based ε-approximations can use |Q| = O((1/ε) log(1/ε)).Function-family formulations also support minimum-cost objectives and applications such as k-means clustering.
49.3 HIGH DIMENSIONAL VECTORS
High-dimensional vector summaries represent frequency counts or approximate vectors while supporting norm-based queries. The survey covers sampling, deterministic counters, linear sketches, frequency moments, and k-sparse tail approximations.
- Overview: High-dimensional vector sketches compactly represent vectors for approximate behavior under various norms, while coresets can represent relative frequencies.Positive integer coordinates can be viewed as counts of labeled objects.
- Frequency counts: k = O((1/ε2) log(1/δ)) sampled objects give an additive ε-(ℓ∞/ℓ1) approximation with probability at least 1 −δ.The sampled vector assigns each coordinate a scaled sample count.
- Frequency counts: Misra-Gries deterministically produces a (1/ε)-sparse weighted coreset for additive ε-(ℓ∞/ℓ1) approximation in streaming.It maintains 1/ε labeled counters and decrements all counters when no counter is available.
- Frequency counts: The count-min sketch uses O((1/ε) log(1/δ)) space for additive ε-(ℓ∞/ℓ1), while count-sketch uses O((1/ε2) log(1/δ)) for additive ε-(ℓ∞/ℓ2).Both use multiple hash functions mapping coordinates to counters.
- Frequency moments: The AMS Sketch estimates the second frequency moment within relative error ε using O((1/ε2) log(1/δ)) space and success probability at least 1 −δ.The FM Sketch similarly estimates the zero frequency moment, with an error bound involving ∥v∥1.
- k-sparse approximations: k-sparse approximations improve error bounds by depending only on the tail, with Misra-Gries and Count-Min using O(k/ε) counters for ℓ∞/ℓ1.Count sketch achieves k-sparse ε-(ℓ∞/ℓ2)-approximations with O(k2/ε2) counters.
49.4 HIGH DIMENSIONAL POINT SETS (MATRICES)
Matrix sketches replace large matrices with smaller representations for low-rank approximation and related tasks. The survey covers row sampling, random projections, and iterative SVD-like methods, including streaming and mergeable settings.
- Overview: Matrix sketching replaces an n×d matrix with a smaller low-rank approximation, viewing its rows as points whose span is approximately captured by a k-dimensional subspace.This connects matrix sketching to scalability in machine learning and data mining.
- Overview: The survey standardizes matrix summaries as an ℓ×d matrix B that approximates A using fewer rows, although dimensionality reduction may instead reduce columns or both.The distinction can be represented by transposing the input matrix.
- Row subset selection: Row sampling selects O((1/ε2)k log k) rows proportional to squared norms, yielding a rank-k approximation with an additive Frobenius-error term.Sampling columns as well extends the approach to two-sided summaries.
- Row subset selection: Leverage-score sampling uses the first k left singular vectors to assign row importance and achieves a relative-error bound with O((1/ε2)k log k) rows.The leverage score of a row is the norm of its row in the left-singular-vector matrix.
- Row subset selection: O(k/ε) rows and columns can achieve strong relative-error bounds outside streaming, while O(d/ε2) reweighted rows are sufficient and necessary for another bound.Approximate leverage scores can also be computed in streaming space.
- Random projections: Random projections form B = SA, where an oblivious sketch matrix S reduces rows while preserving norms; required dimensions include O(d/ε2) for iid projections.Hashing-based approaches use O(d2/ε2) rows.
- Random projections: An oblivious projection matrix supports update-only streaming, merges, deletions, and arbitrary entry updates because it is created independently of A.For sparse matrices, applying the projection takes roughly O(nnz(A)) time.
- Iterative SVD variants: Iterative SVD-like sketches are faster than SVD and work in streaming and mergeable models, maintaining a rank-ℓ approximation while shrinking squared singular values after updates.Frequent Directions processes rows or batches of O(ℓ) rows and uses specified settings of ℓ for its bounds.
49.5 CLUSTERING
Clustering coresets summarize assignment-based costs for center sets, including point centers and higher-dimensional affine subspaces. Strong coresets approximate all candidate center sets, while weak coresets preserve the quality of an optimal or near-optimal solution.
- Assignment-based clustering: Assignment-based clustering maps each point to its closest center among k centers and evaluates the resulting weighted assignments with a cost function.The framework also allows centers to be higher-dimensional subspaces.
- Standard clustering objectives: k-means, k-median, and k-center minimize cost2, cost1, and cost∞, respectively, over center sets of size k.The k-center objective uses the maximum point-to-center distance.
- Projective clustering: Projective clustering replaces point centers with k affine subspaces of dimension j and assigns each point by its distance to the nearest subspace.The projective distance uses orthogonal projection onto each candidate subspace.
- Coreset definitions: A (k, j, ε)-coreset preserves the projective-clustering cost for all sets of k j-dimensional centers, using a subset and weights, possibly with an additive constant γ.The constant γ is often zero unless stated otherwise.
- Strong and weak coresets: Strong coresets approximate every candidate center set within a multiplicative (1 + ε) factor, whereas weak coresets approximate only the optimal or near-optimal solution.Every strong coreset is therefore weak, but the converse does not hold.
k-MEANS AND k-MEDIAN CLUSTERING CORESETS
k-means and k-median admit coreset-size bounds independent of the original data size, with strong and weak constructions connected to VC-dimension-type results and density approximation.
- Size bounds: Strong (k, ε)-coresets for k-means and k-median have size O(dk/ε2), while weak coresets have size O(k log(1/ε)/ε3).The bounds generalize to costp for p ≥ 1, but do not meaningfully cover the p = ∞ k-center case.
- Size bounds: The coreset-size bounds are independent of n and sometimes independent of d, the number and dimension of points in the original set.This separates summary size from the input data-set size in the stated regimes.
- Streaming: Weak constructions extend to streaming with O((k/ε3) log(1/ε) log4 n) space using merge-reduce.The streaming bound includes polylogarithmic dependence on n.
- Underlying technique: The constructions connect clustering coresets to VC-dimension-type results and density approximation by representing each point as a cost function over center sets.Total clustering cost is expressed as the sum of these point-associated functions.
k-CENTER CLUSTERING CORESETS
k-center is harder than k-means and k-median, but approximation algorithms and coreset constructions provide guarantees in selected dimensional and projective-clustering settings.
- k-center difficulty: The k-center problem is NP-hard to approximate within a factor below 2, while Gonzalez’s greedy algorithm achieves a 2-approximation.The greedy method repeatedly chooses the point farthest from the already selected centers.
- Point-center coresets: Low-dimensional k-center coresets use a Gonzalez-based grid with size O(k/εd) and construction time O(n + k/εd).One point is retained from each grid cell.
- Point-center coresets: High-dimensional k-center coresets use O(kO(k/ε)) sequences of parallel MEB algorithms to obtain size O(k/ε) in O(dnkO(k/ε)) time.This construction targets the high-dimensional setting described in the passage.
- Projective-clustering limits: Subspace clustering can lack sublinear coresets: for projective center clustering, the cited result rules out sublinear size when j = 1, k = 2, and d = 3, and extends to j = 2.For j ≥ 2 and k > log n, polynomial-time approximation is also ruled out unless P = NP.
- Projective-clustering coresets: Bicriteria approximations address these limits by approximating k j-dimensional subspaces with O(k log n) subspaces of the same dimension.The cited strong and weak coreset sizes are O(djk/ε2) and O(kj2 log(1/ε)/ε3), respectively.
- Projective-clustering coresets: For squared-distance projective clustering, strong coreset sizes range from O(j/ε) for k = 1 to poly(2kj, 1/ε) when j, k > 1 under bounded integer coordinates.The cited constructions also include cases j = 0 and j = 1, with streaming extensions incurring extra log n factors in space.
49.6 SOURCES AND RELATED MATERIAL
The cited related material spans surveys, books, and introductions covering geometric coresets, approximation, streaming, sketching, randomized matrix sketching, and foundational geometric topics.
- Coresets: AHPV07 is identified as a survey on coresets in geometry.
- Geometric approximation: HP11 is a book on geometric approximation covering ε-approximations, ε-nets, dimensionality reduction, and ε-kernel coresets.
- Streaming: Mut05 covers streaming, including its history, puzzles, applications, and sketching.
- Sketching: CGHJ11 provides an introduction to sketching and its variations, while Mah11 and Woo14 survey randomized algorithms for matrix sketching.
- Foundational topics: The listed geometric references also cover low-distortion embeddings, discrepancy theory, uniform distribution, ε-nets, and ε-approximations.