Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
VPS в 21 локации

От 104 рублей в месяц

Безлимитный трафик. Защита от ДДоС.

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

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 кубов Выше: Аппроксимирующие алгоритмы Назад: Аппроксимирующие алгоритмы   Содержание

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

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

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

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

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