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 ā„¯dlying 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(logB2N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logBN + T/B) memory transfers using O(N log22N) space. The analysis of the latter structure requires that B = 22cfor some non-negative integer constant c.

Duke Authors

Cited Authors

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

Published Date

  • July 28, 2003

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 237 - 245

Citation Source

  • Scopus