A safe zone based approach for monitoring moving skyline queries

Publication Type:
Conference Proceeding
ACM International Conference Proceeding Series, 2013, pp. 275 - 286
Issue Date:
Filename Description Size
Thumbnail2013005455OK.pdf595.23 kB
Adobe PDF
Full metadata record
Given a set of criterions, an object o dominates another object ó if o is more preferable than ó according to every criterion. A skyline query returns every object that is not dominated by any other object. In this paper, we study the problem of continuously monitoring a moving skyline query where one of the criterions is the distance between the objects and the moving query. We propose a safe zone based approach to address the challenge of efficiently updating the results as the query moves. A safe zone is the area such that the results of a query remain unchanged as long as the query lies inside this area. Hence, the results are required to be updated only when the query leaves its safe zone. Although the main focus of this paper is to present the techniques for Euclidean distance metric, the proposed techniques are applicable to any metric distance (e.g., Manhattan distance, road network distance). We present several non-trivial optimizations and propose an efficient algorithm for safe zone construction. Our experiments demonstrate that the cost of our safe zone based approach is reasonably close to a lower bound cost and is three orders of magnitude lower than the cost of a naïve algorithm. © 2013 ACM.
Please use this identifier to cite or link to this item: