Abstract
The query efficiency of a data structure that stores a set of objects, can normally be assessed by analysing the number of objects, pointers etc. looked at when answering a query. However, if the data structure is too big to fit in main memory, data may need to be fetched from disk. In that case, the query efficiency is easily dominated by moving the disk head to the correct locations, rather than by reading the data itself.
To reduce the number of disk accesses, once can group the data into blocks, and strive to bound the number of different blocks accessed rather than the number of individual data objects read. An Rtree is a generalpurpose data structur that stores a hierarchical grouping of geometric objects into blocks. Many heuristics have been designed to determine which objects should be grouped together, but none of these heuristics could give a guarantee on the resulting worstcase query time.
We present the Priority Rtree, or PRtree, which is the first Rtree variant that always answers a window query by accessing $O((N/B)^{11/d} + T/B)$ blocks, where $N$ is the number of $d$dimensional objects stored, $B$ is the number of objects per block, and $T$ is the number of objects whose bounding boxes intersect the query window. This is provably asymptotically optimal. Experiments show that the PRtree performs similar to the best known heuristics on reallife and relatively nicely distributed data, but outperforms them significantly on more extreme data.
BibTeX  Entry
@InProceedings{arge_et_al:DSP:2005:155,
author = {Lars Arge and Mark de Berg and Herman J. Haverkort and Ke Yi},
title = {The Priority RTree: A Practically Efficient and WorstCaseOptimal RTree},
booktitle = {CacheOblivious and CacheAware Algorithms},
year = {2005},
editor = {Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
number = {04301},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2005/155},
annote = {Keywords: RTrees}
}
Keywords: 

RTrees 
Seminar: 

04301  CacheOblivious and CacheAware Algorithms 
Issue Date: 

2005 
Date of publication: 

01.07.2005 