НАУКА и ОБРАЗОВАНИЕ

УДК. 004.65

Национальный исследовательский ядерный университет «МИФИ».

aekorotkov@gmail.com

Хранение пространственных данных и обработка пространственных запросов – актуальные задачи для современных баз данных. Эффективность обработки пространственного запроса зависит от нижележащей индексной структуры. R-дерево – одна из самых известных индексных структур, предназначенная для хранения пространственных данных. Существуют различные версии R-деревьев, и одно и наиболее частых их отличий между собой ‑ это алгоритм разделения узла. Некоторые алгоритмы разделения узла для дву- и более мерных R-деревьев содержат одномерное разделение узла в качестве составной части. Проблема разделения узла в одномерном R-дереве может показаться слишком тривиальной, чтобы рассматриваться отдельно, поскольку одномерные интервалы могут быть разделены на базе их сортировки. Однако, если рассмотреть эту проблему детально, существующие алгоритмы для одномерного разделения узла не идеально работают в сложных случаях. В данной работе вводится новый алгоритм разделения узла, основанный на двух сортировках, для одномерного случая, который может обрабатывать подобные сложные случаи лучше. Также вводится алгоритм разделения узла для двух- и более мерных R-деревьев, который основан на предложенном одномерном алгоритме. Тесты выявляют значительно лучшее поведение предложенных алгоритмов по сравнению с известными в случае сильно пересекающихся данных.

Список литературы

1.     C. C. Aggarwal, J. L. Wolf, P. S. Yu, and M. Epelman. The s-tree: An efficient index for multidimensional objects. In Proceedings of the 5^th International Symposium on Advances in Spatial Databases, SSD ’97, pages 350–373, London, UK, 1997. Springer-Verlag.

2.     A. F. Al-Badarneh, Q. Yaseen, and I. Hmeidi. A new enhancement to the r-tree node splitting. J. Information Science, 36(1):3–18, 2010.

3.     C.-H. Ang and T. C. Tan. New linear node splitting algorithm for rtrees. In Proceedings of the 5th International Symposium on Advances in Spatial Databases, SSD ’97, pages 339–349, London, UK, 1997. Springer-Verlag.

4.     R. Bayer and E. McCreight. 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, pages 107–141, New York, NY, USA, 1970. ACM.

5.     N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The r*-tree: an efficient and robust access method for points and rectangles. SIGMODRec., 19:322–331, May 1990.

6.     V. Gaede and O. G¨unther. Multidimensional access methods. ACMComput. Surv., 30:170–231, June 1998.

7.     J. Gong and S. Ke. A new node-split algorithm in r-tree based on spatial clustering. In M. Li, Q. Liang, L. Wang, and Y. Song, editors, FSKD, pages 2081–2085. IEEE, 2010.

8.     D. Greene. An implementation and performance analysis of spatial data access methods. In Proceedings of the Fifth International Conference on Data Engineering, pages 606–615, Washington, DC, USA, 1989. IEEE Computer Society.

9.     A. Guttman. R-trees: a dynamic index structure for spatial searching. SIGMOD Rec., 14:47–57, June 1984.

10.  J. M. Hellerstein, J. F. Naughton, and A. Pfeffer. Generalized search trees for database systems. In Proceedings of the 21th International Conference on Very Large Data Bases, VLDB ’95, pages 562–573, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.

11.  K. Kanth, D. Agrawal, A. Singh, and A. E. Abbadi. Indexing non-uniform spatial data. Database Engineering and ApplicationsSymposium, International, 0:289, 1997.

12.  C. P. Kolovson and M. Stonebraker. Segment indexes: Dynamic indexing techniques for multi-dimensional interval data. In J. Clifford and R. King, editors, SIGMOD Conference, pages 138–147. ACM Press,1991.

13.  K. A. Ross, I. Sitzmann, and P. J. Stuckey. Cost-based unbalanced r-trees. In Proceedings of the 13th International Conference on Scientific and Statistical Database Management, SSDBM ’01, pages 203, Washington, DC, USA, 2001. IEEE Computer Society.

14.  B. Salzberg and V. J. Tsotras. Comparison of access methods for timeevolving data. ACM Comput. Surv., 31:158–221, June 1999.

15.  Y. Tao and D. Papadias. Performance analysis of r*-trees with arbitrary node extents. Tran. Knowl. Data Eng. (TKDE, 16:6–653, 2004.