Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Cache-Oblivious R-trees

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-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(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.
Original languageEnglish
Title of host publicationProceedings of 21th ACM Symposium on Computational Geometry
EditorsJoe Mitchell, Günter Rote
Number of pages9
PublisherAssociation for Computing Machinery
Publication year2005
ISBN (print)85-7871-585-7
ISBN (Electronic)1-58113-991-8
Publication statusPublished - 2005
EventAnnual Symposium on Computational Geometry - Piza, Italy
Duration: 6 Jun 20058 Jun 2005
Conference number: 21


ConferenceAnnual Symposium on Computational Geometry

    Research areas

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

See relations at Aarhus University Citationformats

ID: 10561010