Efficient algorithm for k representative regret minimization G-Skyline queries

The G-Skyline queries identify Pareto optimal groups not g-dominated by any other group of equal size, crucial in many fields. The k representative G-Skyline queries are proposed to control the output size and obtain representative results, facilitating user decision-making. However, existing k representative G-Skyline queries cannot meet user requirements well, particularly lacking in quantitative representativeness and high efficiency. In this paper, we propose a novel k representative regret minimization G-Skyline (kRMG) query, which aims to find k G-Skyline groups to minimize the maximum regret ratio. The kRMG query provides maximum regret ratio as quantitative representativeness, which helps user decision-making. Then, we propose two novel algorithms called PHP and PHP* to rapidly obtain kRMG. Specifically, PHP proposes prominent G-Skyline groups based on group vectors as candidates, significantly fewer than all G-Skyline groups. Then, PHP proposes an efficient hierarchical pruning strategy to rapidly generate prominent G-Skyline groups, which eliminates many redundant groups. Based on PHP, PHP* designs a two-phase generation strategy to reduce comparison cost in identifying prominent G-Skyline groups. And PHP* proposes a skyline-set reuse strategy, which significantly reduces the number of candidate groups that need to be generated. Extensive experiments on synthetic and real-world datasets show the efficiency and reliability of PHP and PHP*.