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 requirements well, particularly lacking in quantitative representativeness and high efficiency. In this paper, we propose a novel k representative G-Skyline query, k representative regret 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 quantitative representativeness, aiding users in assessing result quality. Then, We propose a novel algorithm, PHP, to rapidly obtain kRMG. Specifically, 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 eliminating numerous redundant groups. Extensive experiments on synthetic and real datasets demonstrate the efficiency and reliability of PHP.