Dynamic skylines considering range queries

Abstract

Dynamic skyline queries are practical in many applications. For example, if no data exist to fully satisfy a query q in an information system, the data "closer" to the requirements of q can be retrieved as answers. Finding the nearest neighbors of q can be a solution; yet finding the data not dynamically dominated by any other data with respect to q, i.e. the dynamic skyline regarding q can be another solution. A data point p is defined to dynamically dominate another data point s, if the distance between each dimension of p and the corresponding dimension of q is no larger than the corresponding distance regarding s and q and at least in one dimension, the corresponding distance regarding p and q is smaller than that regarding s and q. Some approaches for answering dynamic skyline queries have been proposed. However, the existing approaches only consider the query as a point rather than a range in each dimension, also frequently issued by users. We make the first attempt to solve a problem of computing dynamic skylines considering range queries in this paper. To deal with this problem, we propose an efficient algorithm based on the grid index and a novel variant of the well-known Z-order curve. Moreover, a series of experiments are performed to evaluate the proposed algorithm and the experiment results demonstrate that it is effective and efficient. © 2011 Springer-Verlag.