Continuous monitoring of moving skyline and top-k queries

Given a set of criteria, an object o dominates another object $$o'$$ if o is more preferable than $$o'$$ according to every criterion. A skyline query returns every object that is not dominated by any other object. A top-k query returns k most preferred objects according to a given scoring function. In this paper, we study the problem of continuously monitoring moving skyline queries and moving top-k queries where one of the criteria is the distance between the objects and the moving query. We propose safe zone-based techniques 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. We present several non-trivial optimizations and propose an efficient algorithm for safe zone construction for both the skyline queries and top-k queries. Our techniques for the moving top-k queries are generic in the sense that these are immediately applicable to any top-k query as long as its scoring function is monotonic. Furthermore, we show that the proposed techniques can also be extended to monitor various other queries for different distance metrics. Our experiments demonstrate that the cost of our techniques is reasonably close to a lower bound cost and is several orders of magnitude lower than the cost of a naive algorithm.