An efficient approach towards index structures for skyline queries

Given a multidimensional dataset, the skyline query is to find all objects that are not dominated by any other object in the dataset. This query represents a multi-objective optimization approach that is used extensively in various areas such as data analysis, decision support, and intelligent recommendation systems. However, even the most effective skyline query algorithms in the literature often show some limitations in dealing with diverse distribution data. By further analyzing the relationship between index structure and dominance tests, we propose the Quad*-Tree, a variant of the Quad-Tree that allows for configurable fan-out and addresses the issue of low node utilization in high-dimensional spaces. Based on Quad*-Tree, we introduce the concept of Node Dominance Groups (NDG). Based on NDG, we develop U-INDG (Upward Identification of Node Dominance Groups), a suite of novel and optimal skyline query approaches that significantly reduce the cost of dominance tests. Subsequently, we extend our approach to other index structures such as the sorted R-Tree, ZB-Tree, and Quad-Tree. Furthermore, U-INDG is simple to implement and can be efficiently scaled to various systems. Extensive experiments show that U-INDG outperforms the most efficient index-based skyline algorithms currently available. It significantly reduces query time across various types of datasets, with speedups ranging from approximately 2.4 $$\times $$ to 7.8 $$\times $$ compared to state-of-the-art algorithms, while ensuring stable performance.