@article{bc791a3693a04f83a08bd9df8efc3e58,
title = "I/O-efficient 2-d orthogonal range skyline and attrition priority queues",
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.",
keywords = "Computational geometry, External memory, Range searching, Skyline",
author = "Casper Kejlberg-Rasmussen and Yufei Tao and Konstantinos Tsakalidis and Kostas Tsichlas and Jeonghun Yoon",
note = "Funding Information: A preliminary version of this work was published in the proceedings of the 32nd symposium on Principles of Database Theory (PODS '13) [1]. The work of Yufei Tao and Jeonghun Yoon was partially supported by (i) GRF 4166/10, 4165/11, 4164/12 from HKRGC and (ii) project R31-30007 of the World Class University program under the National Research Foundation of Korea, Ministry of Education, Science and Technology of Korea. The work of Konstantinos Tsakalidis was partially supported by NSF grants CCF-1319648 and CCF-1533564. Publisher Copyright: {\textcopyright} 2020 Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",
year = "2021",
month = feb,
doi = "10.1016/j.comgeo.2020.101689",
language = "English",
volume = "93",
journal = "Computational Geometry: Theory and Applications",
issn = "0925-7721",
publisher = "Elsevier B.V.",
}