Cache-oblivious R-trees

Lars Arge, Mark de Berg, Herman Haverkort

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

13 Citaten (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 5 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) e) 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.

Originele taal-2Engels
TitelSCG '05: Proceedings of the twenty-first annual symposium on Computational geometry, June 2005
UitgeverijAssociation for Computing Machinery, Inc
Aantal pagina's10
StatusGepubliceerd - 2005
Evenement21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italië
Duur: 6 jun. 20058 jun. 2005


Congres21st Annual Symposium on Computational Geometry, SCG'05


Duik in de onderzoeksthema's van 'Cache-oblivious R-trees'. Samen vormen ze een unieke vingerafdruk.

Citeer dit