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

DOI10.1016/j.comgeo.2010.04.003zbMath1206.65068OpenAlexW2207300025MaRDI QIDQ991183

Norbert Zeh, Peyman Afshani, 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)

Related Items

Simplex Range Searching and Its Variants: A Review ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Optimal deterministic shallow cuttings for 3-d dominance ranges ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range minima queries with respect to a random permutation, and approximate range counting
• The overlay of minimization diagrams in a randomized incremental construction
• Range searching with efficient hierarchical cuttings
• Fractional cascading. II: Applications
• Reporting points in halfspaces
• Efficient searching with linear constraints
• Efficient splitting and merging algorithms for order decomposable problems.
• Organization and maintenance of large ordered indexes
• Algorithms for three-dimensional dominance searching in linear space.
• Cache-Oblivious Algorithms
• On Dominance Reporting in 3D
• Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting
• Priority Search Trees
• Optimal Search in Planar Subdivisions
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• The priority R-tree
• Low-Dimensional Linear Programming with Violations
• Cache-oblivious data structures for orthogonal range searching
• Cache-oblivious planar orthogonal range searching and counting
• Cache-oblivious R-trees
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Cache-Oblivious B-Trees
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On approximate range counting and depth