ABSTRACT
The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R*-tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R*-tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R*-tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R*-tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.
- Gre 89.D Greene 'An implementation and Performance Analysis of Spatial Data Access Methods', Proc 5th I n t Conf on Data Engineering, 606-615, 1989 Google ScholarDigital Library
- Gut 84.A Guttman 'R-trees a dynamic index structure for spatial searching', Proc ACM SIGMOD Int Conf on Management of Data, 47-57, 1984 Google ScholarDigital Library
- Hin 85.K Hlnrlchs 'The grid file system ~mplementatlon and case studies for appl~catxons', D~ssertat~on No 7734, Eldgen6sslsche Technlsche Hochschule (ETH), Zuench, 1985Google Scholar
- Knu 73.D Knuth 'The art of computer programming', Vol 3 sorting and searclung, Addison-Wesley Publ C o , Reading, Mass, 1973 Google ScholarDigital Library
- KSSS 89.H P Krlegel, M Schlwletz, R Schneider, B Seeger 'Performance comparison of point and spatlal access methods', Proc Syrup on the Design and Implementation of Large Spatial Databases', Santa Barbara, 1989, Lecture Notes m Computer Science Google ScholarDigital Library
- NHS 84.J Nlevergelt, H Hmterberger, K C Sevcd< 'The grid file an adaptable, symmetric mult~ey file structure', ACM Trans on Database Systems, Vol 9, 1, 38- 71, 1984 Google ScholarDigital Library
- RL 85.N Roussopoulos, D Lelfker 'Direct spatial search on plctonal databases using packed R-trees', Proc ACM SIGMOD Int Conf on Managment of Data, 17-31, 1985 Google ScholarDigital Library
- SK 88.B Seeger, H P Krlegel 'Design and implementation of spatial access methods', Proc 14th Int Conf on Very Large Databases, 360-371, 1988 Google ScholarDigital Library
- SK 90.B Seeger, HP Krlegel 'The design and implementation of the buddy tree', Computer Science Techmcal Report 3/90, Umverslty of Bremen, submitted for pubhcatlon, 1990Google Scholar
Index Terms
- The R*-tree: an efficient and robust access method for points and rectangles
Recommendations
The R*-tree: an efficient and robust access method for points and rectangles
The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, ...
Temporally enhanced network-constrained (TENC) R-tree
MobiGIS '16: Proceedings of the 5th ACM SIGSPATIAL International Workshop on Mobile Geographic Information SystemsThis paper describes a new Network-constrained Moving objects indexing structure, which extends the state-of-the-art for this kind of data. The indexing structure we propose is called Temporally Enhanced Network-Constrained R-tree (TENC R-tree), which ...
An Improvement of Index Method and Structure Based on R-Tree
CSSE '08: Proceedings of the 2008 International Conference on Computer Science and Software Engineering - Volume 04The spatial query based on conventional R-tree index structure has been processed mostly in two steps, the filter step and the refinement step, and the R-tree’s interior nodes contains only index entries. However, the conventional index structure and ...
Comments