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).
평면상의 범위내 극대점을 구해주는 문제에서의 목표는, 2차원 공간의 점(데이터)의 집합 P와 사각형 질의(rectangle query) Q = [α_1, α_2] × [β_1, β_2] 가 주어졌을 때 P∩Q 의 극대점(스카이라인)을 효율적으로 구해줄 수 있는 자료구조를 만드는 것이다.
만약 Q의 변(edge) 하나가 없다면 우리는 그것을 3-방향 질의라고 한다. 이 경우에는 크게 두 가지의 질의의 종류로 나누어진다. 첫 번째는 윗 방향 열림 질의 Q = [α_1, α_2] × [β_1, ∞] 이고 두 번째는 왼쪽 방향 열림 질의 이다. Q = [-∞, α_2] × [β_1, β_2]. 윗 방향 열림 질의와 오른 방향 열림 질의는 서로 대응되며, 왼쪽 방향 열림 질의와 아랫 방향 열림 질의 또한 대응된다.
이 논문에서는 윗 방향 열림 질의에 대하여 최적의 질의 응답시간을 제공해주는 선형 자료 구조를 제안할 것이다. 이 결과는 외부 메모리상에서의 I/O 입출력에 대한 것이며, 자료 구조는 정적(static) 자료 구조이다. 또한 더불어 임의의 선형 자료 구조에서의 사각형 질의 응답시간에 대한 최악의 경계를 제안할 것이다.
- 데이터 집합 P 가 정적 자료 구조라고 가정하자. 데이터 포인트들의 도메인이 R^2, U×U 그리드, 순위 공간 (rank space, [O(n)]^2) 일 때 윗 방향 열림 질의에 대하여 각각 O(log_B n +k/B ), O(log log_B U +k/B ) 그리고 O(1 +k/B ) I/Os 로 대답할 수 있는 선형 선형 자료 구조를 제안할 것이다. 각각의 질의 응답시간은 모든 경우에 대해서 최적이다.
- 왼쪽 방향 열림 질의는 더 어렵다. 왼쪽 방향 열림 질의에 대하여 임의의 선형 자료 구조는 Ω((n/B)^ε+k/B) I/Os를 질의 응답시간에 대한 최악의 경계로 가지고 있다. 또한 선형 자료 구조는 일반적인 사각형 질의에 대하여 O((n/B)^ε+k/B) 를 최적 응답 질의 시간으로 가지게 된다.
