Fairness Preserving Data Summarization via Coresets

26 concepts11 papers1 proposal

Large-scale data optimization algorithms, such as $k$-means clustering, selection, or regression, are computationally expensive. To scale them to massive datasets, researchers frequently use coresets—small, weighted subsets of the original data that act as a proxy. Running an algorithm on a well-constructed coreset yields nearly the same solution as running it on the full dataset, but in a fraction of the time.

However, when we introduce fairness constraints—such as ensuring demographic groups are represented according to specific quotas or minimizing the maximum error across groups—standard coresets break down. Because standard data reduction techniques optimize for global geometric representation, they often discard minority sub-populations or distort demographic proportions. If the coreset itself is unrepresentative, any downstream fairness-aware optimization is doomed to fail.

To solve this, a new paradigm has emerged: fairness-preserving data summarization. The fundamental insight is that a data summary must preserve both the spatial geometry of the dataset and the distribution of its sensitive attributes simultaneously.

Tracking Geometry and Demographics Simultaneously

As introduced by Huang et al. in Coresets for Clustering with Fairness Constraints, fair coresets compress millions of data points into a tiny proxy whose size is completely independent of the original dataset's cardinality. Instead, the size depends on the number of protected groups and the data's dimensionality.

How do these summaries maintain this balance? The core mechanism relies on tracking group metadata alongside spatial coordinates. For instance, Braverman et al. in Relative Error Fair Clustering in the Weak-Strong Oracle Model demonstrate that by maintaining explicit metadata regarding group membership for each point in the summary, downstream algorithms can accurately evaluate disparate impact without accessing the full dataset.

Similarly, Schmidt et al. in Fair Coresets and Streaming Algorithms for Fair k-Means Clustering utilize a movement-based approach. Data points are relocated to common positions, and groups of points sharing the same sensitive attribute at that location are compressed into a single coreset point that tracks their exact counts. This ensures that the weighted representation of sensitive attributes remains consistent with the original population.

Reclaiming Composability for Streaming and Distributed Data

In massive data applications, data often arrives in streams or is distributed across multiple servers. Standard coresets are naturally composable: you can compute a coreset on Partition A and another on Partition B, merge them, and compress the result again. However, as noted by Schmidt et al. in Fair Coresets and Streaming Algorithms for Fair k-means, this crucial composability property is lost when naive fairness constraints are introduced, because local partitions lack global demographic context.

To reintroduce composability, researchers have developed two primary strategies:

1. The Union of Group-Specific Coresets

One elegant way to ensure fairness is to treat each demographic group as its own dataset. Gowda et al. show in Socially Fair Center-based and Linear Subspace Clustering that a strong coreset for a minimax fairness objective (which minimizes the maximum average cost across groups) can be constructed simply by taking the union of individual strong coresets generated for each demographic group. This allows existing, highly optimized coreset algorithms to be reused without modification.

Similarly, Wang et al. apply this principle to max-min diversification in Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms, selecting representative candidates from demographic groups independently before performing a global optimization.

2. Pivots and Assignment Costs

For streaming environments where data cannot be stored, Chiplunkar et al. propose a two-pass streaming mechanism for fair $k$-center clustering in How to Solve Fair k-Center in Massive Data Models. The first pass identifies a set of distant spatial "pivot" points, and the second pass collects demographic group representatives near those pivots. This keeps the memory footprint proportional only to the product of the summary size and the number of demographic groups.

For even more dynamic environments, such as sliding windows where data expires over time, Cohen-Addad et al. introduce assignment-preserving coresets in Fair Clustering in the Sliding Window Model. These summaries track data points alongside their group-specific assignment costs, allowing real-time querying of any recent window with minimal memory overhead by introducing a small amount of slack into the fairness constraints.

Preserving Feasibility and High-Dimensional Fairness

Why do these summaries actually work when fed into complex optimization models? The secret lies in preserving the feasibility region of the original problem.

Chhaya et al. demonstrate in On Coresets for Fair Regression and Individually Fair Clustering that by preserving the local density of a dataset through calibrated sampling, any solution that satisfies individual fairness constraints on the summary is guaranteed to remain feasible on the full dataset. This prevents the optimization algorithm from choosing "fair" solutions on the summary that turn out to be highly unfair or invalid when applied to the actual population.

Furthermore, this paradigm extends beyond clustering to high-dimensional problems like low-rank approximation and column subset selection. As Song et al. show in On Socially Fair Low-Rank Approximation and Column Subset Selection, high-dimensional datasets can be projected into lower-dimensional spaces using importance-based sampling or random projections. These compressed representations preserve the error characteristics of individual sub-groups, ensuring that dimensionality reduction does not inadvertently optimize for the majority at the expense of minority sub-populations.

By shifting the fairness intervention from the algorithm stage to the data summarization stage, fairness-preserving coresets decouple optimization complexity from dataset size. Whether through linear-time approximations like the one proposed by Kleindessner et al. in Fair k-Center Clustering for Data Summarization or 100x computational speedups via calibrated sampling, this research direction ensures that scaling up to massive datasets does not require sacrificing social equity.

Key Foundational Work

Fair Coresets and Streaming Algorithms for Fair k-means (2019) — contributed 6 concept elements to this direction.
Coresets for Clustering with Fairness Constraints (2019) — contributed 3 concept elements to this direction.
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering (2018) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fairness_aware_data_summarization_60403fd3,
  title = {fairness-aware data summarization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-aware-data-summarization/rdr_60403fd3e391457789dd42d68c61ee15},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_fairness_aware_data_summarization_60403fd3_v1,
  title = {fairness-aware data summarization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-aware-data-summarization/rdr_60403fd3e391457789dd42d68c61ee15/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake