DBScholar

Back to papers

I/O-Efficient Planar Range Skyline and Attrition Priority Queues

Summary: I/O-optimal linear-space solutions for planar range skyline: static top-open queries solved optimally across continuous, grid and rank-space models; left-open/4-sided queries require Ω((n/B)^ε + k/B) I/Os—matching orthogonal range reporting so skyline adds no extra hardness. Also the first dynamic linear-space structure supporting top-open queries in O(log_{2B^ε} n + k/B^{1-ε}) I/Os with O(log_{2B^ε} n) updates, built atop a new I/O-efficient catenable priority queue with attrition. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1607
Venue
PODS
Year
2013
Pagerank
5.3766157e-05
Overall Rank
8,750 | 39.97%
DOI
10.1145/2463664.2465225

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kejlbergrasmussen_pods13,
        address = {New York, NY, USA},
        series = {{PODS} '13},
        title = {{I/O-Efficient Planar Range Skyline and Attrition Priority Queues}},
        url = {https://dl.acm.org/doi/10.1145/2463664.2465225},
        doi = {10.1145/2463664.2465225},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kejlberg-Rasmussen, Casper and Tao, Yufei and Tsakalidis, Konstantinos and Tsichlas, Kostas and Yoon, Jeonghun},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
11,533 SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization 2022 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers