Cache-oblivious R-trees

L. Arge, M. Berg, de, H.J. Haverkort

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)


We develop a cache-oblivious data structure for storing a set S of N axis-aligned rectangles in the plane, such that all rectangles in S intersecting a query rectangle or point can be found efficiently. Our structure is an axis-aligned bounding-box hierarchy and as such it is the first cache-oblivious R-tree with provable performance guarantees. If no point in the plane is contained in more than a constant number of rectangles in S, we can construct, for any constant e, a structure that answers a rectangle query using memory transfers and a point query using O((N/B) e ) memory transfers, where T is the number of reported rectangles and B is the block size of memory transfers between any two levels of a multilevel memory hierarchy. We also develop a variant of our structure that achieves the same performance on input sets with arbitrary overlap among the rectangles. The rectangle query bound matches the bound of the best known linear-space cache-aware structure.
Original languageEnglish
Pages (from-to)50-68
Issue number1
Publication statusPublished - 2009


Dive into the research topics of 'Cache-oblivious R-trees'. Together they form a unique fingerprint.

Cite this