Streaming Rank-Happiness Maximization Queries Under Group Fairness Constraints
摘要
In multi-criteria decision-making, the happiness maximization query, a.k.a. the regret minimization query, has been an important tool besides the top-k and skyline queries, and its objective is to select a small subset of tuples that retains the best score across multiple criteria. As a variant of happiness-based queries, the rank-happiness maximization query integrates the concept of rank into the happiness ratio, preventing the ratio from being perceived as an arbitrary numerical value which frequently confuses users. Meanwhile, in many real-world scenarios, data arrives in a streaming manner while fairness concerns remain persistently relevant. However, existing algorithms for multi-criteria decision-making neglect the fairness concerns when processing streaming data. In this paper, we study the streaming rank-happiness maximization queries under group fairness constraints. We employ the average rank-happiness ratio as a metric to measure users’ satisfaction, thereby avoiding bias toward a few dissatisfied users. As the average rank-happiness function is monotone and submodular, we formulate the group fairness constraints as matroid constraints. Thus, we convert our problem into a streaming submodular maximization problem under a matroid constraint and propose the FairStream algorithm with provable theoretical guarantees to solve the problem. Extensive experiments on real-world and synthetic datasets confirm the effectiveness and efficiency of our proposed algorithm.