Cache-oblivious planar orthogonal range searching and counting

DOI10.1145/1064092.1064119MaRDI QIDQ5370609zbMATH OpenOpenAlexFDO

Authors Lars Arge, Gerth Stølting Brodal, Rolf Fagerberg, Morten Laustsen

Publication date 20 October 2017

Published in Proceedings of the twenty-first annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1064092.1064119

zbMATH Keywords

cache-obliviousorthogonal range searchingrange countingsemigroup range queries

Mathematics Subject Classification ID

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

Recommendations

• Cache-oblivious data structures for orthogonal range searching
• A general approach for cache-oblivious range reporting and approximate range counting
• 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

Cited in

(14)

• Cache-oblivious R-trees
• Geometric BWT: compressed text indexing via sparse suffixes and range searching
• Cache-oblivious iterated predecessor queries via range coalescing
• Cache-oblivious data structures for orthogonal range searching
• 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
• Orthogonal range searching on the RAM, revisited
• Cache-oblivious range reporting with optimal queries requires superlinear space
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• Cache-oblivious index for approximate string matching
• I/O-efficient data structures for colored range and prefix reporting
• scientific article; zbMATH DE number 7740901 (Why is no real title available?)
• A general approach for cache-oblivious range reporting and approximate range counting

This page was built for publication: Cache-oblivious planar orthogonal range searching and counting

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