Computational Complexity Analysis of Decomposition Methods of OLAP Hyper-cubes of Multidimensional Data

Abstract

The paper investigates the problems of reduction (decomposition) of multidimensional data models in the form of hypercube OLAP structures. OLAP data processing does not allow changes in the dimension of space. With the increase in data volumes, the productivity of computing cubic structures decreases. Methods for reducing large data cubes to sub-cubes with smaller volumes can solve the problem of reducing computing performance.The reduction problems are considered for cases when the cube lattice has already determined criteria aggregation, and the cube decomposition into smaller cubes is needed to reduce the computation time of the full lattice when dynamically changing data in the cube.The objective of the paper is to find conditions for reducing the computational complexity of solving data analysis problems by reduction methods, to obtain exact quantitative boundaries for reducing the complexity of decomposition methods from the class of polynomial degrees of complexity, to establish the nature of the dependence of computational performance on the structural properties of a hypercube, and to determine the quantitative boundaries of computational performance for solving decomposition problems of data aggregation .The study of the computational complexity of decomposition methods for the analysis of multidimensional hyper-cubes of polynomial-logarithmic and polynomial degrees of complexity is carried out. An exact upper limit is found for reducing the complexity of decomposition methods for analyzing the initial OLAP - data hypercube with respect to non-decomposition ones and based on them criteria are proved for the effective application of reduction methods for analyzing hypercube structures in comparison with traditional non-reduction methods.Examples of decomposition methods of cube structures are presented, both reducing and increasing computational complexity in comparison with calculations using the full model.The results obtained can be used in processing and analysis of information arrays of hypercube structures of analytical OLAP-systems belonging to the BigData class, or ultra-large computer multidimensional data systems.

Keywords

• olap–systems
• hypercube of multidimensional data
• reduction methods
• computational complexity
• computational performance