Fast Reverse Skyline Processing without Pre-computation
Reverse skyline queries, which retrieve a set of objects whose dynamic skyline contains a given query, point, are useful and valuable for many applications such as business location and environmental monitoring applications. Though there are several methods for processing reverse skyline queries, they are based on pre-processing. Since they waste time and space to pre-compute necessary data and to manage the pre-computed data, they are not feasible for some applications. In this paper, we propose a robust algorithm to fast and efficiently compute reverse skyline queries without pre-computation. Since the proposed algorithm is based on a branch-and-bound approach, it can access correct nodes by minimizing unnecessary traverses. It can also reduce candidates by using two pruning methods introduced throughout this paper, and it is efficient over frequently changing datasets since it does not pre-compute and maintain any data. To prove a performance of our algorithm, extensive experiences are conducted. The experimental result shows that the proposed algorithm is superior to its competitors.
reverse skyline branch and bound
Ah Han Dongseop Kwon Youngbae Park
Dept.of Computer Engineering Myongji University Yongin-si,Gyeonggi-do, Korea Dept.of Computer Engineering Myongji University Yongin-si, Gyeonggi-do, Korea
国际会议
厦门
英文
288-292
2010-10-29（万方平台首次上网日期，不代表论文的发表时间）