Math @ Duke

Publications [#235610] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Danner, A; HollandMinkley, B, Cacheoblivious data structures for orthogonal range searching,
Proceedings of the Annual Symposium on Computational Geometry
(2003),
pp. 237245
(last updated on 2017/12/16)
Abstract: We develop cacheoblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in ℝd lying in a query hyperrectangle. Cacheoblivious data structures are designed to be efficient in arbitrary memory hierarchies. We describe a dynamic linearsize data structure that answers ddimensional queries in O((N/B)11/d+T/B) memory transfers, where B is the block size of any two levels of a multilevel memory hierarchy. A point can be inserted into or deleted from this data structure in O(logB2 N) memory transfers. We also develop a static structure for the twodimensional case that answers queries in O(logB N + T/B) memory transfers using O(N log22 N) space. The analysis of the latter structure requires that B = 22c for some nonnegative integer constant c.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

