Математика и математическое моделирование. 2021; : 27-42
Анализ эффективности методов полиномиальной степени сложности при декомпозиции OLAP-кубов многомерных данных
https://doi.org/10.24108/mathm.0121.0000244Аннотация
В работе исследуются проблемы редукции (декомпозиции) моделей многомерных данных в виде гиперкубовых OLAP-структур. Рассматривается случай, когда структура данных определяется решеткой, разбивающей гиперкуб на нечетное количество подкубов, и декомпозиция гиперкуба осуществляется на этом множестве подкубовых структур. Установлена точная верхняя граница увеличения вычислительной производительности методов анализа OLAP-данных на подкубах, определяющая эффективность декомпозиционного подхода по сравнению с анализом OLAP-данных на полном нередуцированном гиперкубе. Проведено сравнение эффективности декомпозиции гиперкуба на два подкуба на множествах, состоящих из четного и нечетного числа подкубовых структур и показано, что при большом дроблении данных для методов полиномиальной степени сложности эффективность декомпозиции практически не зависит от этого фактора и растет с ростом степени сложности применяемых методов.
При исследовании математическими методами декомпозиции (редукции) больших гиперкубов многомерных данных аналитических OLAP-систем на подкубовые компоненты ищутся условия уменьшения вычислительной сложности методов решения задач анализа OLAP-гиперкубов при декомпозиции данных по сравнению с применением этих методов к анализу больших массивов информации, накапливаемых непосредственно в гиперкубах многомерных OLAP-данных для установления критериев уменьшения или увеличения вычислительной производительности при применении методов на подкубовых компонентах (редукционные методы) по сравнению с применением этих методов на гиперкубе (нередукционные или традиционные методы) в зависимости от классов той или иной степеней сложности рассматриваемых методов.
В статье получена точная количественная оценка уменьшения вычислительной сложности редукционных методов анализа OLAP-кубов по сравнению с нередукционными методами в ситуации, когда данные методы имеют полиномиальную степень сложности, а решетка исходного гиперкуба данных состоит из нечетного числа подкубов.
Список литературы
1. Андрейчиков А.В., Андрейчикова О.Н. Интеллектуальные информационные системы: учеб. М.: Финансы и статистика, 2004. 422 с.
2. Ноженкова Л.Ф., Шайдуров В.В. OLAP-технологии оперативной информационно-аналитической поддержки организационного управления // Информационные технологии и вычислительные системы. 2010. № 2. С. 15–27.
3. Замятин А.В. Введение в интеллектуальный анализ данных: учеб. пособие. Томск: Изд-во Томского гос. ун-та, 2016. 120 с.
4. Вайнштейн Ю.В. Планирование медицинской помощи с применением аналитических OLAP-моделей // Вестник Томского гос. ун-та. Сер. «Математика. Кибернетика. Информатика». 2004. Приложение № 8470, 9(II). С. 16–22.
5. Петровский А.Б., Ройзензон Г.В. Снижение размерности признакового пространства в задачах многокритериальной классификации: стратификация кортежей // 11-я национ. конф. по искусственному интеллекту с международным участием: КИИ-2008 (г. Дубна, Россия, 29 сентября – 3 октября 2008 г.): Тр. М.: ЛЕНАНД, 2008. Т. 2. С. 262–270.
6. Петровский А.Б., Лобанов В.Н. Многокритериальный выбор в пространстве признаков большой размерности: мультимедийная технология ПАКС-М // Искусственный интеллект и принятие решений. 2014. № 3. С. 92–104.
7. Agarwal S., Agrawal R., Deshpande P.M., Gupta A., Naughton J.F., Ramakrishnan R., Sarawagi S. On the computation of multidimensional aggregates // Materialized views: techniques, implementations and applications / Ed. by A. Gupta. Camb.: MIT Press, 1999. Pp. 506–521. DOI: 10.7551/mitpress/4472.003.0030
8. Чубукова И.А. Data Mining: учеб. пособие. 2-е изд. М.: БИНОМ. Лаборатория знаний, 2008. 382 c.
9. Макаров И.М., Рахманкулов В.З., Ахрем А.А., Ровкин И.О. Исследование свойств гиперкубовых структур в OLAP-системах // Информационные технологии и вычислительные системы. 2005. № 2. С. 4–9.
10. Akhrem A.A., Rakhmankulov V.Z., Yuzhanin K.V. On the complexity of the reduction of multidimensional data models // Scientific and Technical Information Processing. 2017. Vol. 44. No. 6. Pp. 406–411. DOI: 10.3103/S0147688217060028
11. Ахрем А.А., Носов А.П., Рахманкулов В.З., Южанин К.В. Вычислительная производительность методов редукции гиперкубов многомерных данных аналитических OLAP-систем // Искусственный интеллект и принятие решений. 2019. № 4. С. 23–28. DOI: 10.14357/20718594190403
12. Носов А.П., Ахрем А.А., Рахманкулов В.З., Южанин К.В. Анализ вычислительной сложности методов декомпозиции OLAP-гиперкубов многомерных данных // Математика и математическое моделирование. 2020. № 4. С. 52-64. DOI: 10.24108/mathm.0420.0000221
Mathematics and Mathematical Modeling. 2021; : 27-42
Analysing Efficiency Methods of Polynomial Complexity Degree in Multidimensional OLAP Cube Data Decomposition
https://doi.org/10.24108/mathm.0121.0000244Abstract
The article investigates the problems of reduction (decomposition) of multidimensional data models in terms of hypercube OLAP-structures. Describes the case when a data structure is defined by the array that slices and dices the hypercube into the odd number of subcubes, and this set of subcube structures becomes decomposed. Defines an exact upper bound for increasing a computational performance of methods to analyze OLAP-data on subcubes, which determines the decomposition approach efficiency in comparison with the OLAP-data analysis on a complete unreduced hypercube. A compared efficiency of the hypercube decomposition into two subcubes on the sets consisting of the even and odd number of subcube structures has shown that with considerable data partitioning for methods of a polynomial complexity degree the decomposition efficiency essentially is independent on this factor and rises with increasing complexity degree of methods applied.
When using the mathematical methods to study decomposition (reduction) of large hyper-cubes of multidimensional data of analytical OLAP systems into subcube components, there is a need to find conditions for minimising the computational complexity of methods to solve the problems of the OLAP hyper-cube analysis during data decomposition in comparison with using these methods for analyzing large amounts of information that is accumulated directly in the hyper-cubes of multidimensional OLAP-data to establish the criteria for decreasing or increasing computational performance when applying methods on the subcube components (reduction methods) as compared to applying these methods on a hypercube (non-reduction or traditional methods), depending on one or another degree of complexity of complex methods.
The article provides an accurate quantitative estimate of decreasing computational complexity of reduction methods for analyzing OLAP-cubes as compared to the non-reduction methods in the case when said methods have the polynomial complexity and the original hypercube array of data comprises the odd number of subcubes.
References
1. Andreichikov A.V., Andreichikova O.N. Intellektual'nye informatsionnye sistemy: ucheb. M.: Finansy i statistika, 2004. 422 s.
2. Nozhenkova L.F., Shaidurov V.V. OLAP-tekhnologii operativnoi informatsionno-analiticheskoi podderzhki organizatsionnogo upravleniya // Informatsionnye tekhnologii i vychislitel'nye sistemy. 2010. № 2. S. 15–27.
3. Zamyatin A.V. Vvedenie v intellektual'nyi analiz dannykh: ucheb. posobie. Tomsk: Izd-vo Tomskogo gos. un-ta, 2016. 120 s.
4. Vainshtein Yu.V. Planirovanie meditsinskoi pomoshchi s primeneniem analiticheskikh OLAP-modelei // Vestnik Tomskogo gos. un-ta. Ser. «Matematika. Kibernetika. Informatika». 2004. Prilozhenie № 8470, 9(II). S. 16–22.
5. Petrovskii A.B., Roizenzon G.V. Snizhenie razmernosti priznakovogo prostranstva v zadachakh mnogokriterial'noi klassifikatsii: stratifikatsiya kortezhei // 11-ya natsion. konf. po iskusstvennomu intellektu s mezhdunarodnym uchastiem: KII-2008 (g. Dubna, Rossiya, 29 sentyabrya – 3 oktyabrya 2008 g.): Tr. M.: LENAND, 2008. T. 2. S. 262–270.
6. Petrovskii A.B., Lobanov V.N. Mnogokriterial'nyi vybor v prostranstve priznakov bol'shoi razmernosti: mul'timediinaya tekhnologiya PAKS-M // Iskusstvennyi intellekt i prinyatie reshenii. 2014. № 3. S. 92–104.
7. Agarwal S., Agrawal R., Deshpande P.M., Gupta A., Naughton J.F., Ramakrishnan R., Sarawagi S. On the computation of multidimensional aggregates // Materialized views: techniques, implementations and applications / Ed. by A. Gupta. Camb.: MIT Press, 1999. Pp. 506–521. DOI: 10.7551/mitpress/4472.003.0030
8. Chubukova I.A. Data Mining: ucheb. posobie. 2-e izd. M.: BINOM. Laboratoriya znanii, 2008. 382 c.
9. 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.
10. Akhrem A.A., Rakhmankulov V.Z., Yuzhanin K.V. On the complexity of the reduction of multidimensional data models // Scientific and Technical Information Processing. 2017. Vol. 44. No. 6. Pp. 406–411. DOI: 10.3103/S0147688217060028
11. Akhrem A.A., Nosov A.P., Rakhmankulov V.Z., Yuzhanin K.V. Vychislitel'naya proizvoditel'nost' metodov reduktsii giperkubov mnogomernykh dannykh analiticheskikh OLAP-sistem // Iskusstvennyi intellekt i prinyatie reshenii. 2019. № 4. S. 23–28. DOI: 10.14357/20718594190403
12. Nosov A.P., Akhrem A.A., Rakhmankulov V.Z., Yuzhanin K.V. Analiz vychislitel'noi slozhnosti metodov dekompozitsii OLAP-giperkubov mnogomernykh dannykh // Matematika i matematicheskoe modelirovanie. 2020. № 4. S. 52-64. DOI: 10.24108/mathm.0420.0000221
