Dynamic Planar Range Skyline Queries in Log logarithmic Expected Time

Abstract The skyline of a set P of points 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 2-d space and provide expected performance guarantees for dynamic (insertions and deletions) 3-sided range skyline queries. We assume that the x and y coordinates of the points are drawn from a class of distributions and present the ML-tree (Modified Layered Range-tree), which attains O ( log 2 ⁡ N log ⁡ log ⁡ N ) expected update time and O ( t log ⁡ log ⁡ N ) time with high probability for finding planar skyline points in a 3-sided query rectangle q = [ a , b ] × [ d , + ∞ ) in the RAM model, where N is the cardinality of P and t is the answer size.