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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Streaming Rank-Happiness Maximization Queries Under Group Fairness Constraints

  • Conghao Liu,
  • Jiping Zheng

摘要

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.