I/O-Efficient Planar Range Skyline and Attrition Priority Queues

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

  • Casper Kejlberg-Rasmussen
  • Yufei Tao, Chinese University of Hong Kong, Hong Kong
  • Konstantinos Tsakalidis, Hong Kong University of Science and Technology, HKUST, Hong Kong
  • Kostas Tsichlas, Aristotle University of Thessaloniki, Grækenland
  • Jeonghun Yoon, Korea Advanced Institute of Science and Technology, KAIST, Sydkorea
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.
TitelProceedings of the 32nd symposium on Principles of database systems , PODS '13
RedaktørerRichard Hull, Wenfei Fan
Antal sider12
ForlagAssociation for Computing Machinery
ISBN (trykt)978-1-4503-2066-5
StatusUdgivet - 2013
BegivenhedACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - Rome, Italien
Varighed: 23 jan. 201325 jan. 2013
Konferencens nummer: 40


KonferenceACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
SerietitelA 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

Se relationer på Aarhus Universitet Citationsformater

ID: 56212015