Efficient computation of k representative regret minimization G-Skyline groups

The G-Skyline queries identify Pareto optimal groups not g-dominated by any other group, playing a crucial role in various fields. The k representative G-Skyline queries aim to control the output size and obtain representative results, facilitating user decision-making. However, existing k representative G-Skyline queries cannot meet user require- ments well, particularly lacking in quantitative representativeness and high efficiency. In this paper, we propose a novel k representative G- Skyline query, k representative r egret minimization G-Skyline (kRMG) query, designed to find k G-Skyline groups to minimize the maximum regret ratio. The kRMG query provides maximum regret ratio as quan- titative representativeness, aiding users in assessing result quality. Then, we propose a novel algorithm, PHP to rapidly obtain kRMG. Specifi- cally, PHP proposes prominent G-Skyline groups based on group vectors as small-scale candidate groups, significantly reducing the number of candidates. Additionally, PHP proposes an efficient hierarchical pruning strategy to rapidly obtain prominent G-Skyline groups, effectively elimi- nating numerous redundant groups. Extensive experiments on synthetic and real datasets demonstrate the efficiency and reliability of PHP.