An MBR-Oriented Approach for Efficient Skyline Query Processing

Ji Zhang, Wenlu Wang, Xunfei Jiang, Wei-Shinn Ku, Hua Lu

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review


This research proposes an advanced approach that improves the efficiency of skyline query processing by significantly reducing the computational cost on object comparisons, i.e., dominance tests between objects. Our solutions are based on two novel concepts. The skyline query over Minimum Bounding Rectangles (MBRs) receives a set of MBRs and returns the MBRs that are not dominated by other MBRs. In the dominance test for MBRs, the detailed attribute values of objects in the MBRs are not accessed. Moreover, the dependent group of MBRs reduces the search space for dominance tests. Objects in an MBR are only compared with the ones in the corresponding dependent groups of the MBR rather than with the entire dataset. Our solutions apply the two concepts to the R-tree in order to use its hierarchical structure in which every node is a natural abstraction of an MBR. Specifically, given the R-tree index of an input dataset, we first eliminate unqualified objects by utilizing the skyline query over MBRs (i.e., intermediate nodes in the R-tree). Subsequently, we generate dependent groups for the skyline MBRs. Two dependent group generation methods that rely on either the sorting technique or the R-tree index are developed. Further, we apply an existing skyline algorithm to every dependent group, and the results of the original skyline query are the union of skyline objects in the dependent groups. In addition, we also analyze the cardinality of the two new concepts based on a probabilistic model, which enables us to analyze the computational complexity of the proposed solutions. Our experimental results show that the proposed solutions are clearly more efficient than the state-of-the-art approaches.
Titel35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019
Antal sider12
ISBN (Trykt)9781538674758
StatusUdgivet - 2019
Udgivet eksterntJa
Begivenhed35th International Conference on Data Engineering (ICDE) - Macau, Kina
Varighed: 8 apr. 201911 apr. 2019
Konferencens nummer: 35


Konference35th International Conference on Data Engineering (ICDE)

Citer dette