Математика и математическое моделирование. 2021; : 29-45
Анализ эффективности декомпозиции OLAP-гиперкубов данных для методов экспоненциальной вычислительной сложности
https://doi.org/10.24108/mathm.0321.0000258Аннотация
Исследуются проблемы редукции (декомпозиции) моделей многомерных данных в виде гиперкубовых OLAP-структур. При декомпозиции больших гиперкубов многомерных данных на подкубовые компоненты преследуется цель повышения вычислительной производительности аналитических OLAP-систем, которая связана с уменьшением вычислительной сложности редукционных методов решения задач анализа OLAP-данных по отношению к вычислительной сложности нередукционных методов, применяемых к данным непосредственно на всем гиперкубе. В работе формализованы понятия редукционных и нередукционных методов и дано определение верхней границы изменения вычислительной сложности редукционных методов при декомпозиции задачи анализа многомерных OLAP–данных по сравнению с нередукционными методами в классе экспоненциальной степени вычислительной сложности. Получены точные значения верхней границы изменения вычислительной сложности при декомпозиции гиперкуба на два подкуба на множествах, состоящих из четного и нечетного числа подкубовых структур, и приведены ее основные свойства, которые используются для определения эффективности декомпозиции. Получена формула эффективности декомпозиции при редукции задач анализа OLAP-данных на две подкубовые структуры, и показано, что с увеличением размерности n решетки, задающей количество подкубов в структуре данных гиперкуба, эффективность такой декомпозиции подчиняется экспоненциальному закону с показателем n/2 в независимости от четности n. На примерах показана возможность применения найденных значений верхней границы изменения вычислительной сложности для установления критериев эффективности редукционных методов и целесообразности декомпозиции в конкретных случаях.
Результаты работы могут быть использованы при обработке и анализе массивов информации гиперкубовых структур аналитических OLAP-систем, относящихся к классу BigData, или сверхбольших компьютерных систем многомерных данных.
Список литературы
1. Agarwal S., Agrawal R., Deshpande P.M., Gupta A., Naughton J.F., Ramakrishnan R., Sarawagi S. On the computation of multidimensional aggregates // 22nd Intern conf. on very large databases: VLDB’96 (Mumbai (Bombay), India, September 3-6, 1996): Proc. San Francisco: Morgan Kaufmann Publ. Inc., 1996. Pp. 506– 521.
2. Макаров И.М., Рахманкулов В.З., Ахрем А.А., Ровкин И.О. Исследование свойств гиперкубовых структур в OLAP–системах // Информационные технологии и вычислительные системы. 2005. № 2. С. 4–9.
3. Ахрем А.А., Рахманкулов В.З., Южанин К.В. О сложности редукции моделей многомерных данных // Искусственный интеллект и принятие решений. 2016. № 4. С. 79-85.
4. Ахрем А.А., Рахманкулов В.З., Южанин К.В. Декомпозиционные методы анализа многомерных данных // Системные исследования. Методологические проблемы: Ежегодник 2015-2018. М., 2018. С. 88–97.
5. Ахрем А.А., Носов А.П., Рахманкулов В.З., Южанин К.В. Вычислительная производительность методов редукции гиперкубов многомерных данных аналитических OLAP–систем // Искусственный̆ интеллект и принятие решений. 2019. № 4. С. 23–28. DOI: 10.14357/201718594190403
6. Носов А.П., Ахрем А.А., Рахманкулов В.З., Южанин К.В. Анализ вычислительной̆ сложности методов декомпозиции OLAP–гиперкубов многомерных данных // Математика и математическое моделирование. 2020. № 4. С. 52–64. DOI: 10.24108/mathm.0420.0000221
7. Чубукова И.А. Data Mining: учеб. пособие. 2-е изд. М.: Бином. Лаборатория знаний, 2008. 382 c.
8. Ахрем А.А., Носов А.П., Рахманкулов В.З. Анализ эффективности методов полиномиальной̆ степени сложности при декомпозиции OLAP–кубов многомерных данных // Математика и математическое моделирование. 2021. № 1. С. 27–42. DOI: 10.24108/mathm.0121.0000244
9. Гуров С.И. Булевы алгебры, упорядоченные множества, решётки. 2-е изд. М.: URSS; Либроком, 2013. 352 c.
10. Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы: общий̆ подход: пер. с англ. М.: БИНОМ. Лаборатория знаний, 2006. 406 c.
Mathematics and Mathematical Modeling. 2021; : 29-45
Efficiency Analysis of OLAP-data Hypercube Decomposition for Exponential Computational Complexity Methods
https://doi.org/10.24108/mathm.0321.0000258Abstract
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.
References
1. Agarwal S., Agrawal R., Deshpande P.M., Gupta A., Naughton J.F., Ramakrishnan R., Sarawagi S. On the computation of multidimensional aggregates // 22nd Intern conf. on very large databases: VLDB’96 (Mumbai (Bombay), India, September 3-6, 1996): Proc. San Francisco: Morgan Kaufmann Publ. Inc., 1996. Pp. 506– 521.
2. Makarov I.M., Rakhmankulov V.Z., Akhrem A.A., Rovkin I.O. Issledovanie svoistv giperkubovykh struktur v OLAP–sistemakh // Informatsionnye tekhnologii i vychislitel'nye sistemy. 2005. № 2. S. 4–9.
3. Akhrem A.A., Rakhmankulov V.Z., Yuzhanin K.V. O slozhnosti reduktsii modelei mnogomernykh dannykh // Iskusstvennyi intellekt i prinyatie reshenii. 2016. № 4. S. 79-85.
4. Akhrem A.A., Rakhmankulov V.Z., Yuzhanin K.V. Dekompozitsionnye metody analiza mnogomernykh dannykh // Sistemnye issledovaniya. Metodologicheskie problemy: Ezhegodnik 2015-2018. M., 2018. S. 88–97.
5. Akhrem A.A., Nosov A.P., Rakhmankulov V.Z., Yuzhanin K.V. Vychislitel'naya proizvoditel'nost' metodov reduktsii giperkubov mnogomernykh dannykh analiticheskikh OLAP–sistem // Iskusstvennyĭ intellekt i prinyatie resheniĭ. 2019. № 4. S. 23–28. DOI: 10.14357/201718594190403
6. Nosov A.P., Akhrem A.A., Rakhmankulov V.Z., Yuzhanin K.V. Analiz vychislitel'noĭ slozhnosti metodov dekompozitsii OLAP–giperkubov mnogomernykh dannykh // Matematika i matematicheskoe modelirovanie. 2020. № 4. S. 52–64. DOI: 10.24108/mathm.0420.0000221
7. Chubukova I.A. Data Mining: ucheb. posobie. 2-e izd. M.: Binom. Laboratoriya znaniĭ, 2008. 382 c.
8. Akhrem A.A., Nosov A.P., Rakhmankulov V.Z. Analiz effektivnosti metodov polinomial'noĭ stepeni slozhnosti pri dekompozitsii OLAP–kubov mnogomernykh dannykh // Matematika i matematicheskoe modelirovanie. 2021. № 1. S. 27–42. DOI: 10.24108/mathm.0121.0000244
9. Gurov S.I. Bulevy algebry, uporyadochennye mnozhestva, reshetki. 2-e izd. M.: URSS; Librokom, 2013. 352 c.
10. Miller R., Bokser L. Posledovatel'nye i parallel'nye algoritmy: obshchiĭ podkhod: per. s angl. M.: BINOM. Laboratoriya znaniĭ, 2006. 406 c.
