I/O-efficient 2-d orthogonal range skyline and attrition priority queues

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Casper Kejlberg-Rasmussen
  • Yufei Tao, Chinese University of Hong Kong
  • ,
  • Konstantinos Tsakalidis, University of Liverpool
  • ,
  • Kostas Tsichlas, University of Patras
  • ,
  • Jeonghun Yoon, Korea Advanced Institute of Science and Technology

We present the first static and dynamic external memory data structures for variants of 2-d orthogonal range skyline reporting with worst-case logarithmic query and update I/O-complexity. The results are obtained by using persistent data structures and by extending the attrition priorities queues of Sundar (1989) [26] to also support real-time concatenation, a result of independent interest. We show that the problem is as hard as standard 2-d orthogonal range reporting in the indexability model by a lower bound on the I/O-complexity of 2-d orthogonal anti-dominance skyline reporting queries.

Original languageEnglish
Article number101689
JournalComputational Geometry: Theory and Applications
Volume93
ISSN0925-7721
DOIs
Publication statusPublished - Feb 2021

    Research areas

  • Computational geometry, External memory, Range searching, Skyline

See relations at Aarhus University Citationformats

ID: 213168640