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

DOI10.1016/J.COMGEO.2020.101689zbMATH Open1470.68235OpenAlexW3045481965MaRDI QIDQ827322FDOQ827322

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

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

zbMATH Keywords

computational geometryrange searchingexternal memoryskyline

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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)