A general approach for cache-oblivious range reporting and approximate range counting
From MaRDI portal
Publication:991183
DOI10.1016/j.comgeo.2010.04.003zbMath1206.65068MaRDI 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
data structures; range searching; range counting; range reporting; cache-obliviousness; memory hierarchies; optimal query bound; worst-case query time
65D18: Numerical aspects of computer graphics, image analysis, and computational geometry
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
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