STR: a simple and efficient algorithm for R-tree packing
Scott T. Leutenegger, Mario Alberto Lopez, Jeffrey Edgington · Proceedings - International Conference on Data Engineering · 2002
Presents the results from an extensive comparison study of three R-tree packing algorithms: the Hilbert and nearest-X packing algorithms, and an algorithm which is very simple to implement, called the STR (Sort-Tile-Recursive) algorithm. The algorithms are evaluated using both synthetic and actual data from various application domains including VLSI design, GIS (Tiger files), 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 as 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.
Cited by 487 works. doi:10.1109/icde.1997.582015
Authors
References
- R-trees
- The R*-tree: an efficient and robust access method for points and rectangles
- Direct spatial search on pictorial databases using packed R-trees
- On packing R-trees
- Hilbert R-tree: An Improved R-tree using Fractals
- Fractals for secondary key retrieval
- Filtering Search: A New Approach to Query-Answering
- An Advancing Front Delaunay Triangulation Algorithm Designed for Robustness
- Time- and space-optimality in B-trees
- A simple analysis of the LRU buffer policy and its relationship to buffer warm-up transient