Обзор алгоритмов MOLAP


Алгоритм Bottom-Up Computation


BUC-алгоритм предназначен для вычисления разреженных кубов и кубов типа айсберг. При этом, в отличие от MultiWay, куб рассчитывается от наиболее общего подкуба к детальным подкубам. Поэтому можно снизить затраты на партиционирование данных. К тому же подобный порядок позволяет наиболее эффективно использовать условие Apriori, снижая объем необходимых вычислений.

Bottom-Up Computation переводится как вычисление "снизу вверх", что вызывает недоумение, т.к. структуры кубов принято изображать, располагая детальные подкубы ниже, а агрегирующие выше. С этим связаны и термины roll-up и drill-down: мы или поднимаемся выше по структуре, агрегируя данные (roll-up), либо спускаемся к детальным элементам (drill-down). Однако авторы работы [4], использовали противоположный подход, и название алгоритма закрепилось.

На рисунке изображена схема работы алогоритма BUC для создания трехмерного куба ABC, с измерениями A, B и С.

В общих чертах, алгоритм работает следующим образом:

  1. Агрегируется весь набор входных данных и записывается итоговый результат.
  2. Для каждого измерения d входные данные партиционируются по d, т.е. для каждого уникального элемента d создается партиция.
  3. Для каждой партиции, созданной на предыдущем шаге, проверяется условие MinSup. К примеру, если задано условие count > x, то проверяется количество кортежей в партиции.
  4. Если партиция удовлетворяет условию MinSup, то рекурсивно запускается алгоритм BUC, и в качестве входных данных используется эта партиция. Таким образом вычисляется куб типа айсберг по измерениям, начиная от d+1.
  5. После возвращения из вложенных рекурсивных вызовов на партициях по измерению d, алгоритм повторяется для следующего измерения.

Рассмотрим работу алгоритма на примере создания четырехмерного куба с измерениями A, B, C и D и условием MinSup "count > 3". Предположим, что измерение А содержит 4 элемента

$ a_0,a_1,a_2,a_3,a_4$

, измерение B - 4 элемента

$ b_0,b_1,b_2,b_3,b_4$

, измерение C - 2 элемента

$ c_1, c_2$

и измерение D - 2 элемента

$ d_1, d_2$

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




Начало  Назад  Вперед



Книжный магазин