1. I/O-efficient 2-d orthogonal range skyline and attrition priority queues.
- Author
-
Kejlberg-Rasmussen, Casper, Tao, Yufei, Tsakalidis, Konstantinos, Tsichlas, Kostas, and Yoon, Jeonghun
- Subjects
- *
DATA structures , *COMPUTATIONAL geometry - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF