Cache-oblivious range reporting with optimal queries requires superlinear space

DOI10.1007/S00454-011-9347-7zbMATH Open1215.68103OpenAlexW4239171964MaRDI QIDQ540448FDOQ540448

Authors Peyman Afshani, Norbert Zeh, Chris H. Hamilton

Publication date 3 June 2011

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-011-9347-7

zbMATH Keywords

lower boundrange reportingcache-obliviousness

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Cache-oblivious range reporting with optimal queries requires superlinear space
• Improved space bounds for cache-oblivious range reporting
• A general approach for cache-oblivious range reporting and approximate range counting
• A general approach for cache-oblivious range reporting and approximate range counting
• Cache-oblivious planar orthogonal range searching and counting

Cites work

• scientific article; zbMATH DE number 5506205 (Why is no real title available?)
• scientific article; zbMATH DE number 1256735 (Why is no real title available?)
• scientific article; zbMATH DE number 1424325 (Why is no real title available?)
• A general approach for cache-oblivious range reporting and approximate range counting
• Algorithms for three-dimensional dominance searching in linear space.
• Cache-oblivious R-trees
• Cache-oblivious data structures for orthogonal range searching
• Cache-oblivious planar orthogonal range searching and counting
• Efficient searching with linear constraints
• Efficient splitting and merging algorithms for order decomposable problems.
• On Dominance Reporting in 3D
• On the limits of cache-obliviousness
• Optimal halfspace range reporting in three dimensions
• Organization and maintenance of large ordered indexes
• Priority Search Trees
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions

Cited in

(5)

• Cache-oblivious hashing
• A general approach for cache-oblivious range reporting and approximate range counting
• Improved space bounds for cache-oblivious range reporting
• Cache-oblivious range reporting with optimal queries requires superlinear space
• A general approach for cache-oblivious range reporting and approximate range counting

This page was built for publication: Cache-oblivious range reporting with optimal queries requires superlinear space

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