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

DOI10.1016/J.COMGEO.2020.101689MaRDI QIDQ827322zbMATH OpenOpenAlexFDO

Authors Casper Kejlberg-Rasmussen, Yufei Tao, Konstantinos Tsakalidis, Kostas Tsichlas, Jeonghun Yoon

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2020.101689

zbMATH Keywords

computational geometryrange searchingexternal memoryskyline

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Output-sensitive skyline algorithms in external memory
• I/O-optimal categorical 3-sided skyline queries
• Optimal planar orthogonal skyline counting queries
• Dynamic planar range skyline queries in log logarithmic expected time
• Worst-case efficient external-memory priority queues

Cites work

• A new approach to the dynamic maintenance of maximal points in a plane
• Dynamic Maintenance of Maxima of 2-d Point Sets
• Dynamic Planar Range Maxima Queries
• Dynamic indexability and the optimality of B-trees
• I/O-efficient data structures for colored range and prefix reporting
• Lower bounds for intersection searching and fractional cascading in higher dimension
• Lower bounds for orthogonal range searching: I. The reporting case
• Maintenance of configurations in the plane
• On Finding the Maxima of a Set of Vectors
• On a model of indexability and its bounds for range queries
• On rectangular visibility
• On the dynamic maintenance of maximal points in the plane
• Optimal External Memory Interval Management
• Optimal planar orthogonal skyline counting queries
• Purely functional, real-time deques with catenation
• Range aggregate maximal points in the plane
• Surpassing the information theoretic bound with fusion trees
• Time-space trade-offs for predecessor search
• Worst-case data structures for the priority queue with attrition

Cited in

(3)

• Output-sensitive skyline algorithms in external memory
• Two-dimensional range successor in optimal time and almost linear space
• I/O-optimal categorical 3-sided skyline queries

This page was built for publication: I/O-efficient 2-d orthogonal range skyline and attrition priority queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827322)