JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]


Journal of Information Science and Engineering, Vol. 30 No. 2, pp. 501-517


An Efficient Pruning Method to Process Reverse Skyline Queries


AH HAN, YOUNGBAE PARK AND DONGSEOP KWON+
Department of Computer Engineering
Myongji University
Yongin-si, Gyeonggi-do, 449-728 Korea

 


    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.

 


Keywords: skyline, reverse skyline, preference queries, query processing, database

  Retrieve PDF document (JISE_201402_13.pdf)