EUVIMEDEUVIMED entdecken
Crossref

The priority R-tree

Lars Arge, Mark De Berg, Herman Haverkort, Ke Yi

ACM Transactions on Algorithms · 2008-03 · 4 (1) · 1-30

DOI: 10.1145/1328911.1328920 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 28.03.2008. Verfasst von Lars Arge und 3 weiteren Autor:innen. Die Arbeit wurde bisher 105-mal zitiert (Crossref) und nennt 26 Literaturangaben. Gefördert von: National Science Foundation, Nederlandse Organisatie voor Wetenschappelijk Onderzoek, Army Research Office.

AbstractBibliografische AngabenZitieren

Abstract (Originalsprache)

We present the priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O (( N / B ) 1−1/ d + T / B ) I/Os, where N is the number of d -dimensional (hyper-) rectangles stored in the R-tree, B is the disk block size, and T is the output size. This is provably asymptotically optimal and significantly better than other R-tree variants, where a query may visit all N / B leaves in the tree even when T = 0. We also present an extensive experimental study of the practical performance of the PR-tree using both real-life and synthetic data. This study shows that the PR-tree performs similarly to the best-known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.

Förderung

  • National Science Foundation
  • Nederlandse Organisatie voor Wetenschappelijk Onderzoek
  • Army Research Office
  • Research Grants Council, University Grants Committee, Hong Kong

Zitieren

APA

Arge, L., Berg, M. D., Haverkort, H., & Yi, K. (2008). The priority R-tree. ACM Transactions on Algorithms, 4(1), 1-30. https://doi.org/10.1145/1328911.1328920

Vancouver

Arge L, Berg MD, Haverkort H, Yi K. The priority R-tree. ACM Transactions on Algorithms. 2008;4(1):1-30. doi:10.1145/1328911.1328920

BibTeX
@article{Arge2008,
  author = {Arge, Lars and Berg, Mark De and Haverkort, Herman and Yi, Ke},
  title = {The priority R-tree},
  journal = {ACM Transactions on Algorithms},
  year = {2008},
  volume = {4},
  number = {1},
  pages = {1--30},
  doi = {10.1145/1328911.1328920}
}
Kostenlos starten →