Анализ эффективности методов полиномиальной степени сложности при декомпозиции OLAP-кубов многомерных данных

В работе исследуются проблемы редукции (декомпозиции) моделей многомерных данных в виде гиперкубовых 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