A DYNAMIC INDEXING SCHEME FOR MULTIDIMENSIONAL DATA
Journal Title: Современные информационные технологии и ИТ-образование - Year 2018, Vol 14, Issue 1
Abstract
We present a new dynamic index structure for multidimensional data. The considered index structure is based on an extended grid file concept. Strengths and weaknesses of the grid files were analyzed. Based on that analysis we proposed to strengthen the concept of grid files by considering their stripes as linear hash tables, introducing the concept of chunk and representing the grid file structure as a graph. As a result we significantly reduced the amount of disk operations. Efficient algorithms for storage and access of index directory are proposed, in order to minimize memory usage and lookup operations complexities. Estimations of complexities for these algorithms are presented. A comparison of our approach to support effective grid file structure with other known approaches is presented. This comparison shows effectiveness of suggested metadata storage environment. An estimation of directory size is presented. A prototype to support of our grid file concept has been created and experimentally compared with MongoDB (a renowned NoSQL database). Comparison results show effectiveness of our approach in the cases of given point lookup, lookup by wide ranges and closest objects lookup when considering more than one dimension, and also better memory usage.
Authors and Affiliations
Manuk Manukyan, Grigor Gevorgyan
Keywords
Related Articles
- EP ID EP508781
- DOI 10.25559/SITITO.14.201801.111-125
- Views 84
- Downloads 0
TIME EFFICIENT ALGORITHM FOR THE GENERALIZED0 ENTROPYCALCULATION OF TWO-DIMENSIONS WORDS BY THE METHOD OF A SLIDING WINDOW
In the article we consider methods for calculating the entropy of two-dimensional words of finite length over in finite alphabet, with reference to the problem of self-organization of rod-like particles on a torus. Monit...
VECTORIZATION OF OPERATIONS ON SMALL-DIMENSIONAL MATRICES FOR INTEL XEON PHI KNIGHTS LANDING PROCESSOR
The article is devoted to the vectorization of calculations for Intel Xeon Phi Knights Landing (KNL) processor. Small-dimensional matrices are considered as objects for optimization. These operations are wide common in c...
INTERNET TECHNOLOGIES FOR TRAFFIC AND PEDESTRIAN DATA COLLECTION
The article shows the technology of obtaining initial data on the state and functioning of the city transport system. The technology makes it possible to obtain data on the intensity of any movement: intensity of traffic...
VECTORIZATION OF SMALL-SIZED SPECIAL-TYPE MATRICES MULTIPLICATION USING INSTRUCTIONS AVX-512
Modern software packages for supercomputer calculations require a large amount of computing resources. At the same time there are new hardware architectures that open up new opportunities for program code optimizing. The...
SYNTHESIS OF FAULT ESTIMATION OBSERVER, BASED ON SPECTRAL MIMO H2 OPTIMIZATION
This paper is devoted to slowly varying additive fault detection with implementation of the observer-filter to be designed. Sensitivity of the observer to the external disturbance is to be minimized by the choice of its...