Abstract
We study the static and dynamic planar range skyline reporting problem in the external memory model with block size B, under a linear space budget. The problem asks for an O(n/B) space data structure that stores n points in the plane, and supports reporting the k maximal input points (a.k.a.skyline) among the points that lie within a given query rectangle Q = [α1[α2] × [β1β2. When Q is 3-sided, i.e. one of its edges is grounded, two variants arise: top-open for β2 = ∞ and left-open for α1 = - ∞ (symmetrically bottom-open and right-open) queries.
We present optimal static data structures for top-open queries, for the cases where the universe is R2, a U × U grid, and rank space [O(n)]2. We also show that left-open queries are harder, as they require Ω((n/B)ε + k/B) I/Os for ε > 0, when only linear space is allowed. We show that the lower bound is tight, by a structure that supports 4-sided queries in matching complexities. Interestingly, these lower and upper bounds coincide with those of the planar orthogonal range reporting problem, i.e., the skyline requirement does not alter the problem difficulty at all!
Finally, we present the first dynamic linear space data structure that supports top-open queries in O(log2Bε n + k/B1 ε > and updates in O(log2Bε n) worst case I/Os, for ε ∈ [0, 1]. This also yields a linear space data structure for 4-sided queries with optimal query I/Os and O(log(n/B)) amortized update I/Os. We consider of independent interest the main component of our dynamic structures, a new real-time I/O-efficient and catenable variant of the fundamental structure priority queue with attrition by Sundar.
We present optimal static data structures for top-open queries, for the cases where the universe is R2, a U × U grid, and rank space [O(n)]2. We also show that left-open queries are harder, as they require Ω((n/B)ε + k/B) I/Os for ε > 0, when only linear space is allowed. We show that the lower bound is tight, by a structure that supports 4-sided queries in matching complexities. Interestingly, these lower and upper bounds coincide with those of the planar orthogonal range reporting problem, i.e., the skyline requirement does not alter the problem difficulty at all!
Finally, we present the first dynamic linear space data structure that supports top-open queries in O(log2Bε n + k/B1 ε > and updates in O(log2Bε n) worst case I/Os, for ε ∈ [0, 1]. This also yields a linear space data structure for 4-sided queries with optimal query I/Os and O(log(n/B)) amortized update I/Os. We consider of independent interest the main component of our dynamic structures, a new real-time I/O-efficient and catenable variant of the fundamental structure priority queue with attrition by Sundar.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 32nd symposium on Principles of database systems , PODS '13 |
| Editors | Richard Hull, Wenfei Fan |
| Number of pages | 12 |
| Publisher | Association for Computing Machinery |
| Publication date | 2013 |
| Pages | 103-114 |
| ISBN (Print) | 978-1-4503-2066-5 |
| DOIs | |
| Publication status | Published - 2013 |
| Event | ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - Rome, Italy Duration: 23 Jan 2013 → 25 Jan 2013 Conference number: 40 |
Conference
| Conference | ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages |
|---|---|
| Number | 40 |
| Country/Territory | Italy |
| City | Rome |
| Period | 23/01/2013 → 25/01/2013 |
| Series | A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings |
|---|---|
| ISSN | 1055-6338 |
Keywords
- skyline
- range reporting
- priority queues
- external memory
- data structures