Efficiency of multidimensional X-tree supernodes in low-dimensional spaces

Andrey O. Trubakov, Evgeniy O. Trubakov

Abstract


Indexing multidimensional or multi-attribute data is an important problem today. Data volumes are growing very fast and it is necessary to use specialized structures and algorithms to index them. However, in the field of research of algorithms for working with multidimensional data there are still many blank spots.

In this paper, we present the results of research on one of the structures used to index multidimensional data - X-tree. This structure has proved itself well in the field of indexing high-dimensional data. However, its behavior for low-dimensional spaces has been poorly studied. We have conducted a number of experiments in spaces of up to 5 dimensions and investigated the effectiveness of this structure compared to the R-tree traditionally used in such areas. The results of the study and conclusions are given in the last chapter of this paper.


Full Text:

PDF (Russian)

References


V.K. Gulakov, A.O. Trubakov, E.O. Trubakov. Structures and algorithms of multidimensional data processing : a monograph. - 2nd ed. - Saint-Petersburg : Lan, 2021. – 356 с. –- ISBN 978-5-8114-7965-8.

Н. Samet. Foundations of multidimensional and metric data structures. – San Francisco : Morgan Kaufmann Publishers Inc., 2006. – 1024 p. – ISBN 0-12-369446-9.

K. Markov, K. Ivanova, I. Mitov, S. arastanev. Advance of the access methods. // International Journal «Information Technologies and Knowledge», Vol.2, 2008.

S. Brakatsoulas, D. Pfoser, Y. Theodoridis. Revisiting R-tree construction principles. // Advances in Databases and Information Systems, 2002. – P. 149-162.

A.O. Trubakov, E.S. Molodkov. Algorithms of building supernodes when indexing multidimensional data in high-dimensional spaces using X-tree // Software Products, Systems and Algorithms. – Tver, 2018. – N 4. – C.37-47.

A. Guttman. R-Trees: A dynamic index structure for spatial searching // In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1984. – P. 47-57.

R.N. Brisaboa, M.R. Luaces, G. Navarro, D. Seco. Space-efficient representations of rectangle datasets supporting orthogonal range querying // Information Systems, Volume 38, Issue 5, 2013. – P. 635-655.

Y. Manolopoulos, A. Nanopoulos, A.N. Papadopoulos, Y. Theodoridis.R-Trees: Theory and Applications. // Springer Publishing Company, Incorporated, 2005. – 194 p. – ISBN:978-1-85233-977-7.

N. Athanasiou, M. Vassilakopoulos, A. Corral, Y. Manolopoulos. Use-based Optimization of Spatial Access Methods // In Proceedings of the 9th International Conference on Management of Digital EcoSystems, New York, 2017. – P. 65–72.

C. Torres, P. Perez-Lantero, G. Gutierrez. Linear separability in spatial databases // Knowl Inf Syst 54, 2018. – P. 287-314.

S. Berchtold, D.A. Keim, H. Kriegel. The X-tree: An Index Structure for High-Dimensional Data. – 1996. – 12 p.

K. Lin, H.V. Jagadish, C. Faloutsos. The TV-Tree: An Index Structure for High-Dimensional Data. – 1994.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162