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


Вейвлеты


Одной из самых успешных (с точки зрения ожидаемых результатов) работ в области аппроксимации 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]$

. Подобные преобразования могут выполняться очень быстро. Детальные коэффициенты в данном примере нормализуются по уровню.

В ходе таких преобразований информация не теряется и не приобретается.


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



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