dorsal/arxiv
View SchemaContinuous Fairness On Data Streams
| Authors | Subhodeep Ghosh, Zhihui Du, Angela Bonifati, Manish Kumar, David Bader, Senjuti Basu Roy |
|---|---|
| Categories | |
| ArXiv ID | 2601.08976vv1 |
| URL | https://arxiv.org/abs/2601.08976 |
| License | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Abstract
We study the problem of enforcing continuous group fairness over windows in data streams. We propose a novel fairness model that ensures group fairness at a finer granularity level (referred to as block) within each sliding window. This formulation is particularly useful when the window size is large, making it desirable to enforce fairness at a finer granularity. Within this framework, we address two key challenges: efficiently monitoring whether each sliding window satisfies block-level group fairness, and reordering the current window as effectively as possible when fairness is violated. To enable real-time monitoring, we design sketch-based data structures that maintain attribute distributions with minimal overhead. We also develop optimal, efficient algorithms for the reordering task, supported by rigorous theoretical guarantees. Our evaluation on four real-world streaming scenarios demonstrates the practical effectiveness of our approach. We achieve millisecond-level processing and a throughput of approximately 30,000 queries per second on average, depending on system parameters. The stream reordering algorithm improves block-level group fairness by up to 95% in certain cases, and by 50-60% on average across datasets. A qualitative study further highlights the advantages of block-level fairness compared to window-level fairness.
{
"annotation_id": "02c65439-26f7-45ce-a5e3-eec8214051ea",
"date_created": "2026-02-17T05:53:20.182000Z",
"date_modified": "2026-02-17T05:53:20.182000Z",
"file_hash": "cff910441c4902dc61553d7381d0f3003a3efcaae42b5bf8ca41125fc5db91d3",
"private": false,
"record": {
"abstract": "We study the problem of enforcing continuous group fairness over windows in data streams. We propose a novel fairness model that ensures group fairness at a finer granularity level (referred to as block) within each sliding window. This formulation is particularly useful when the window size is large, making it desirable to enforce fairness at a finer granularity. Within this framework, we address two key challenges: efficiently monitoring whether each sliding window satisfies block-level group fairness, and reordering the current window as effectively as possible when fairness is violated. To enable real-time monitoring, we design sketch-based data structures that maintain attribute distributions with minimal overhead. We also develop optimal, efficient algorithms for the reordering task, supported by rigorous theoretical guarantees. Our evaluation on four real-world streaming scenarios demonstrates the practical effectiveness of our approach. We achieve millisecond-level processing and a throughput of approximately 30,000 queries per second on average, depending on system parameters. The stream reordering algorithm improves block-level group fairness by up to 95% in certain cases, and by 50-60% on average across datasets. A qualitative study further highlights the advantages of block-level fairness compared to window-level fairness.",
"arxiv_id": "2601.08976",
"authors": [
"Subhodeep Ghosh",
"Zhihui Du",
"Angela Bonifati",
"Manish Kumar",
"David Bader",
"Senjuti Basu Roy"
],
"categories": [
"cs.LG",
"cs.CY",
"cs.DS"
],
"license": "http://creativecommons.org/licenses/by-nc-nd/4.0/",
"title": "Continuous Fairness On Data Streams",
"url": "https://arxiv.org/abs/2601.08976",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0b015d69-b21e-4235-ac69-8d8c9ea1d5bf",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}