scientific article; zbMATH DE number 3907783

From MaRDI portal
Publication:3685210





[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.











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)