Skyline Queries in O(1) time?
share
The skyline of a set P of points (SKY(P)) consists of the "best" points with respect to minimization or maximization of the attribute values. A point p dominates another point q if p is as good as q in all dimensions and it is strictly better than q in at least one dimension. In this work, we focus on the static 2-d space and provide expected performance guarantees for 3-sided Range Skyline Queries on the Grid, where N is the cardinality of P, B the size of a disk block, and R the capacity of main memory. We present the MLR-tree, which offers optimal expected cost for finding planar skyline points in a 3-sided query rectangle, q=[a,b]×(-∞,d], in both RAM and I/O model on the grid [1,M]× [1,M], by single scanning only the points contained in SKY(P). In particular, it supports skyline queries in a 3-sided range in O(t· t_PAM(N)) time (O((t/B)· t_PAM(N)) I/Os), where t is the answer size and t_PAM(N) the time required for answering predecessor queries for d in a PAM (Predecessor Access Method) structure, which is a special component of MLR-tree and stores efficiently root-to-leaf paths or sub-paths. By choosing PAM structures with O(1) expected time for predecessor queries under discrete μ-random distributions of the x and y coordinates, MLR-tree supports skyline queries in optimal O(t) expected time (O(t/B) expected number of I/Os) with high probability. The space cost becomes superlinear and can be reduced to linear for many special practical cases. If we choose a PAM structure with O(1) amortized time for batched predecessor queries (under no assumption on distributions of the x and y coordinates), MLR-tree supports batched skyline queries in optimal O(t) amortized time, however the space becomes exponential. In dynamic case, the update time complexity is affected by a O(log^2N) factor.
READ FULL TEXT