Cache-oblivious data structures for orthogonal range searching


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Arge, L; Danner, A; Holland-Minkley, B

Published Date

  • January 1, 2003

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 237 - 245

Digital Object Identifier (DOI)

  • 10.1145/777825.777828

Citation Source

  • Scopus