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


Алгоритм Bottom-Up Computation - часть 2


Рисунок показывает порядок партиционирования исходных данных по различным элементам измерения А, затем В, С и D. Для этого BUC сканирует исходные данные, агрегируя все кортежи, чтобы получить итоговое значение all. Партиционирование по измерению А создает 4 партиции, при этом запоминается количество кортежей в каждой партиции.

Рис. 4.1:

Разбиение данных при работе алгоритма BUC

Image buc_partitioning_small

Использование условия Appriori позволяет сократить время работы алгоритма. Начиная с элемента

$ a_1$

измерения A, кортежи партиции

$ a_1$

агрегируются с вычислением значения

$ (a_1, *,*,*)$

. Предположим, что

$ (a_1, *,*,*)$

удовлетворяет условию MinSup, тогда запускается рекурсивное вычисление для партиции

$ (a_1, *,*,*)$

.

$ (a_1, *,*,*)$

партиционируется по измерению В. Проверяется количество кортежей для

$ (a_1,b_1,*,*)$

. Если для

$ (a_1,b_1,*,*)$

условие MinSup удовлетворяется, то партиционирование продолжается по C, начиная с

$ c_1$

. Если же в

$ (a_1,b_1,c_1,*)$

количество исходных фактов равно 2, что не удовлетворяет исходному условию MinSup , то по лемме Apriori и ни один из потомков не будет удовлетворять условию MinSup. В этом случае алгоритм BUC не вычисляет дальше

$ (a_1,b_1,c_1,*)$

, избегая затрат на партиционирование по измерению D. Вычисляется

$ (a_1,b_1,c_2,*)$

и так далее.

Производительность алгоритма BUC зависит от порядка измерений и симметричности данных. Измерения должны обрабатываться в порядке убывания мощности (количества элементов). Чем больше мощность измерения, тем меньше партиции и больше вариантов для применения условия MinSup. Аналогично, равномерные измерения (когда данные равномерно распределены по элементам) лучше подходят для применения условия Apriori.

Основным достоинством алгоритма BUC можно считать эффективное распределение затрат на партиционирование. Однако, в отличие от MultiWay, расходы на агрегирование не разделяются между родителями и потомками. К примеру, результаты вычисления подкуба AB не используются для вычисления подкуба ABC, который нужно вычислять с нуля.

Вперед: Алгоритм Star-Cubing

Выше: Вычисление Iceberg кубов

Назад: Вычисление Iceberg кубов

 




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