Matematika i Matematičeskoe Modelirovanie (Dec 2021)
Efficiency Analysis of OLAP-data Hypercube Decomposition for Exponential Computational Complexity Methods
Abstract
The paper studies problems of reduction (decomposition) of OLAP-hypercube multidimensional data models. When decomposing large hyper-cubes of multidimensional data into sub-cube components the goal is to increase the computational performance of analytical OLAP systems, which is related to decreasing computational complexity of reduction methods for solving OLAP-data analysis problems with respect to the computational complexity of non-reduction methods, applied to data directly all over the hypercube. The paper formalizes the concepts of reduction and non-reduction methods and gives a definition of the upper bound for the change in the computational complexity of reduction methods in the decomposition of the problem of analyzing multidimensional OLAP-data in comparison with non-reduction methods in the class of exponential degree of computational complexity.The exact values of the upper bound for changing computational complexity are obtained for the hypercube decomposition into two sub-cubes on sets consisting of an even and an odd number of sub-cube structures, and its main properties are given, which are used to determine the decomposition efficiency. A formula for the efficiency of decomposition into two sub-cube structures for reduction of OLAP data analysis problems is obtained, and it is shown that with an increase in the dimension “n” of the lattice specifying the number of sub-cubes in the hypercube data structure, the efficiency of such a decomposition obeys an exponential law with an exponent “n/2”, regardless of the parity “n”. The examples show the possibility to use the values (found) of the upper bound for the change in computational complexity to establish the effectiveness criteria for reduction methods and the expediency of decomposition in specific cases.The paper results can be used in processing and analysis of information arrays of hypercube structures of analytical OLAP systems belonging to the Big-Data or super-large computer systems of multidimensional data.
Keywords