An Efficient Pruning Method to Process Reverse Skyline Queries

Ah Han ； Youngbae Park ； Dongseop Kwon

《Journal of Information Science and Engineering》 30卷2期 (2014/03) Pp. 501-517

https://doi.org/10.6688/JISE.2014.30.2.13

並列摘要

Several algorithms for processing reverse skyline queries have been proposed in recent literature. However, these algorithms are based on pre-processing approaches, and hence involve complex procedures and waste storage space due to inefficient use of storage. In addition, they are not robust to frequently changing data as, they have to re-compute and update the pre-computed results. To overcome these issues, this paper proposes a novel algorithm to efficiently process reverse skyline queries using an approach based on two pruning methods: the search-area pruning method and the candidate-objects pruning method. Utilizing these pruning methods, the algorithm is able to process reverse skyline queries efficiently even in situations where data is changing frequently. The proposed algorithm also effectively reduces the inefficient use of storage under existing approaches for storing pre-computed results. We conducted extensive experiments to show that the proposed algorithm shows better performance compared to existing approaches regardless of the dimension, distribution, or size of the data.

並列關鍵字

skyline ； reverse skyline ； preference queries ； query processing ； database