Preview

Математика и математическое моделирование

Расширенный поиск

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

https://doi.org/10.24108/mathm.0420.0000221

Полный текст:

Аннотация

В работе исследуются проблемы редукции (декомпозиции) моделей многомерных данных в виде гиперкубовых OLAP-структур. OLAP обработка данных не допускает изменения размерности пространства. С увеличением объемов данных падает производительность вычислений кубовых структур. Методы редукции больших кубов данных на подкубы с меньшими объемами позволяют решать проблему снижения производительности вычислений.

Рассматриваются задачи редукции для случаев, когда агрегирование критериев уже определено решёткой куба, а декомпозиция куба на меньшие по размерности кубы нужна для снижения времени вычисления полной решётки при динамическом изменении данных в кубе.

Цель работы состоит в нахождении условий уменьшения вычислительной сложности решения задач анализа данных редукционными методами, получении точных количественных границ уменьшения сложности декомпозиционных методов из класса полиномиальной степеней сложности, установлении характера зависимости вычислительной производительности от структурных свойств гиперкуба и определении количественных границ вычислительной производительности решения декомпозиционных задач агрегирования данных.

Проведено исследование вычислительной сложности декомпозиционных методов анализа многомерных гиперкубов полиномиально-логарифмической и полиномиальной степеней сложности. Найдена точная верхняя граница уменьшения сложности декомпозиционных методов анализа исходного OLAP--гиперкуба данных по отношению к недекомпозиционным, и на их основе доказаны критерии эффективного применения редукционных методов анализа гиперкубовых структур по сравнению с традиционными нередукционными методами.

Приведены примеры методов декомпозиции кубовых структур, как уменьшающих, так и увеличивающих вычислительную сложность по сравнению с вычислениями по полной модели.

Результаты работы могут быть использованы при обработке и анализе массивов информации гиперкубовых структур аналитических OLAP-систем, относящихся к классу BigData, или сверхбольших компьютерных систем многомерных данных.

Об авторах

А. П. Носов
Федеральный исследовательский центр «Информатика и управление» РАН, Москва
Россия

Носов Алексей Петрович

старший научный сотрудник, отдел 81



А. А. Ахрем
Федеральный исследовательский центр «Информатика и управление» РАН, Москва
Россия

Ахрем Андрей Афанасьевич

главный специалист, отдел 82



В. З. Рахманкулов
Федеральный исследовательский центр «Информатика и управление» РАН, Москва
Россия

Рахманкулов Виль Закирович

руководитель отдела, отдел 82



К. В. Южанин
Федеральный исследовательский центр «Информатика и управление» РАН, Москва
Россия
Южанин Кирилл Викторович


Список литературы

1. Павловский Ю.Н., Смирнова Т.Г. Проблема декомпозиции в математическом моделировании. М.: ФАЗИС, 1998. 272 с.

2. Ёлкин В.И. Редукция нелинейных управляемых систем: декомпозиция и инвариантность по возмущениям. М.: ФАЗИС, 2003. 208 с.

3. Цурков В.Н. Декомпозиция в задачах большой размерности. М.: Наука, 1981. 352 с.

4. Петровский А.Б., Лобанов В.Н. Многокритериальный выбор в пространстве признаков большой размерности: мультимедийная технология ПАКС-М // Искусственный интеллект и принятие решений. 2014. № 3. С. 92 – 104.

5. Agarwal S., Agrawal R., Deshpande P.M., Gupta A., Naughton J., Ramakrishnan R., Sarawagi S. On the computation of multidimensional aggregates // Materialized views: techniques, implementations and applications / Ed. by A. Gupta, I.S. Mumick. Camb.: MIT Press, 1999. Ch. 24. Pp. 506 – 521. DOI: 10.7551/mitpress/4472.003.0030

6. Чубукова И.А. Data mining: учеб. пособие. 2-е изд. М.: Бином. Лаборатория знаний, 2008. 382 c.

7. Макаров И.М., Рахманкулов В.З., Ахрем А.А., Ровкин И.О. Исследование свойств гиперкубовых структур в OLAP-системах // Информационные технологии и вычислительные системы. 2005. № 2. С. 4 – 9.

8. Ахрем А.А., Рахманкулов В.З., Южанин К.В. О сложности редукции моделей многомерных данных // Искусственный интеллект и принятие решений. 2016. № 4. С. 79-85.

9. Ахрем А.А., Рахманкулов В.З., Южанин К.В. Декомпозиционные методы анализа многомерных данных // Системные исследования. Методологические проблемы: ежегодник 2015 – 2018. Вып. 38. М., 2018. С. 88 – 97.

10. Ахрем А.А., Носов А.П., Рахманкулов В.З., Южанин К.В. Вычислительная производительность методов редукции гиперкубов многомерных данных аналитических OLAP-систем // Искусственный интеллект и принятие решений. 2019. № 4. С. 23 – 28.

11. Гуров С.И. Булевы алгебры, упорядоченные множества, решётки. 2-е изд. М.: URSS, 2013. 352 c.

12. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука. ФИЗМАТЛИТ, 1997. 368 с.


Дополнительные файлы

1. Неозаглавлен
Тема
Тип Исследовательские инструменты
Скачать (24KB)    
Метаданные

Для цитирования:


Носов А.П., Ахрем А.А., Рахманкулов В.З., Южанин К.В. Анализ вычислительной сложности методов декомпозиции OLAP–гиперкубов многомерных данных. Математика и математическое моделирование. 2020;(4):52-64. https://doi.org/10.24108/mathm.0420.0000221

For citation:


Nosov A.P., Akhrem A.A., Rakhmankulov V.Z., Yuzhanin K.V. Computational Complexity Analysis of Decomposition Methods of OLAP Hyper-cubes of Multidimensional Data. Mathematics and Mathematical Modeling. 2020;(4):52-64. (In Russ.) https://doi.org/10.24108/mathm.0420.0000221

Просмотров: 677


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)