Preview

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

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

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

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

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

Аннотация

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

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

Об авторах

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

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

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



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

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

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



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

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

Зав. отделом, отдел 82



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

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.


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

Рецензия

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


Носов А.П., Ахрем А.А., Рахманкулов В.З. Анализ эффективности декомпозиции OLAP-гиперкубов данных для методов экспоненциальной вычислительной сложности. Математика и математическое моделирование. 2021;(3):29-45. https://doi.org/10.24108/mathm.0321.0000258

For citation:


Nosov A.P., Akhrem A.A., Rakhmankulov V.Z. Efficiency Analysis of OLAP-data Hypercube Decomposition for Exponential Computational Complexity Methods. Mathematics and Mathematical Modeling. 2021;(3):29-45. (In Russ.) https://doi.org/10.24108/mathm.0321.0000258

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


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


ISSN 2412-5911 (Online)