STR: A Simple and Efficient Algorithm for R-Tree Packing
by Leutenegger, Scott T., Edgington, Jeffrey M., Lopez, Mario A
Uploaded at 2026-11-03 03:05
- Language
- English
- Published
- February 1, 1997
- Submitted by
- gwilliam
- Downloads
- 7,889
Report DMCA
This document was submitted by our user and they confirm that they have the consent to share it. Assuming that you are writer or own the copyright of this document, report to us by using this DMCA report button.
Loading preview... Please wait.
In this paper we present the results from an extensive comparison study of three R-tree packing algorithms, including a new easy to implement algorithm. The algorithms are evaluated using both synthetic and actual data from various application domains including VLSI design, GIS (tiger), and computational fluid dynamics. Our studies also consider the impact that various degrees of buffering have on query performance. Experimental results indicate that none of the algorithms is best for all types of data. In general, our new algorithm requires up to 50 fewer disk accesses than the best previously proposed algorithm for point and region queries on uniformly distributed or mildly skewed point and region data, and approximately the same for highly skewed point and region data.