A new double sorting-based node splitting algorithm for R-tree
Tóm tắt
A storing of spatial data and processing of spatial queries are important tasks for modern data-bases. The execution efficiency of spatial query depends on underlying index structure. R-tree is a well-known spatial index structure. Currently there exist various versions of R-tree, and one of the most common variations between them is node splitting algorithm. The problem of node splitting in one-dimensional R-tree may seem to be too trivial to be considered separately. One-dimensional intervals can be split on the base of their sorting. Some of the node splitting algorithms for R-tree with two or more dimensions comprise one-dimensional split as their part. However, under detailed consideration, existing algorithms for one-dimensional split do not perform ideally in some complicated cases. This paper introduces a novel one-dimensional node splitting algorithm based on two sortings that can handle such complicated cases better. Also this paper introduces node splitting algorithm for R-tree with two or more dimensions that is based on the one-dimensional algorithm mentioned above. The tests show significantly better behavior of the proposed algorithms in the case of highly overlapping data.
Tài liệu tham khảo
Al-Badarneh, A.F., Yaseen, Q., and Hmeidi, I., A New Enhancement to the R-Tree Node Splitting, J. Inform. Sci., 2010, vol. 36, no. 1, pp. 3–18.
Ang, C.-H. and Tan, T.C., New Linear Node Splitting Algorithm for R-Trees, in Proceedings of the 5th International Symposium on Advances in Spatial Databases, SSD-97, UK, London: Springer-Verlag, 1997, pp. 339–349.
Bayer, R. and McCreight, E., Organization and Maintenance of Large Ordered Indices, in Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, SIGFIDET-70, USA, NY, New York: ACM, 1970, pp. 107–141.
Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B., The R*-Tree: an Efficient and Robust Access Method for Points and Rectangles, SIGMOD Rec., 1990, vol. 19, pp. 322–331.
Gaede, V. and GBünther, O., Multidimensional Access Methods, ACM Comput. Surv., 1998, vol. 30, pp. 170–231.
Greene, D., An Implementation and Performance Analysis of Spatial Data Access Methods, in Proceedings of the Fifth International Conference on Data Engineering, USA, DC, Washington: IEEE Computer Society, 1989, pp. 606–615.
Guttman, A., R-Trees: a Dynamic Index Structure for Spatial Searching, SIGMOD Rec., 1984, vol. 14, pp. 47–57.
Hellerstein, J.M., Naughton, J.F., and Pfeffer, A., Generalized Search Trees for Database Systems, in Proceedings of the 21th International Conference on Very Large Data Bases, VLDB-95, USA, CA, San Francisco: Morgan Kaufmann Publishers Inc., 1995, pp. 562–573.
Kanth, K., Agrawal, D., Singh, A., and Abbadi, A.E., Indexing Non-Uniform Spatial Data, Database Engineering and Applications Symposium, International, 1997, p. 289.
Kolovson, C.P. and Stonebraker, M., Segment Indexes: Dynamic Indexing Techniques for Multidimensional Interval Data, Clifford, J. and King, R., Ed., SIGMOD Conference, ACM Press, 1991, pp. 138–147.
Salzberg, B. and Tsotras, V.J., Comparison of Access Methods for Time-Evolving Data, ACM Comput. Surv., 1999, vol. 31, pp. 158–221.
Tao, Y. and Papadias, D., Performance Analysis of R*-Trees with Arbitrary Node Extents, Tran. Knowl. Data Eng. (TKDE), 2004, vol. 16. pp. 6–653.