A general approach for cache-oblivious range reporting and approximate range counting

DOI10.1016/J.COMGEO.2010.04.003MaRDI QIDQ991183zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Norbert Zeh, Chris H. Hamilton

Publication date 2 September 2010

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2010.04.003

zbMATH Keywords

data structuresrange searchingrange countingrange reportingcache-obliviousnessmemory hierarchiesoptimal query boundworst-case query time

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• 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
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Approximate range counting revisited
• Approximate range counting revisited
• Towards tight lower bounds for range reporting on the RAM
• Cache-oblivious planar orthogonal range searching and counting
• scientific article; zbMATH DE number 2081109
• Cache-oblivious data structures for orthogonal range searching

Cites work

• scientific article; zbMATH DE number 5506205 (Why is no real title available?)
• scientific article; zbMATH DE number 1195522 (Why is no real title available?)
• scientific article; zbMATH DE number 2086622 (Why is no real title available?)
• scientific article; zbMATH DE number 2119642 (Why is no real title available?)
• scientific article; zbMATH DE number 1424325 (Why is no real title available?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Algorithms for three-dimensional dominance searching in linear space.
• Cache-Oblivious B-Trees
• Cache-oblivious R-trees
• Cache-oblivious algorithms
• Cache-oblivious data structures for orthogonal range searching
• Cache-oblivious planar orthogonal range searching and counting
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Computational geometry. Algorithms and applications.
• Efficient searching with linear constraints
• Efficient splitting and merging algorithms for order decomposable problems.
• Fractional cascading. II: Applications
• Introduction to algorithms
• Low-Dimensional Linear Programming with Violations
• On Dominance Reporting in 3D
• On approximate range counting and depth
• On approximating the depth and related problems
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Optimal Search in Planar Subdivisions
• Optimal halfspace range reporting in three dimensions
• Organization and maintenance of large ordered indexes
• Priority Search Trees
• Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting
• Range minima queries with respect to a random permutation, and approximate range counting
• Range searching with efficient hierarchical cuttings
• Reporting points in halfspaces
• The overlay of minimization diagrams in a randomized incremental construction
• The priority R-tree: a practically efficient and worst-case optimal R-tree
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications

Cited in

(10)

• Independent range sampling, revisited
• Cache-oblivious planar orthogonal range searching and counting
• Cache-oblivious range reporting with optimal queries requires superlinear space
• A general approach for cache-oblivious range reporting and approximate range counting
• Optimal deterministic shallow cuttings for 3-d dominance ranges
• Improved space bounds for cache-oblivious range reporting
• Cache-oblivious range reporting with optimal queries requires superlinear space
• scientific article; zbMATH DE number 2086641 (Why is no real title available?)
• Simplex Range Searching and Its Variants: A Review
• Approximating the k-Level in Three-Dimensional Plane Arrangements

This page was built for publication: A general approach for cache-oblivious range reporting and approximate range counting

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