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
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
Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Priority Search Trees
- Title not available (Why is that?)
- Organization and maintenance of large ordered indexes
- Efficient searching with linear constraints
- On the limits of cache-obliviousness
- Cache-oblivious data structures for orthogonal range searching
- Efficient splitting and merging algorithms for order decomposable problems.
- Algorithms for three-dimensional dominance searching in linear space.
- On Dominance Reporting in 3D
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cache-oblivious planar orthogonal range searching and counting
- Cache-oblivious R-trees
- A general approach for cache-oblivious range reporting and approximate range counting
Cited In (2)
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)
