An efficient approach towards index structures for skyline queries
Abstract 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 intellig...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2025-08-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s44443-025-00183-3 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849235683154067456 |
|---|---|
| author | Huaiguang Song Zhongbo Wu Binglei Guo Zhao Wu Min Wang |
| author_facet | Huaiguang Song Zhongbo Wu Binglei Guo Zhao Wu Min Wang |
| author_sort | Huaiguang Song |
| collection | DOAJ |
| description | Abstract 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. |
| format | Article |
| id | doaj-art-6f5ee76087ec4b3cafb05c2eb9a6a0c9 |
| institution | Kabale University |
| issn | 1319-1578 2213-1248 |
| language | English |
| publishDate | 2025-08-01 |
| publisher | Springer |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj-art-6f5ee76087ec4b3cafb05c2eb9a6a0c92025-08-20T04:02:42ZengSpringerJournal of King Saud University: Computer and Information Sciences1319-15782213-12482025-08-0137612310.1007/s44443-025-00183-3An efficient approach towards index structures for skyline queriesHuaiguang Song0Zhongbo Wu1Binglei Guo2Zhao Wu3Min Wang4Department of Computer Engineering, Hubei University of Arts and ScienceDepartment of Computer Engineering, Hubei University of Arts and ScienceDepartment of Computer Engineering, Hubei University of Arts and ScienceDepartment of Computer Engineering, Hubei University of Arts and ScienceDepartment of Computer Engineering, Hubei University of Arts and ScienceAbstract 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.https://doi.org/10.1007/s44443-025-00183-3Skyline queriesIndex structuresDiverse distribution dataDominance tests |
| spellingShingle | Huaiguang Song Zhongbo Wu Binglei Guo Zhao Wu Min Wang An efficient approach towards index structures for skyline queries Journal of King Saud University: Computer and Information Sciences Skyline queries Index structures Diverse distribution data Dominance tests |
| title | An efficient approach towards index structures for skyline queries |
| title_full | An efficient approach towards index structures for skyline queries |
| title_fullStr | An efficient approach towards index structures for skyline queries |
| title_full_unstemmed | An efficient approach towards index structures for skyline queries |
| title_short | An efficient approach towards index structures for skyline queries |
| title_sort | efficient approach towards index structures for skyline queries |
| topic | Skyline queries Index structures Diverse distribution data Dominance tests |
| url | https://doi.org/10.1007/s44443-025-00183-3 |
| work_keys_str_mv | AT huaiguangsong anefficientapproachtowardsindexstructuresforskylinequeries AT zhongbowu anefficientapproachtowardsindexstructuresforskylinequeries AT bingleiguo anefficientapproachtowardsindexstructuresforskylinequeries AT zhaowu anefficientapproachtowardsindexstructuresforskylinequeries AT minwang anefficientapproachtowardsindexstructuresforskylinequeries AT huaiguangsong efficientapproachtowardsindexstructuresforskylinequeries AT zhongbowu efficientapproachtowardsindexstructuresforskylinequeries AT bingleiguo efficientapproachtowardsindexstructuresforskylinequeries AT zhaowu efficientapproachtowardsindexstructuresforskylinequeries AT minwang efficientapproachtowardsindexstructuresforskylinequeries |