Introduction

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 CC satisfies

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

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

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

See the Sketch in Action

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.

<!-- Coreset demo: generate a 2D point cloud, build a weighted coreset, compare k-means centers -->
<p class="hint">A <b>coreset</b> is a tiny weighted subset that stands in for a full dataset. Generate points, build a coreset (orange), then run k-means on both — the cluster centers almost coincide.</p>
<div class="controls">
  <label>Points n = <input id="nPts" type="range" min="50" max="300" value="120" step="10"> <span id="nVal">120</span></label>
  <label>Clusters k = <input id="kClust" type="range" min="2" max="5" value="3"> <span id="kVal">3</span></label>
  <label>Coreset 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">Generate points</button>
  <button id="btnCoreset" type="button">Build coreset</button>
  <button id="btnKmeans" type="button">Run k-means</button>
  <button id="btnReset" type="button" class="ghost">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> full dataset
  <span class="dot core"></span> coreset point (size ∝ weight)
  <span class="cross full-x">+</span> k-means center (full data)
  <span class="cross core-x">+</span> k-means center (coreset)
</div>

/* Layout and palette for the coreset demo */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Coreset construction via sensitivity sampling + k-means comparison
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;

// Application state: raw points, coreset, cluster centers from full data and coreset
let pts = [], coreset = [], fullCenters = [], coreCenters = [];
let phase = 'empty'; // phases: empty | points | coreset | kmeans

const nInput = document.getElementById('nPts');
const kInput = document.getElementById('kClust');
const cInput = document.getElementById('cSize');
document.getElementById('nVal').textContent = nInput.value;
document.getElementById('kVal').textContent = kInput.value;
document.getElementById('cVal').textContent = cInput.value;
nInput.addEventListener('input', () => { document.getElementById('nVal').textContent = nInput.value; });
kInput.addEventListener('input', () => { document.getElementById('kVal').textContent = kInput.value; });
cInput.addEventListener('input', () => { document.getElementById('cVal').textContent = cInput.value; });

// Utility helpers: random uniform, squared distance, Euclidean distance
function rand(min, max) { return min + Math.random() * (max - min); }
function dist2(a, b) { return (a[0]-b[0])**2 + (a[1]-b[1])**2; }
function dist(a, b) { return Math.sqrt(dist2(a, b)); }

// Generate n points sampled around k random cluster seeds
function generatePoints() {
  const n = +nInput.value;
  const k = +kInput.value;
  pts = [];
  // Place k random seeds spread across the canvas
  const seeds = [];
  for (let i = 0; i < k; i++) {
    seeds.push([rand(60, W - 60), rand(40, H - 40)]);
  }
  // Scatter points around the seeds with uniform noise
  for (let i = 0; i < n; i++) {
    const seed = seeds[i % k];
    pts.push([seed[0] + rand(-55, 55), seed[1] + rand(-45, 45)]);
  }
  coreset = []; fullCenters = []; coreCenters = [];
  phase = 'points';
  setStatus('Points generated. Now build a coreset.', 'info');
  document.getElementById('legend').style.display = 'none';
  draw();
}

// Build a coreset of size m using sensitivity-based importance sampling
function buildCoreset() {
  if (pts.length === 0) return;
  const m = +cInput.value;
  const k = +kInput.value;

  // Approximate cluster centers via k-means++ as the bicriteria approximation
  const seeds = kmeansPlusPlus(pts, k);
  const assign = pts.map(p => nearest(p, seeds));

  // Compute within-cluster squared distances to estimate sensitivities
  const clusterCosts = new Array(k).fill(0);
  pts.forEach((p, i) => { clusterCosts[assign[i]] += dist2(p, seeds[assign[i]]); });
  const totalCost = clusterCosts.reduce((a, b) => a + b, 0) || 1;

  // Sensitivity of point p = (its contribution to cluster cost) + (uniform floor 2/n)
  const sens = pts.map((p, i) => {
    const ci = assign[i];
    const d2 = dist2(p, seeds[ci]);
    return d2 / (clusterCosts[ci] || 1) + 2 / pts.length;
  });
  const sensSum = sens.reduce((a, b) => a + b, 0);

  // Sample m points proportional to sensitivity; weight = sensSum / (m * sens)
  const chosen = [];
  for (let j = 0; j < m; j++) {
    let r = Math.random() * sensSum, acc = 0, idx = 0;
    for (let i = 0; i < sens.length; i++) { acc += sens[i]; if (acc >= r) { idx = i; break; } }
    const w = sensSum / (m * sens[idx]);
    chosen.push({ pt: pts[idx], w });
  }
  coreset = chosen;
  phase = 'coreset';
  setStatus(fmt('Coreset built (%m% weighted points). Now run k-means.', { m: m }), 'info');
  document.getElementById('legend').style.display = 'none';
  draw();
}

// Run weighted k-means on both the full dataset and the coreset, then compare
function runKmeans() {
  if (pts.length === 0 || coreset.length === 0) return;
  const k = +kInput.value;

  // All points with unit weight
  fullCenters = kmeansWeighted(pts.map(p => ({ pt: p, w: 1 })), k, 60);
  // Coreset points with their importance weights
  coreCenters = kmeansWeighted(coreset, k, 60);

  // Evaluate both center sets on the full dataset to compute the approximation ratio
  const fullCost = wcost(pts.map(p => ({ pt: p, w: 1 })), fullCenters);
  const coreCostOnFull = wcost(pts.map(p => ({ pt: p, w: 1 })), coreCenters);
  const ratio = coreCostOnFull / fullCost;

  phase = 'kmeans';
  document.getElementById('legend').style.display = 'flex';
  setStatus(fmt('Cost ratio (coreset / full) = %ratio%  — closer to 1.0 is better.', { ratio: ratio.toFixed(3) }), ratio < 1.15 ? 'ok' : 'info');
  draw();
}

// Return index of the nearest center to point p
function nearest(p, centers) {
  let best = 0, bd = Infinity;
  centers.forEach((c, i) => { const d = dist2(p, c); if (d < bd) { bd = d; best = i; } });
  return best;
}

// k-means++ seeding: pick next center proportional to squared distance from existing centers
function kmeansPlusPlus(points, k) {
  const c = [points[Math.floor(Math.random() * points.length)]];
  while (c.length < k) {
    const dists = points.map(p => Math.min(...c.map(ct => dist2(p, ct))));
    const sum = dists.reduce((a, b) => a + b, 0);
    let r = Math.random() * sum, acc = 0;
    for (let i = 0; i < points.length; i++) { acc += dists[i]; if (acc >= r) { c.push(points[i]); break; } }
  }
  return c;
}

// Weighted k-means: iterate weighted centroid updates for a fixed number of iterations
function kmeansWeighted(wpts, k, iters) {
  let centers = kmeansPlusPlus(wpts.map(wp => wp.pt), k);
  for (let it = 0; it < iters; it++) {
    const sums = Array.from({ length: k }, () => [0, 0]);
    const weights = new Array(k).fill(0);
    wpts.forEach(({ pt, w }) => {
      const ci = nearest(pt, centers);
      sums[ci][0] += w * pt[0]; sums[ci][1] += w * pt[1]; weights[ci] += w;
    });
    centers = sums.map((s, i) => weights[i] > 0 ? [s[0]/weights[i], s[1]/weights[i]] : centers[i]);
  }
  return centers;
}

// Total weighted squared distance from each point to its nearest center
function wcost(wpts, centers) {
  return wpts.reduce((acc, { pt, w }) => acc + w * dist2(pt, centers[nearest(pt, centers)]), 0);
}

// Render the canvas: full data (blue), coreset (orange scaled by weight), and cluster centers (crosses)
function draw() {
  ctx.clearRect(0, 0, W, H);
  if (pts.length === 0) return;

  // Draw full-dataset points in blue (skip those already shown as coreset points)
  const coreKeys = new Set(coreset.map(c => c.pt[0].toFixed(3) + ',' + c.pt[1].toFixed(3)));
  pts.forEach(p => {
    const inCore = coreKeys.has(p[0].toFixed(3) + ',' + p[1].toFixed(3));
    ctx.beginPath();
    ctx.arc(p[0], p[1], inCore ? 0 : 3, 0, Math.PI * 2);
    ctx.fillStyle = '#4a90d9';
    ctx.globalAlpha = 0.45;
    ctx.fill();
    ctx.globalAlpha = 1;
  });

  // Draw coreset points in orange; radius proportional to square root of weight
  coreset.forEach(({ pt, w }) => {
    const r = Math.max(3, Math.min(8, 3 * Math.sqrt(w)));
    ctx.beginPath();
    ctx.arc(pt[0], pt[1], r, 0, Math.PI * 2);
    ctx.fillStyle = '#e86d1f';
    ctx.globalAlpha = 0.85;
    ctx.fill();
    ctx.globalAlpha = 1;
  });

  // Draw cross markers for cluster centers
  function drawCross(cx, cy, color) {
    ctx.strokeStyle = color; ctx.lineWidth = 2.5;
    ctx.beginPath(); ctx.moveTo(cx - 7, cy); ctx.lineTo(cx + 7, cy); ctx.stroke();
    ctx.beginPath(); ctx.moveTo(cx, cy - 7); ctx.lineTo(cx, cy + 7); ctx.stroke();
  }
  fullCenters.forEach(c => drawCross(c[0], c[1], '#1d3557'));
  coreCenters.forEach(c => drawCross(c[0], c[1], '#c04000'));
}

function setStatus(t, cls) {
  const s = document.getElementById('statusBox');
  s.textContent = t; s.className = 'status ' + cls;
}

document.getElementById('btnGenerate').addEventListener('click', generatePoints);
document.getElementById('btnCoreset').addEventListener('click', buildCoreset);
document.getElementById('btnKmeans').addEventListener('click', runKmeans);
document.getElementById('btnReset').addEventListener('click', () => {
  pts = []; coreset = []; fullCenters = []; coreCenters = [];
  phase = 'empty';
  setStatus('', '');
  document.getElementById('legend').style.display = 'none';
  draw();
});

// Auto-generate on load so the canvas is never empty
generatePoints();
Result
Console

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.

The Real Complexity

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

  • Sensitivity sampling: every point pp gets a sensitivity score σ(p)\sigma(p) measuring its worst-case influence on any query. Sampling proportional to σ\sigma and re-weighting by 1/σ1/\sigma gives an unbiased sketch with bounded error.
  • Size bound: for k-means in dd dimensions with error ε\varepsilon, coresets of size O(kε−2d)O(k \varepsilon^{-2} d) exist — independent of the number of points nn. 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 Ω(n⋅f(k))\Omega(n \cdot f(k)) on the full data run in O(∣C∣⋅f(k))O(|C| \cdot f(k)) after coreset construction, where ∣C∣≪n|C| \ll n. This is the mathematical engine behind scalable dimensionality reduction and large-scale k-means clustering.

Where It Matters

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.

Conclusion

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 nn — 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/coresets/Content licensed under CC BY-NC 4.0.