scientific article; zbMATH DE number 3907783
[For the entire collection see Zbl 0561.00020.] Our main result is that space 0[N(log N/log log N)\({}^{k-1}]\) suffices for either doing dynamic k-dimensional aggregate orthogonal range queries in time \(O(\log^ kN)\) on a set of N records, or for arbitrary \(\epsilon >O\) to do static aggregate queries in time \(O(\log^{k-1+\epsilon}N)\). This result improves upon the memory space used by slightly more than one dozen previous authors by a factor O[(log log N)\({}^{k-1}]\), and it has applications to rectangle intersection problems, VLSI-design, relational data bases, and queries about the past.
- scientific article; zbMATH DE number 3876615
- Efficient multiway radix search trees
- Efficient tree layout in a multilevel memory hierarchy
- Space efficient algorithms for breadth-depth search
- Reductions in binary search trees
- Space saving by dynamic algebraization based on tree-depth
- Improving time and space efficiency in generalized binary search trees
- A polynomial-time algorithm for memory space reduction
- Limited memory space dilation and reduction algorithms
- Memory-tight reductions
- Efficient multiway radix search trees
- Memory-tight reductions
- Space saving generalization of \(B\)-trees with \(2/3\) utilization
- Space saving by dynamic algebraization based on tree-depth
- ON MULTI-LEVEL k-RANGES FOR RANGE SEARCH
- A linear in memory non-exhaustive algorithm to solve a two-dimensional interval search problem
- New Data Structures for Orthogonal Range Queries
- Space-Time Trade-Offs for Orthogonal Range Queries
- On the performance of orthogonal range queries in multiattribute and doubly chained trees
- On the average performance of orthogonal range search in multidimensional data structures
- Minimizing access pointers into trees and arrays
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3685210)