在数据流中实现细粒度公平性,实时监测并重排数据提升公平性。
Continuous Fairness On Data Streams
- 按区块细粒度定义公平性,支持大窗口下的精准控制。
- 毫秒级处理,每秒可处理约3万次查询,重排后公平性提升50%-95%。
- 适合需要持续公平性的实时系统,如推荐、信贷审批流。
我们研究在数据流滑动窗口中持续保证群体公平性的方法。提出一种新型公平性模型,在每个滑动窗口内以更细粒度的区块为单位确保公平性,尤其适用于窗口较大的场景。在此框架下,解决两大挑战:高效监测每个窗口是否满足区块级群体公平性,以及在公平性被违反时尽可能有效地重排当前窗口数据。为实现实时监测,设计基于概要的数据结构,以极低开销维护属性分布;同时开发出最优且高效的重排算法,并提供严格的理论保障。在四个真实世界流式场景上的评估表明,该方法具备实际有效性:平均达到约30,000次查询/秒的吞吐量,处理延迟为毫秒级;重排算法在特定情况下将区块级公平性提升高达95%,平均提升50%-60%。定性分析进一步凸显区块级公平性相较于窗口级公平性的优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。