Key words
store the data, optimal container, multidimensional data structures, multidimensional hierarchical containers, hashed multidimensional containers, space-filling curves.
articles
The author:
Potapov D. Published in
№ 2(74)
27 april 2018 year
Rubric: Software development technologies
Rubric: Software development technologies
Existing methods of multidimensional «key-value» storages construction for using in adaptive data storages review
The work is dedicated to methods of multidimensional data storages construction. This questions
is actual because of the growing demand of these containers in different areas. Containers can be used
for working with multidimensional vectors in such fields of knowledge as biology (e. g. to search
for incomplete coincidences in protein and DNA sequences), physics (e. g. computational hydrodynamics,
electromagnetism), economics, political science, medicine and technology, for solving various
tasks in computer graphics, multimedia databases and animation, for working with spatial data.
Hierarchical containers, such as R-like trees (R-tree, R+-tree, R*-tree, X-tree, M-tree, SS-tree, SRtree,
VAMSplit R-tree) and BSP-like trees (BSP-tree, k-d tree, BD-tree, k-d-b tree, hb-tree, LSD-tree,
BIH/SKD-tree, quadtree, octree, VP tree) are analyzed in the paper. The article also reviews hashed
containers such as Gridfile and its modifications (Twin Grid file, Two-layer Grid file, Multilevel Grid
file), EXCELL, R-file, MOLHE and PLOP. Other methods of constructing multidimensional data containers,
such as space-filling curves («row by row» curve, «snake» curve, spiral curve, Cantor curve,
Peano curve, U-index curve, Z-mirror curve, Gray curve and Hilbert curve) and high-dimensional containers
(VA-
File, VA+-File, LPC-File, A-Tree, GC-Tree, RA-Blocks, IQ-tree, SA-tree, A-tree, iDistance)
are examined in this paper. The article also identifies the main fields of application for the analyzed
structures which can be used in adaptive storage implementation.
