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

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

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

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

Вейвлеты

Одной из самых успешных (с точки зрения ожидаемых результатов) работ в области аппроксимации OLAP-данных является [24].

Основными посылками работы явились два наблюдения:

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

Рассмотрим особенности работы этого алгоритма. Прежде всего отметим, что это алгоритм нацелен на оптимизацию только одного типа запросов — подтипа интервальных запросов (range-sum query).

Range-sum query: $ Sum(l_1:h_1,\ldots,l_d:h_d) = \sum\limits_{l_1\le i_1 \le h_1}\cdots \sum\limits_{l_d\le i_d \le h_d}A[i_1,\ldots,i_d]$

Шаги алгоритма:

Шаг Первый

Формируется куб частичных сумм (partial sum cube) — куб, в котором ячейки представляют собой многомерные суммы всех прилежащих ячеек. Это представление данных хорошо тем, что ячейки куба частичных сумм монотонно не убывают по всем измерениям, поэтому аппроксимация подобного куба является более точной, нежели аппроксимация исходного куба. Для ответа на интервальный запрос требуется оценка значения лишь в одной ячейке, а не в целом наборе ячеек.

Partial Sum Cube:

$ P[x_1,\ldots,x_d] = Sum(0:x_1,\ldots,0:x_d)=\sum\limits_{0\le i_1 \le x_1}\cdots \sum\limits_{0\le i_d \le x_d}A[i_1,\ldots,i_d]$

Шаг Второй
Создается новый куб, в котором каждая в каждой ячейке содержится натуральный логарифм значения соответствующей ячейки из куба частичных сумм. Таким образом, еще больше ''сглаживаются'' колебания значений.
Шаг Третий
Формируется декомпозиция получившегося куба, основанная на вейвлетах ( в простейшем случае, хоаровских вейвлетах), — декомпозиция неоднократно применяется для каждого из измерений; таким образом, куб ''складывается'' по каждому из измерений.

Пример декомпозиции сигнала

Положим, у нас есть одномерный набор значений $ [2,2,7,11]$ .

Таблица 3.1: Декомпозиция сигнала вейвлетами

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert}
\hline
Разрешение & С...
...] &[0,2]\\
\hline
1&[5$\frac 1 2$]&[3$\frac 1 2$]\\ [2pt]
\hline
\end{tabular}$

Конечное преобразование сигнала будет выглядеть так $ [5\frac1 2,3\frac 1 2 ,0,2]$ . Подобные преобразования могут выполняться очень быстро. Детальные коэффициенты в данном примере нормализуются по уровню.

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

Шаг Четвертый
На следующем этапе мы выбираем $ C$ главных коэффициентов вейвлетовой декомпозиции данных. Остальные $ N - C$ коэффициентов мы получаем, усредняя начальные $ C$ коэффициентов. Хранятся только $ C$ коэффициентов куба.

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

К сожалению, несмотря на всю эффективность этого метода, он подходит лишь для обработки только одного типа запросов. Более того, для создания кубов этот алгоритм требует достаточного объема вычислений, и результирующий куб почти невозможно изменять при изменениях данных. Применение этого алгоритма ограничено также и тем, что необходимо тщательно выбирать коэффициент $ C$ , основываясь на заданном допустимом значении ошибки.

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

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

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

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

Релиз ядра Linux 4.14  (6)
Пятница 17.11, 16:12
Apple запустила Pay Cash (2)
Четверг 09.11, 21:15
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
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...