Previous [ 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 (March 2014)

An Efficient Pruning Method to Process Reverse Skyline Queries*

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

Full Text () Retrieve PDF document (201403_13.pdf)

Received September 28, 2011; revised March 15, 2012; accepted September 4, 2012.
Communicated by Vincent S. Tseng.
* This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF-2009-0076144, NRF- 2012R1A1A2044389).
* A preliminary version of this paper appeared in the Proceedings of 2010 IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS), Xiamen, China, Oct 2010.
+ Corresponding author: Dongseop Kwon.