License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-1554
URL: http://drops.dagstuhl.de/opus/volltexte/2005/155/

Arge, Lars ; de Berg, Mark ; Haverkort, Herman J. ; Yi, Ke

The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree

pdf-format:
Dokument 1.pdf (428 KB)


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 R-tree is a general-purpose 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 worst-case query time. We present the Priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query by accessing $O((N/B)^{1-1/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 PR-tree performs similar to the best known heuristics on real-life 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 R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree},
  booktitle =	{Cache-Oblivious and Cache-Aware 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 =	{1862-4405},
  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: R-Trees}
}

Keywords: R-Trees
Seminar: 04301 - Cache-Oblivious and Cache-Aware Algorithms
Issue date: 2005
Date of publication: 01.07.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI