Geometric Streams & Coresets

Summarizing Clouds of Moving Points

Imagine a delivery company receiving millions of vehicle locations. Keeping every point makes later clustering accurate but expensive. Keeping only a few uniformly sampled points is cheap but may erase a remote village containing few vehicles. A coreset is a small weighted summary designed so that every allowed candidate solution has nearly the same objective cost on the summary as on the full data.

The objective matters. For $k$-center, the cost is the largest distance from any point to its nearest chosen center. For $k$-median, distances are summed. For $k$-means, squared distances are summed. A point far from the main cloud can dominate $k$-center, influence $k$-median, and influence $k$-means even more strongly. One sample cannot be called “a coreset” without naming the objective, metric, candidate family, and approximation guarantee.

Consider one-dimensional points $P=\{0,0,1,9,10,10\}$. For one center at $c=5$, the $k$-median cost is $5+5+4+4+5+5=28$, while the $k$-means cost is $25+25+16+16+25+25=132$. Replacing the two zeros by one weighted point $(0,2)$ and the two tens by $(10,2)$ preserves both costs exactly for every center because duplicate points are identical. Replacing the whole set by its mean preserves neither objective for arbitrary centers.

Streaming coresets commonly use merge-reduce. Small batches become weighted summaries; summaries of equal scale are merged and compressed again. This resembles carrying in binary addition and bounds memory logarithmically in stream length. However, approximation errors can accumulate across levels, so the local error budget must be chosen from the desired global guarantee.

Coresets, Sensitivity and Geometric Objectives

Let $P$ be a weighted point multiset, $\mathcal C$ a family of candidate solutions, and $f(p,C)\ge0$ the contribution of point $p$ to candidate $C$. Define

$$ \operatorname{cost}_P(C)=\sum_{p\in P}w_p f(p,C). $$

A strong $\varepsilon$-coreset $S$ satisfies

$$ (1-\varepsilon)\operatorname{cost}_P(C)\le\operatorname{cost}_S(C)\le(1+\varepsilon)\operatorname{cost}_P(C) $$

for every $C\in\mathcal C$. A weak coreset may guarantee only that optimizing on $S$ yields a near-optimal solution for $P$. These are different quantifiers.

For clustering, $f(p,C)=d(p,C)^z$, where $d(p,C)=\min_{c\in C}d(p,c)$ and $z=1$ gives $k$-median while $z=2$ gives $k$-means. The $k$-center objective uses a maximum rather than a sum and generally requires different summaries. Facility location adds opening costs, so preserving assignment cost alone may not preserve the full objective.

The sensitivity of point $p$ is conceptually

$$ \sigma(p)=\sup_{C:\operatorname{cost}_P(C)>0}\frac{w_p f(p,C)}{\operatorname{cost}_P(C)}. $$

Sampling probabilities use computable upper bounds $s(p)\ge\sigma(p)$ rather than exact sensitivities. A sampled point gets inverse-probability weight so each fixed candidate’s estimated cost is unbiased. Uniform control over every candidate requires concentration plus a complexity argument for $\mathcal C$, such as a finite net, dimension, or pseudo-dimension bound.

Bounding boxes are composable exact summaries for coordinate extrema: the bounding box of a union is obtained from coordinate-wise minima and maxima of the parts. They preserve range queries of that form, not clustering costs. Mergeability is objective-specific.

flowchart TD
    A[Point stream P with weights] --> B[Choose objective and candidate family C]
    B --> C[Point contribution f of p and C]
    C --> D[Define cost as weighted sum]
    D --> E[Bound sensitivity of each point]
    E --> F[Sample with probability from sensitivity upper bounds]
    F --> G[Assign inverse-probability weights]
    G --> H[Concentration for one fixed candidate]
    H --> I[Uniform argument over all candidates]
    I --> J[Strong epsilon coreset]
    J --> K[Optimize weighted small instance]
    A --> L[Batch summaries]
    L --> M[Merge-reduce levels]
    M --> J
    B -. change k, metric, or exponent .-> X[Guarantee must be re-established]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C,D navy;
    class E,F,G,H purple;
    class I,J,K,M teal;
    class L teal;
    class X crimson;

From Weighted Samples to Approximation

Suppose $m$ points are sampled independently with probability $q(p)$ and a selected copy of $p$ receives weight $w_p/(m q(p))$. For fixed $C$, one draw contributes $w_p f(p,C)/(m q(p))$. Summing $m$ draws gives expectation $\operatorname{cost}_P(C)$. Sensitivity-based probabilities bound each normalized contribution relative to the total cost, allowing concentration.

Uniform approximation needs more than unbiasedness. If candidate solutions are finite, a union bound may suffice. For continuous center locations, the proof uses geometric discretization or statistical dimension. Sample size depends on total sensitivity $S=\sum_p s(p)$, error $\varepsilon$, failure probability $\delta$, and complexity of the candidate family. Exact formulas vary by objective and construction.

Merge-reduce uses composability. If $S_1$ and $S_2$ each approximate their batches for every candidate, then their weighted union approximates the union because costs add. Reducing that union introduces another error. Along a path of $L$ reductions, factors like $(1\pm\eta)^L$ accumulate, so choosing $\eta$ on the order of $\varepsilon/L$ keeps global distortion near $\varepsilon$.

This logic can fail with negative weights, incompatible metrics, or summaries constructed for different $k$. It can also fail operationally when floating-point weights overflow or when late data are merged into the wrong window. The algebra of composition assumes the metadata has the same meaning.

flowchart TD
    A[Valid sensitivity upper bounds] --> B[Set sampling probabilities]
    B --> C[Sample and inverse-probability reweight]
    C --> D[Unbiased cost for one fixed candidate]
    D --> E[Bound each normalized contribution]
    E --> F[Apply concentration]
    F --> G[Control all candidates by complexity argument]
    G --> H[Strong local coreset]
    H --> I[Merge summaries of equal scale]
    I --> J[Cost additivity preserves local approximation]
    J --> K[Reduce merged weighted set]
    K --> L[Compose errors along hierarchy]
    L --> M[Global streaming coreset]
    A -. sensitivity underestimated .-> X[Rare influential point can be missed]
    K -. negative or incompatible weights .-> Y[Composition proof fails]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C navy;
    class D,E,F,G purple;
    class H,I,J,K,L,M teal;
    class X,Y crimson;

Fleet Locations, Clustering and Sensor Maps

For an approachable delivery problem, weighted coresets can summarize stops before testing depot locations. $k$-median matches total travel distance; $k$-center matches worst service radius; $k$-means emphasizes squared displacement. Selecting the wrong objective may satisfy a theorem and still violate the business goal.

For a fleet at scale, edge devices can build local coresets, which are merged centrally if they share coordinate reference systems, time windows, weights, objective, and parameters. Location uncertainty and map-network distance complicate the Euclidean model. A coreset for latitude/longitude Euclidean distance is not automatically valid for road travel time.

For sensor maps, a bounding box summarizes extrema exactly, while clustering coresets represent spatial density or facility cost. Missing sensors, duplicate telemetry, drift, and varying measurement reliability require explicit weights and population semantics.

Adversarial cases include a rare distant group omitted by uniform sampling, injected extreme points that dominate sensitivity, and clients adapting points after public randomness is known. Per-group coverage, robust objectives, bounded contributions, seed policies, and exact audit samples may be needed beyond the mathematical coreset guarantee.

Construct a Geometry-Aware Summary Plan

Begin with the decision, not the compression. Define points, weights, metric, time window, candidate centers, constraints, objective exponent, and error quantifiers. Then choose sensitivity sampling, deterministic geometric summaries, or merge-reduce and show exactly how local guarantees compose.