Arge, Lars^{4}; de Berg, Mark^{3}; Haverkort, Herman^{3}

Editor:

Joe Mitchell, Günter Rote

Affiliations:

^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} unknown^{4} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

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 B or more rectangles in S, the structure answers a rectangle query using �O(sqr{�N/B}+T/B) �memory transfers and a point query using O((N/B)ε) mem�ory transfers for any ε > 0, where 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.

ISBN:

1581139918, 8578715857

Type:

Conference paper

Language:

English

Published in:

Proceedings of 21th Acm Symposium on Computational Geometry, 2005, p. 170-179

Keywords:

I/O-efficiency; Cache-oblivious data structures; Geometric data structures; R-trees