Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Обучение от Mail.Ru Group.
Онлайн-университет
для программистов с
гарантией трудоустройства.
Набор открыт!
2008 г.

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

Юрий Кудрявцев, факультет ВМиК МГУ

Вперед: Семантические алгоритмы Выше: Вычисление Iceberg кубов Назад: Алгоритм Bottom-Up Computation   Содержание

Алгоритм Star-Cubing

Алгоритм Star-Cubing, представленный в работе [13], предназначен для вычисления кубов типа айсберг. В алгоритме сочетаются агрегирование "снизу-вверх" и "сверху-вниз", многопозиционное агрегирование (как в алгоритме MultiWay) и применение леммы Apriori (как в алгоритме Bottom-Up Computation). Данные хранятся в специальной структуре star-tree, эффективно сжимающей данные, что позволяет сократить время расчета и объем потребляемых ресурсов.

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

Последовательность вычислений в алгоритме Star-Cubing проиллюстрирована на рисунке 4.2, описывающем вычисление четырехмерного куба ABCD. Если бы использовалась только вычисление снизу-вверх, то подкубы, помеченные словом "отсечено", были бы вычислены. Star-Cubing может отсечь указанные подкубы, принимая в расчет разделяемые измерения. Здесь ACD/A означает, что подкуб ACD имеет разделяемое измерение А, ABD/AB — подкуб AB имеет разделяемое измерение AB, ABC/ABC — подкуб ABC имеет разделяемое измерение ABC и т.д. Таким образом, все подкубы ветви, начинающейся с ACD, включают измерение A, ветви, начинающейся с ABD,- измерение AB, ветви, начинающейся с ABC,- измерение ABC. Подобные измерения называются разделяемыми для соответствующих ветвей.

Поскольку разделяемые измерения можно обнаружить в самом начале вычисления дерева подкубов, можно избежать перевычисления подобных измерений в дальнейшем. К примеру, подкуб AB, вычисляемый из ABD, отсечен, т.к. уже вычислен в ABD/AD. Аналогично отсекается куб A, вычислимый из AD, т.к. уже вычислен ACD/A.

Напомним, что необходимым условием использования условия Apriori является дистрибутивность используемой агрегирующей функции. К примеру, если в разделяемом измерении А значение $ a_1$ не удовлетворяет условию MinSup, то отсекается вся ветвь от $ a_1CD/a_1$ (включая $ a_1C/a_1C,a_1D/a_1,a_1/a_1$ ), поскольку эти ячейки заведомо не удовлетворяют условию MinSup.

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

В алгоритме для представления индивидуальных подкубов используются деревья. На рисунке 4.3 изображена часть дерева куба для подкуба ABCD. Каждый уровень дерева представляет собой измерение, и каждый узел представляет собой значение атрибута. Каждый узел имеет 4 поля: значение аттрибута, агрегированное значение, указатель/указатели на потомков и указатель/указатели на элементы того же уровня. Кортежи подкуба вставляются в дерево один за другим. Путь от корня к листу представляет собой кортеж. К примеру, агрегированное значение (по мере count) узла $ c_2$ в дереве равно 5, что означает 5 ячеек значения $ (a_1,b_1,c_2,*)$ . Подобное представление позволяет сократить пространство, требуемое для хранения общих префиксов (см. также алгоритм DWARF), и хранить агрегированные значения в внутренних узлах, что позволяет на этапе вычисления отсекать ветви, основанные на разделяемых измерения. К примеру, дерево подкуба AB может быть использовано для отсечения возможных ячеек в ABD.

Если агрегированое значение, допустим p, не удовлетворяет условию, то бесполезно различать подобные узлы в процессе вычисления куба. Поэтому узел p можно заменить *, еще больше сжимая таким образом дерево. Будем называть узел р узлом-звездой (star-node), если агрегированное значение по измерению в точке p не удовлетворяет условию MinSup. Дерево подкуба, сжатое с помощью узлов-звезд, будем называть деревом звезд (star-tree).

Рассмотрим пример построения дерева-звезд.

Таблица 4.1: Фактическая таблица для куба из четырех измерений до начала работы алгоритма Star-Cubing.

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert}
\hline
...
... $d_4$ & 1\\
\hline
$a_2$ & $b_4$ &$c_3$ & $d_4$ & 1\\
\hline
\end{tabular}
$

Как показывает таблица 4.1 всего существует 5 кортежей и 4 измерения. Размерности измерений A,B,C,D равны 2,4,4,4 соответственно. Одномерные агрегаты приведены в таблице 4.2. Предположим MinSup = 2, тогда только значения $ a_1, a_2, b_1, c_3, d_4$ удовлетворяют условию. Все прочие значения превращаются в узлы-звезды. После отбрасывания узлов-звезд получается таблица 4.3. Отметим, что эта таблица содержит меньше кортежей и различных значений, нежели исходная таблица фактов. Поэтому для построения подкуба мы будем использовать эту таблицу. Получившееся дерево звезд изображено на рисунке 4.4, а таблица узлов-звезд — на таблице 4.4 . Для выделения узлов-звезд используются таблицы звезд (от англ star-table) для каждого дерева. Пример таблицы подобной таблицы для описанного выше случая приведен на рисунке . Более эффективно использовать битовые массивы или хэш таблицы для таблиц звезд.

Таблица 4.2: Агрегаты по каждому из измерений.

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert}
\hline
Dimension & co...
..._4$ &$c_3(2)$\\
\hline
$D$ & $d_1,d_2,d_3$ &$d_4(2)$\\
\hline
\end{tabular}
$

Таблица 4.3: Фактическая таблица после удаления узлов-звезд.

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert}
\hline
...
...*$ & $*$ & 1\\
\hline
$a_2$ & $*$ &$c_3$ & $d_4$ & 2\\
\hline
\end{tabular}
$

Рис. 4.4: Дерево звезд
Image star_cubing_star_tree

Таблица 4.4: Таблица узлов-звезд для рисунка 4.4

$\displaystyle \begin{tabular}{\vert c\vert}
\hline
$b_2 \rightarrow *$ \\
\hli...
... *$ \\
\hline
$d_1 \rightarrow *$ \\
\hline
\ldots \\
\hline
\end{tabular}
$

Сокращая узлы-звезд, дерево звезд обеспечивает точное сжатие исходных данных, эффективное с точки зрения использования памяти. Однако возрастают временные затраты на поиск узлов или кортежей в дереве. Для сокращения подобных затрат все узлы в дереве звезд сортируются по алфавиту внутри каждого измерения, причем узлы-звезды отображаются первыми. В целом, узлы сортируются в порядке $ *,p_1,p_2,...,p_n$ на каждом уровне.

Рассмотрим на этом же примере примере, как в работе Star-Cubing алгоритма используются деревья-звезды.

При агрегировании используется дерево-звезд типа того, которое изображено на рисунке 4.4. Агрегирование начинается снизу-вверх, при этом используется алгоритм поиска в глубину. Первый этап вычислений (т.е. обработка первой ветви дерева) изображен на рис 4.5. В левой части рисунка показано основное дерево звезд. Для каждого значения атрибута изображено агрегированное значение этого узла. Подстрочный номер указывает порядок обхода узлов. Остаются деревья BCD, ACD/A, ABD/AB, ABC/ABC, потомки основного дерева звезд, отвечающие за уровень выше базового на рисунке 4.2. Подстрочные номера вновь указывают на порядок обхода. Например, на первом шаге алгоритма создается корневой узел дерева-потомка BCD, на втором — корневой узел дерева ACD/A, на третьем — корневой узел ABD/AB и узел b*.

В правой части рисунка 4.5 показаны деревья в памяти на 5-ом шаге алгоритма. Поскольку к этому моменту поиск в глубину достигает листа дерева, происходит возврат. До возврата алгоритм отмечает, что все возможные узлы базового измерения ABC уже были просмотрены. Это значит, что дерево ABC/ABC уже просмотрено, и результат равен count, а дерево можно удалить. Аналогично, двигаясь назад от d* к c* и принимая во внимание, что у c* нет потомков, алгоритм устанавливает, что count в ABD/AB является финальным результатом, и дерево удаляется.

При возврате в вершине b*, поскольку существует одноуровневый узел $ b_1$ , дерево ACD/A будет сохранено в памяти, и поиск в глубину пойдет от вершины $ b_1$ , так же, как до этого от b*. Результирующие деревья изображены на рисунке 4.6. Деревья потомки ACD/A и ABD/A создаются заново, со значениями из поддерева $ b_1$ . К примеру, агрегированное значение с* в ACD/D возрастает от 1 до 3. Деревья остаются неизменными, к ним лишь добавляются новые ветви либо увеличиваются агрегированные значения. Например, дополнительная ветвь добавляется в дерево BCD.

По достижению листа d* алгоритм вновь возвращается, в этот раз до $ a_1$ , где будет замечен одноуровневый узел $ a_2$ . В этом случае будут удалены все деревья, кроме BCD на рисунке 4.6. После этого аналогичный обход будет совершен для $ a_2$ . Дерево BCD продолжает расти, а остальные деревья начинаются с корня в $ a_2$ .

Для того, чтобы у узла были потомки, необходимо выполнение двух условий:

  1. узел должен удовлетворять условию MinSup ;
  2. дерево, исходящее из этого узла, должно быть невырожденным, т.е. содержать хотя бы один нетривиальный узел (не узел-звезду).

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

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

Star-Cubing также можно использовать и для полной материализации куба. При вычислении полного куба на плотном массиве данных производительность Star-Cubing сравнима с производительностью MultiWay и намного превосходит производительность BUC. В случае разреженных исходных данных StarCubing намного быстрее MultiWay и в большинстве случаев быстрее BUC. При вычислении кубов типа айсберг Star-Cubing быстрее BUC, если данные распеределены несимметрично, и разрыв в производительности увеличивается по мере уменьшения MinSup.

Вперед: Семантические алгоритмы Выше: Вычисление Iceberg кубов Назад: Алгоритм Bottom-Up Computation   Содержание

Новости мира IT:

Архив новостей

Последние комментарии:

Релиз ядра Linux 4.14  (7)
Среда 22.11, 11:59
Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...