Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Cache-Oblivious R-trees

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Lars Arge
  • Mark de Berg, Netherlands
  • Herman Haverkort, Netherlands
  • Department of Computer Science
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(√N/B + T/B) memory transfers and a point query using O((N/B)ε) memory 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.
Original languageEnglish
JournalAlgorithmica
Volume53
Issue1
Pages (from-to)50-68
Number of pages18
ISSN0178-4617
DOIs
Publication statusPublished - 2009

    Research areas

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

See relations at Aarhus University Citationformats

ID: 6215932