When datasets grow to millions or billions of points, traditional optimization algorithms break down. Algorithms for clustering, data mining, and subset selection typically require global access to the entire dataset. However, in modern large-scale computing, data is rarely sitting in one place; it is either distributed across thousands of machines in a cloud cluster or arriving continuously as an unbounded stream.
Moving all this data to a single central coordinator creates an impossible communication bottleneck. To bypass this, we need a way to compress data locally into tiny, highly accurate summaries. Crucially, these summaries must be composable: if we compute summaries independently on different chunks of data, we must be able to merge them into a single global summary without losing our theoretical accuracy guarantees.
This design philosophy underpins the merge-and-reduce framework using composable coresets. It allows us to scale complex geometric and combinatorial optimization problems to arbitrary sizes.
The Intuition of Composability
A coreset is a small, weighted subset of a dataset that acts as a proxy for the full collection. For any candidate solution (such as a set of cluster centers), the cost or quality of that solution evaluated on the coreset closely approximates the cost evaluated on the full dataset within a small error factor $\epsilon$.
The defining magic of a composable coreset is its behavior under unions. Suppose we have a massive dataset $X$ that is partitioned into two disjoint subsets, $A$ and $B$. If we compute a coreset $C(A)$ for $A$ and a coreset $C(B)$ for $B$ completely independently, their union $C(A) \cup C(B)$ is guaranteed to be a valid coreset for the entire dataset $A \cup B$.
Distributed Chunks: [ Subset A ] [ Subset B ]
│ │
Local Compression: ▼ ▼
[ Coreset C(A) ] [ Coreset C(B) ]
│ │
Merging: └───────────┬─────────────┘
▼
Global Summary: [ C(A) ∪ C(B) ]
Why does this simple property hold? Because the approximation guarantees are uniform. If $C(A)$ preserves the objective function for all possible solutions to our problem, and $C(B)$ does the same for $B$, then their combined representation preserves the sum of the objectives across the entire dataset. As demonstrated in Randomized Composable Coresets for Matching and Vertex Cover by Assadi et al., this property allows multiple processors to execute simultaneous, independent communication protocols, sending small-scale representations to a central coordinator for global solution estimation without any back-and-forth communication.
The Merge-and-Reduce Framework
If we simply keep taking the union of local coresets, the size of our summary will grow linearly with the number of data partitions. To prevent this summary explosion, we use a hierarchical tree structure known as the merge-and-reduce framework.
When two or more local coresets are merged, the resulting union can be treated as a new dataset and compressed again using the same coreset algorithm.
Layer 2 (Global): [ Bounded Coreset ]
▲
( Reduce Step )
│
Layer 1 (Merged): [ C(A) ∪ C(B) ∪ ... ]
▲
( Merge Step )
┌────────────────────┴────────────────────┐
Layer 0 (Local): [ Coreset C(A) ] [ Coreset C(B) ] [ Coreset C(C) ]
In Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction, Ding et al. show that this merge-and-reduce property ensures the final representation size remains completely independent of the total number of original data points. This enables two powerful paradigms:
- Massively Parallel Computing (MapReduce): Data chunks are summarized in parallel on worker nodes. The workers send only their tiny coresets to a central master node, which merges and reduces them to compute the final global solution.
- Streaming Data Analysis: As data arrives in continuous batches, we can maintain a running coreset in memory. When the memory fills up, we reduce the current coreset, allowing us to process unbounded streams with a memory footprint that scales only logarithmically with the stream length. For example, Rosman et al. leverage this mechanism for the $k$-segmentation of streaming high-dimensional video and financial data, achieving massive speedups via embarrassingly parallel processing.
Preserving Geometry in Distributed Clustering
Clustering problems—such as $k$-means, $k$-median, and $k$-center—are natural candidates for composable coresets because their objective functions are additive across disjoint partitions.
For complex, non-linear data structures, Jiang et al. show in Coresets for Kernel Clustering that strong coresets can be constructed for general kernels. By reducing a dataset into a tiny reweighted subset independent of both the original data size and the feature space dimension, they break the notorious $O(n^2)$ computational barrier inherent to kernel methods.
However, scaling clustering becomes significantly harder when real-world constraints are introduced:
- Capacity Constraints: In balanced clustering, clusters have strict capacity bounds. Bhaskara et al. tackle this in Distributed Balanced Clustering via Mapping Coresets. by introducing mapping coresets. These summaries preserve not just the locations of points, but also their point-to-center assignment capacities across disjoint partitions, providing the first distributed approximation algorithms for capacitated clustering.
- Outliers: When a dataset contains noise, a naive local summary might accidentally discard global outliers. In k-Center Clustering with Outliers in the MPC and Streaming Model, de Berg et al. overcome this by designing a "mini-ball covering" technique. By ensuring that local geometric coverings combine transitively, the authors maintain consistency and mathematical guarantees whether data is processed in parallel or as a stream.
- Statistical Mixtures: Beyond hard clustering, Lučić et al. demonstrate in Training Gaussian Mixture Models at Scale via Coresets that the principle of composability allows multiple data subsets to be merged and re-compressed to train complex Gaussian Mixture Models (GMMs) with negligible loss in accuracy.
On an even larger scale, Voevodski shows in Large Scale K-Median Clustering for Stable Clustering Instances that massive datasets can be compressed into local Voronoi cell statistics. This proves that distributed heavy-lifting can be completely decoupled from centralized global optimization when the underlying data instances are stable.
Maximizing Diversity and Information Content
A distinct challenge arises in diversity maximization—the task of selecting a small subset of items that are as "spread out" or distinct as possible (e.g., via determinant maximization). This problem is inherently global; an item that looks highly diverse within a local partition might be completely redundant when compared to items sitting in a different partition.
As Gollapudi et al. note in Composable Coresets for Determinant Maximization: Greedy is Almost Optimal, this global interaction imposes severe constraints on algorithm design. It is incredibly difficult to ensure that a small summary generated locally contains the specific elements necessary to represent the diversity of the entire dataset when combined with other summaries.
To solve this, researchers rely on geometric and submodular properties:
- Directional Height and Local Search: In Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm, Mahabadi et al. leverage a geometric concept called "directional height." The authors prove that a simple local search algorithm can select small data summaries on individual machines that, when merged, closely approximate the global determinant optimum.
- The Power of Greedy Selection: Gollapudi et al. proved that the standard, intuitive Greedy algorithm is far more powerful than previously thought, providing a tight, near-optimal approximation bound when used to construct composable coresets for diversity maximization.
- Graph and Nearest-Neighbor Measures: In Improved Diversity Maximization Algorithms for Matching and Pseudoforest, Mahabadi et al. extend these guarantees to matching-based and nearest-neighbor-based diversity measures, maintaining constant-factor approximations even when data is arbitrarily partitioned across multiple machines.
By validating these properties, Ceccarello et al. show in MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension that diversity maximization can scale seamlessly across MapReduce clusters while maintaining strict theoretical guarantees.
Incorporating Fairness Constraints
Modern data summarization tasks often require that the chosen summary respects group representation bounds (e.g., ensuring demographic fairness across gender or race). Composable coresets handle these constraints elegantly because data summarization can be performed independently across different categories or partitions of a dataset.
In Fair Coresets and Streaming Algorithms for Fair k-Means Clustering, Schmidt et al. introduce "fair coresets"—small, weighted summaries that preserve fairness constraints during compression. By adapting movement-based coreset techniques, the authors enable fair $k$-means clustering to scale to massive streaming datasets.
For diversity tasks, Wang et al. combine integer linear programming with composable coresets in Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms, allowing systems to select diverse subsets from individual groups and combine them into a smaller global pool.
Finally, in Core-sets for Fair and Diverse Data Summarization, Mahabadi et al. prove that the union of category-specific local summaries perfectly maintains the mathematical guarantees of the global diversity objective. This insight allows systems to process and store only small, representative subsets of historical data, yielding massive speedups and incremental updates in streaming environments.
Conclusion
The power of mergeable data summaries lies in their ability to decouple massive data processing from centralized decision-making. Whether applied to geometric clustering, scientific visualization across parallel simulation blocks (as explored by Yang et al. in Correlation-aware probabilistic data summarization for large-scale multi-block scientific data visualization), or fair diversity maximization, the core mechanism remains the same. By ensuring that local summaries compose transitively, we can confidently compress data at its source, knowing that the global solution found on the merged pieces will be nearly as good as a solution found by looking at the entire world at once.
Key Foundational Work
Coresets for k-Segmentation of Streaming Data (2014) — contributed 2 concept elements to this direction.
Distributed Balanced Clustering via Mapping Coresets. (2014) — contributed 1 concept elements to this direction.
The single pixel GPS: learning big data signals from tiny coresets (2012) — contributed 1 concept elements to this direction.