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

Abstract

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.
OriginalsprogEngelsk
Titel35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019
Antal sider12
ForlagIEEE
Publikationsdato2019
Sider806-817
ISBN (Trykt)9781538674758
DOI
StatusUdgivet - 2019
Udgivet eksterntJa
Begivenhed35th International Conference on Data Engineering (ICDE) - Macau, Kina
Varighed: 8 apr. 201911 apr. 2019
Konferencens nummer: 35
https://www.computer.org/csdl/proceedings/icde/2019/1aDSOMTGCIw

Konference

Konference35th International Conference on Data Engineering (ICDE)
Nummer35
LandKina
ByMacau
Periode08/04/201911/04/2019
Internetadresse

Citer dette

Zhang, J., Wang, W., Jiang, X., Ku, W-S., & Lu, H. (2019). An MBR-Oriented Approach for Efficient Skyline Query Processing. I 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019 (s. 806-817). IEEE. https://doi.org/10.1109/ICDE.2019.00077