I/O-efficient planar range skyline

Abstract

In the planar range skyline reporting problem, the goal is to store a set P of n 2D points in a structure such that, given a query rectangle Q = [α_1, α_2] × [β_1, β_2] the maxima (a.k.a. skyline) of P∩Q can be reported efficiently. The query is 3-sided if an edge of Q is grounded, giving rise to two variants: top-open queries (β_2 = ∞) and left-open queries (α_1 = -∞).

This paper presents results in external memory under the O(n/B) space budget (B is the block size), specifically: - We give structures that answer top-open queries in O(log_B n + k/B), O(loglog_B U + k/B), and O(1 +k/B) I/Os when the universe is R^2, a U×U grid, and rank space [O(n)]^2, respectively (where k is the number of reported points). The query complexity is optimal in all cases. - We show that the left-open case is harder, such that any linear-size structure must incur Ω((n/B)^ε + k/B) I/Os to answer a query. In fact, this case turns out to be just as difficult as the general 4-sided queries, for which we provide a static structure with the optimal query cost O((n/B)^ε + k/B).