2017/09/12 by Spyros Sioutas, Sioutas, Spyros, Kostas Tsichlas +10
Computer Science · #Algorithms and Data Compression #Computational Geometry and Mesh Generation #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #cs.DB
paper · pdf · doi:10.48550/arxiv.1709.03949
22 pages
arxiv created 2017/09/12 · openalex publication_date 2017/09/12 · arxiv updated 2017/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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⋅ tPAM(N)) time (O((t/B)⋅ tPAM(N)) I/Os), where t is the answer size and tPAM(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(log2N) factor.