Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235610] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Arge, L; Danner, A; Holland-Minkley, B, Cache-oblivious data structures for orthogonal range searching, Proceedings of the Annual Symposium on Computational Geometry (2003), pp. 237-245
    (last updated on 2018/07/18)

    We develop cache-oblivious 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 hyper-rectangle. Cache-oblivious data structures are designed to be efficient in arbitrary memory hierarchies. We describe a dynamic linear-size data structure that answers d-dimensional queries in O((N/B)1-1/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 two-dimensional 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 non-negative integer constant c.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320