Coresets

Imagine you need to cluster a billion GPS traces, fit a regression to a terabyte of sensor readings, or train a model on every photo ever taken. Running the algorithm on the full data would take forever — but throwing away most of it would destroy the answer.

Coresets offer a third path. A coreset is a small weighted subset of the original data such that any algorithm you run on it produces an answer that is nearly as good as running on the full dataset. Each surviving point gets a weight that compensates for the points that were removed, so the geometry of the data is preserved in miniature.

The key guarantee is formal: for a given error tolerance $\varepsilon$ and a class of queries (say, k-means cost), a coreset $C$ satisfies

$$\text{cost}(C, Q) \approx \text{cost}(P, Q) \quad \text{for every query } Q$$

where $P$ is the original point set. The coreset can be orders of magnitude smaller than $P$, yet any optimizer that works on $C$ finds a solution that is nearly optimal for $P$ too.

This idea underpins fast streaming algorithms, distributed machine learning, and any problem where data arrives faster than you can store it.

Below is a random 2-D point cloud. Press Build coreset to select a small weighted sample using sensitivity-based sampling. Then press Run k-means to cluster both the full dataset and the coreset — notice how the cluster centers almost coincide.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label>{{label_n}} <input id="nPts" type="range" min="50" max="300" value="120" step="10"> <span id="nVal">120</span></label>
  <label>{{label_k}} <input id="kClust" type="range" min="2" max="5" value="3"> <span id="kVal">3</span></label>
  <label>{{label_size}} <input id="cSize" type="range" min="10" max="60" value="20" step="5"> <span id="cVal">20</span></label>
</div>
<div class="btn-row">
  <button id="btnGenerate" type="button">{{btn_generate}}</button>
  <button id="btnCoreset" type="button">{{btn_coreset}}</button>
  <button id="btnKmeans" type="button">{{btn_kmeans}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="cv" width="380" height="280"></canvas>
<div id="statusBox" class="status"></div>
<div id="legend" class="legend" style="display:none">
  <span class="dot full"></span> {{legend_full}}
  <span class="dot core"></span> {{legend_core}}
  <span class="cross full-x">+</span> {{legend_center_full}}
  <span class="cross core-x">+</span> {{legend_center_core}}
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px 4px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .5rem; line-height: 1.4; }
.controls { display: flex; flex-wrap: wrap; gap: .4rem .9rem; margin-bottom: .5rem; font-size: .82rem; }
.controls label { display: flex; align-items: center; gap: .3rem; }
.controls input[type=range] { width: 80px; }
.btn-row { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
canvas { display: block; border: 1px solid #dde3ea; border-radius: 8px; width: 100%; max-width: 380px; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.4em; margin: .4rem 0; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.legend { font-size: .78rem; display: flex; flex-wrap: wrap; align-items: center; gap: .3rem .8rem; }
.dot { display: inline-block; width: 9px; height: 9px; border-radius: 50%; }
.dot.full { background: #4a90d9; }
.dot.core { background: #e86d1f; }
.cross { font-weight: 900; font-size: 1rem; line-height: 1; }
.cross.full-x { color: #1d3557; }
.cross.core-x { color: #c04000; }

// Code not found

The coreset uses far fewer points (shown in orange) yet the k-means centers it finds (orange crosses) land very close to the centers found on all the data (blue crosses). The error shown is the ratio of coreset cost to full-data cost — values near 1.0 mean the coreset is a faithful proxy.

Why do coresets work, and how small can they be?

• Sensitivity sampling: every point $p$ gets a sensitivity score $\sigma(p)$ measuring its worst-case influence on any query. Sampling proportional to $\sigma$ and re-weighting by $1/\sigma$ gives an unbiased sketch with bounded error.
• Size bound: for k-means in $d$ dimensions with error $\varepsilon$, coresets of size $O(k \varepsilon^{-2} d)$ exist — independent of the number of points $n$. Compress a billion rows to a few thousand and the answer barely changes.
• Streaming construction: coresets can be built in a single pass over the data and merged in a tree (the "merge-and-reduce" framework of Har-Peled & Mazur, 2004 and Feldman & Langberg, 2011), making them ideal for data streams and distributed systems.
• Hardness perspective: without coresets, exact k-means is NP-hard even in the plane. The coreset reduction converts intractable exact optimization into tractable approximation — a genuine algorithmic win, not a trick.

The result is that problems requiring time $\Omega(n \cdot f(k))$ on the full data run in $O(|C| \cdot f(k))$ after coreset construction, where $|C| \ll n$. This is the mathematical engine behind scalable dimensionality reduction and large-scale k-means clustering.

Anywhere the data is huge and the algorithm is expensive, coresets have found a home:

• Streaming data: sensor networks, financial ticks, and click logs arrive faster than they can be stored. A coreset built in a single pass over the stream preserves enough structure for accurate downstream analysis.
• Federated and distributed ML: each device or shard builds its own local coreset and ships only that to the server — dramatically reducing communication while keeping model quality close to centralized training.
• Robotics and LiDAR: a self-driving car processes millions of 3-D points per second. Coreset compression lets real-time mapping and obstacle detection run within tight latency budgets.
• Computational geometry: facility location, smallest enclosing ball, and regression problems all have coreset constructions that reduce input size before the heavy solver runs.
• Database query optimization: approximate aggregation queries ("what is the average order value by region?") can be answered from a coreset stored in memory rather than scanning the full table.

Master coresets and you hold the key to making almost any geometric or statistical algorithm scale — the same principle that powers k-means at Google scale and dimensionality reduction in every modern ML pipeline.

A coreset is a beautiful idea: instead of fighting the size of your data, shrink it to a principled skeleton. The weights compensate for what was removed; the geometry stays intact; and any algorithm you run on the sketch returns an answer nearly as good as on the full dataset.

The theory is tight — coreset sizes that are independent of $n$ — and the practice is real: streaming pipelines, federated learning, and real-time robotics all rely on this compression. The next time you wonder how a machine learning model trains in seconds on data that would take hours to load, a coreset (or something very much like it) is probably lurking somewhere in the pipeline.