автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Метод приближенной обработки запросов в системах оперативного анализа данных

/

Ухаров Андрей Олегович

Метод приближенной обработки запросов в системах оперативного анализа данных

Специальность 05.13.17 - Теоретические основы информатики (технические науки)

Автореферат диссертации на соискание ученой степени кандидата технических наук

1 2 МАЙ 2011

Москва-2011

4845405

Работа выполнена в Московском государственном техническом университете им. Н. Э. Баумана.

доктор технических наук, профессор Григорьев Юрий Александрович

доктор технических наук, профессор Синицин Игорь Николаевич

доктор технических наук, доцент Романов Виктор Петрович

Федеральное государственное унитарное предприятие «Научно-исследовательский институт «Восход»

Защита диссертации состоится «26» мая 2011 года в 14:30 на заседании диссертационного совета Д 212.141.10 в Московском государственном техническом университете имени Н.Э. Баумана по адресу: 107005, г. Москва, 2-я Бауманская ул., д.5.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н.Э. Баумана.

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

Автореферат разослан «_»_2011 г.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Ученый секретарь

Диссертационного совета Д 212.141.10 к.т.н., доцент

С.Р. Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В настоящее время распространены три основных подхода к приближенной обработке запросов: методы выборки, методы гистограмм и методы вейвлет-преобразования. Однако существующие подходы обладают рядом недостатков, что сдерживает их применение на практике. Методы выборки и гистограмм ориентированы на получение агрегатных значений с большим количеством элементов. Вычисление же единичных значений или сумм с небольшим числом слагаемых сопровождается значительной погрешностью. Более того с ростом размерности данных (а в современных ОЬАР-системах по оценкам аналитиков количество измерений в кубах достигает 10-15) увеличивается стоимость построения и хранения приближенного представления, обеспечивающего приемлемую погрешность. В этой связи наиболее перспективным представляется подход на основе вейвлет-преобразования, позволяющий вычислять как единичные, так и суммарные значения на основе многомерных данных. Однако существующие методы накладывают ряд ограничений на структуру данных, не позволяют производить обновление значений без полного пересчета всего набора и не предоставляют точных методов оценки погрешностей.

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

Цель работы. Целью данной работы является разработка математических методов и инструментального средства для приближенной обрабопш запросов на основе вейвлет-преобразования. Ч4

В работе решаются следующие задачи:

1. Разработка метода вейвлет-преобразования Хаара г-мерного набора данных с произвольной длиной измерений.

2. Разработка метода восстановления исходного элемента и суммы элементов из сжатого хранилища данных с произвольной длиной измерения.

3. Разработка метода обновления сжатого хранилища данных без полного пересчета вейвлет-коэффициентов.

4. Разработка метода оценки погрешностей восстановления исходного элемента данных и суммы элементов.

5. Разработка инструментального средства приближенной обработки запросов.

6. Разработка ОЬАР-системы «Надзор за заболеваемостью» и анализ результатов использования предложенных методов.

Объект исследования. Объектом исследования настоящей работы являются системы оперативного анализа данных (ОЬАР-системы).

Предмет исследования. Предметом исследования являются процессы приближенной обработки запросов на основе вейвлет-преобразования в системах оперативного анализа данных.

Научная новизна. В работе получены следующие новые научные результаты:

1. Разработан метод нестандартного вейвлет-преобразования Хаара, учитывающий произвольную длину измерений, отличную от 2", и позволяющий уменьшить объем хранимых вейвлет-коэффициентов до объема исходных значений. Доказана лемма о замещении усредненных вейвлет-коэффициентов на разных уровнях детализации вейвлет-преобразования, что позволило сократить количество операций чтения/записи.

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

3. Доказаны леммы и теорема о независимости расчета обновленных значений в разработанных алгоритмах дискретного нестандартного вейвлет-преобразования Хаара и на их основе предложен метод обновления имеющейся вейвлет-декомпозиции без пересчета ранее вычисленных вейв-лет-коэффициентов.

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

Методы исследования. Исследования проводились на основе комплексного использования теории вейвлетов, теории вероятности, теории алгоритмов.

Практическая ценность полученных результатов. В настоящей работе для практического использования предложенных методов приближенной обработки запросов на основе вейвлет-преобразования и оценки погрешности восстановления значений разработано инструментальное средство. Оно позволяет сформировать приближенное представление многомерного набора данных (ОЬАР-куба) с произвольной длиной измерения по заданным критериям: допустимая прогнозируемая погрешность вычисления единичного значения, допустимая прогнозируемая погрешность вычисления суммы значений с учетом ее мерности, объем приближенного представления. На основе приближенного представления с помощью инструментального средства можно восстанавливать единичные и суммарные значения. Таким образом, разработанное инструментальное средство предоставляет возможность сформировать приближенное представление данных с прогнозируемой погрешностью и требуемым объемом, и осуществлять аналитическую обработку над ним, получая единичные либо суммарные значения. Приближенное представление при необходимости может быть обновлено. При этом не накладывается ограничение на длину измерений.

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

Публикации по теме. По материалам настоящей работы опубликовано 6 печатных работ, из них 4 - в научных журналах, рекомендуемых ВАК.

Апробация работы. Материалы работы были изложены автором на семинарах кафедры ИУ-5 МГТУ им. Н.Э. Баумана в 2008 и 2009 годах.

Объем работы. Диссертационная работа содержит 187 страниц, 52 рисунка и 16 таблиц, 1 страницу копий актов о внедрении, список литературы из 141 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе "Критический анализ существующих методов приближенной обработки запросов в ОЬАР-системах" приведено описание систем аналитической обработки данных, выделены их особенности. В рамках ОЬАР-систем рассмотрена концепция приближенной обработки запросов,

указаны ее основные этапы. Подробно проанализированы существующие подходы к приближенной обработке запросов и выделен ряд существенных недостатков. На основе проведенного анализа сформулирована концепция и требования к новым методам приближенной обработки запросов.

Для систем аналитической обработки данных приведено описание модели данных (многомерные кубы) и рассмотрены основные операции (формирование срезов, вращение, укрупнение и детализация). Выделены ключевые принципы ОЬАР-систем: 1) многомерное представление данных, 2) гибкость анализа, т.е. возможность построения произвольных неформализованных запросов, 3) устойчивая производительность анализа, т.е. производительность при выполнении произвольного запроса, 4) глубина анализа, т.е. поддержка необходимого числа измерений, 5) поддержка вычисления суммарных значений.

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

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

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

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

В результате анализа было выявлено, что методы приближенной обработки данных на основе вейвлет-преобразования являются наиболее перспективными с точки зрения обработки наборов данных с множеством измерений и вычисления как единичных, так и суммарных значений. Был проведен детальный анализ существующих методов, основанных на вейвлет-преобразовании. Анализ показал, что они обладают рядом существенных недостатков:

1. Недостаточно разработанные методы оценки погрешности восстановления значений: верхняя граница общей относительной погрешности не позволяет адекватно оценить качество приближенного ответа; не оцени-

вается погрешность вычисления сумы значений; ряд оценок подразумевает использование динамического программирования.

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

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

В связи с недостатками существующих математических методов возникла необходимость разработать следующее:

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

2. Математические методы оценки погрешности восстановления единичного значения и суммы значений.

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

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

Известно, что вейвлет-преобразование Хаара представляет собой математический метод иерархической декомпозиции функций. Исходный массив данных можно представить в виде кусочно-постоянной функции. Множество функций представляют собой пространство V-1, где .¡-количество интервалов, на которых функция постоянна. Базис для пространства У-1 может быть задан масштабирующими характеристическими функциями, каждая из которых отличается от нуля на некотором отрезке.

Можно определить еще одно пространство как ортодополнение для У-1 в пространстве . Совокупность множества линейно-независимых

(1)

функций из пространства WJ называется множеством вейвлетов Хаара.

= -х-1)Д = 0..2] -1;у/(>0 =

' 1 1,0<х<—

2

О.иначе

(2)

Таким образом, вейвлеты из являются инструментом для преставления той части функций в , которую невозможно представить в V'.

Например, набор данных из четырех значений может быть представ-

2

лен как Р(х) = с^ (х) + с^2 (х)+с2^(х) + сз^(х), где коэффициенты С; соответствуют значениям исходного массива. Переписывая это же выражение в базисе V1 и V1, на следующем уровне детализации имеем

Р(х) = с{,^(х) + с}^1 (х) + с^(х) + &\у/\ (х), где =¿±51 - усреднен-

2 2 2 2

ные коэффициенты, а ^_со~с1 ;(1|_с2~сз _ уточняющие коэффициенты.

Наконец, переходя к базису У0^0^1, на последнем уровне детализации получаем Р(х) = + с!°1//д (х) + (^¿(х) + ¿¡^'(х). Таким образом, через

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

Дискретное нестандартное вейвлет-преобразование Хаара (ДНВПХ) для многомерного набора данных заключается в последовательном применении операций усреднения и уточнения по каждому из измерений на всех уровнях детализации. Как видно, существующий метод подразумевает, что длина измерения равна 2".

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

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

В диссертационной работе предложен метод нестандартного вейвлет-преобразования, на основе ДНВПХ Чакрабарти, позволяющий работать с измерениями произвольной длины, сокращая при этом количество операций чтения/записи. В процессе разработки данного метода была доказана лемма о замещении значений.

Лемма 1. При ДНВПХ Чакрабарти усредненные значения А{ уровня детализации j заменяются усредненными и уточняющими значениями А/-1,о/"1 уровняИ,] = 1.Хеутах, где Ьеутах- максимальный уровень детализации. ■

Определение 1. Пусть задано измерение произвольной длины Щ|| = ш. Измерение с1;Ас1с1 будем называть дополненным, если оно эквивалентно с!|, но при этом длина которого считается равной 2" :2П > т. Несуществующие значения в интервале (ш,2п] будем называть фиктивными значениями, ш

Определение 2. Измерение на уровне детализации ] на некотором шаге к является неактивным, если на этом шаге т^ >||^||-1, т.е. рассчитанное на шаге к значение правой координаты попадает в область фиктивных значений. ■

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

V - исходный набор данных

\Л/ - вейвлет-декомпозиция

а в с

авсо.о

авсо.о

авсо.о &в. СО

/

\

ав.со _

ав.со

ав.со

ре

ч

Л

Е И

А.В ____ с 0

□ - Фиктивное значение/ коэффициент

а.в-

Прямой ход рекурсии

„ _ I | - Область уточняющих

Обратный ход рекурсии I—I коэффициентов **

а+в 2

= ^

Рис. 1. Вейвлет-преобразование с произвольной длиной измерения

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

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

На рис. 2 представлено вычисление суммы трех значений исходного набора. На каждом уровне детализации (от 3 до 0) в соответствии с областями действия определяются коэффициенты, участвующие в восстановлении слагаемых суммы. Значения отсутствующих коэффициентов (второй и шестой коэффициенты) вычисляются исходя из их расположения в декомпозиции и знания того, что исходные фиктивные значения трактовались нулями. На уровнях 1 и 0 учитывается взаимная компенсация коэффициентов.

£У = У(0) + У(1) + У(2)

□ - Фиктивное значение/ коэффициент

Область действия

W

1.625 1.625 1.75 -1 1.5

1.625 1.625 1.75 -1 м

1.625 1.625 1.75 -1 13

1.625 1.625 1.75 -1 15

1.625-3 = 4.875

1.625-3 = 4.875

4.875

9.75

1.75+|1.75-1.751

-1 + 1И.5

11.5

13

IV =13

Рис. 2. Обратное вейвлет-преобразование для суммы значений

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

Лемма 2. Пусть задан г-мерный набор данных, в котором длины всех измерений равны 2". Количество реальных значений в каждом измерении

равно к, такое что к < 2" и ш = . Тогда при ДНВПХ с произвольной

длиной измерения уточняющие вейвлет-коэффициенты будут добавлены в декомпозицию только на уровнях Ьеу^ -1,1 = 1.лп, а общее среднее на уровне 0. ■

Лемма 3. При ДНВПХ с произвольной длиной измерения г-мерного набора данных, в котором длины всех измерений равны, левая и правая части набора данных по каждому измерению на каждом уровне детализации 0.1еутах -1 рассчитываются независимо друг от друга. ■

Теорема 1. Пусть задан г-мерный набор данных V с дополненными измерениями длиной 2П, где координаты фиктивных значений лежат в интервале [2т..2"-1],ш<п. Пусть для этого набора получена декомпозиция на основе ДНВПХ с произвольной длиной измерения. Если добавить в исходный набор данных значения с координатами [2т..2т+к - 1],т + к < п, то при вычислении декомпозиции обновленного набора данных V' на уровне детализации п-ш-1 декомпозицией левой части V' будет являться декомпозиция ^Л^, а усредненным значением на данном уровне -Ч\Ч{0,..0}). -

В диссертационной работе предложен новый метод вычисления погрешности приближенной обработки данных. Он позволяет оценить распределения ошибки восстановления как исходного элемента данных, так и суммы элементов. Обозначим исходный набор данных как У(у1)(1 = 1..2"), а восстановленный как = 1..2"). Будем считать, что восстановленный набор был получен после обнуления некоторых нормализованных вейвлет-коэффициентов Ср] = 1..М*,^ в соответствующей декомпозиции W. Таким

образом, единичное исходное значение может быть представлено как V; = VI + ДУ|, где АУ; - ошибка восстановления.

Введем вероятностное пространство. Пусть конкретные | ] = случайно равномерно распределены по кубу вейвлет-

декомпозиции. Тогда конкретная декомпозиция с коэффициентами {^и = 1..М*,сз*0}, которые находятся в определенных позициях и которые

впоследствии будут обнулены, является единичной выборкой из соответствующей генеральной совокупности.

Пусть V - есть некоторое исходное значение. Выразим ошибку при

восстановлении V следующим образом:

= = (3)

В выражении (3) ^ - есть случайная величина соответствующая использованию вейвлет-коэффициента с^ который был обнулен и который должен был быть использован при восстановлении V. Величины были признаны независимыми. В дальнейшем индексы будем опускать. В работе

было показано, что ^ имеет распределение на уровне Ье[п-1..0], представленное в табл. 1. Р^,Р£- вероятности вхождения коэффициента 'с' с положительным и отрицательным знаком на уровне Ь, а кь- денормализую-щий коэффициент.

Таблица 1.

Распределение £

Вероятность Рь+ Рь

Значение 0

Далее была решена задача нахождения вероятностей • Было показано, что для того, чтобы некоторый коэффициент 'с' принял участие в восстановлении единичного исходного значения V на уровне детализации Ь необходимо выполнение 2-ух условий: попадание коэффициента на уровень Ь (вероятность Рь ) и попадание этого коэффициента в область действия Б (вероятность Рьз), соответствующую исходному значению. Для указанных вероятностей на основе структуры распределения областей действия вейв-лет-коэффициентов были найдены выражения (4), где г - количество измерений.

Рь=^Й;Рь5=2^+1-"')Ь6[п-1,0] (4)

Из (4) были получены окончательные выражения для р^ :

- - 2гп+1 (5)

Из выражения (3) имеем, что Ау представляет собой сумму независимых случайных величин ^, которые имеют распределение, представленное

в табл. 1. С использование центральной предельной теоремы Ляпунова в диссертационной работе было доказано, что при достаточно большом количестве отброшенных (обнуленных) коэффициентов (И*) распределение

Ду = £ , ] = 1. .И* близко к нормальному. }

Была исследована скорость сходимости распределения Ау к нормальному закону, которая может быть выражена следующим образом:

вир

Ф(х)

< а' . —, где А - некоторая константа.

V«7

Для распределения погрешности восстановления элемента исходных данных Ау были вычислены выражения математического ожидания и дисперсии.

М,(Ау) = 0;0,(АУ) = ^.^.|С? (6)

Аналогичные рассуждения были проведены для случая вычисления суммы элементов. Вероятность использования некоторого коэффициента 'с' на уровне детализации Ь для вычисления некоторой суммы £ V рассчитывается с помощью следующих величин: Р^ - вероятности попадания на уровень Ь (аналогично формуле (4)), РЬ8- вероятности попадания в область действия для суммы значений ]Гу, Ршс- вероятности, что данный коэффициент не будет компенсирован. При этом соответствующие события являются независимыми. В работе были получены следующие выражения, где т. — количество измерений, а I - мерность суммы:

р'5 = 2(«-гХп-Ь-1).ршс =^11£[1)2]Ье[п_1(0] (7)

Из (4) и (7) получаем окончательные выражения для :

- П. - 2Ы1+[+1 (8)

Получены выражения для математического ожидания и дисперсии ошибки восстановления суммы элементов, которые представлены ниже:

МЕ (ЛУ) = 0;ВЕ т = (9)

С помощью выражений (6) и (9) можно оценить доверительные интервалы ошибки восстановления как исходного элемента данных, так и суммы элементов.

Погрешность выполнения запроса общего вида можно оценить следующим образом. Пусть X - подмножество ячеек от 1 до М гиперкуба Г, М « Г. Поставим в соответствие ¡-ой ячейке этого подмножества переменную V,. Представим запрос на множестве X в виде функции от многих переменных: . Пусть Г - дифференцируемая функция. Ошибку

выполнения запроса можно представить в виде дифференциала функции £:

м ^

А Г = У ——Л V:, где Ду; - достаточно малая ошибка восстановления еди-

¡=1

ничного значения. Пусть {ДУ|} - независимые случайные величины. Тогда получим:

М(ДО = М,(Ду)2 0;П(ДО = В,(Ду)Е (10)

¡ = 1 ЗУ; ¡Д дv¡ ) ^ >

где у, - восстановленное значение 1-ой ячейки из множества X.

Например, для суммы М значений из (10) получим D(Af) = М ■ D, (Ду),

а для среднего - D(Af) = D'(Av).

М

В третьей главе "Разработка инструментального средства приближенной обработки запросов на основе ДНВПХ с произвольной длиной измерения" разработан проект инструментального средства (ИС) приближенной обработки запросов на основе методологии объектно-ориентированного анализа и проектирования с использованием унифицированного языка моделирования (UML - Unified Modeling Language). Приводится концептуальное, функциональное и структурное описание системы, описание архитектуры ИС, а также формализованное описание схемы БД и программного обеспечения. Для описания прикладной части ИС была разработана объектная модель, представленная в виде диаграммы классов.

Основной задачей, поставленной при разработке ИС, была возможность использования уже существующих механизмов организации хранения, управления и доступа к многомерным данным. В работе было предложено использовать многомерные БД OLAP-систем для размещения приближенного представления и осуществления запросов к нему. Таким образом, вейвлет-декомпозиция исходного набора данных представляется в виде OLAP-куба, содержащего вместо исходных значений вейвлет-коэффициенты. Доступ к вейвлет-коэффициентам осуществляется средствами языка MDX (Multidimensional Expressions), позволяющего оперировать многомерными данными.

В основу проектируемого ИС был положен модульный принцип, в результате чего были выделены два модуля и ряд библиотек, а также разработана схема их взаимодействия. На рис.3 приведена упрощенная структурная схема ИС.

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

Пользовательский модуль предоставляет возможность сформировать запрос к сжатому представлению данных (OLAP-кубу) и отобразить полученный приближенный результат. Для восстановления исходных значений из вейвлет-декомпозиции используется библиотека приближенных вычислений: на основе пользовательского MDX запроса определяется набор коэффициентов, необходимых для восстановления запрашиваемых значений, затем формируется множество MDX запросов, возвращающих нужные вейвлет-коэффициенты, и вычисляется искомое значение.

: Пользователь (Аналитик!

13: Отобразить

9: Создать МОХ запросы для получения вейвлет-коэффициентов

приближенное значение

8: Вычислить координаты необходимых вейвлет-коэффициентов 12: Рассчитать приближенное значение

Рис. 3. Упрощенная структурная схема ИС

В четвертой главе "Использование разработанного средства для создания компонента ОЬАР-модуля системы "Надзор за заболеваемостью" приведено описание реализации компонента аналитического модуля системы "Надзор за заболеваемостью", а так же исследованы результаты использования разработанного инструментального средства.

Система "Надзор за заболеваемостью" - государственная система сбора, передачи, хранения и анализа информации о заболеваниях человека и животных, а также связанных с ними данных об образцах и лабораторных тестах. Она реализована в виде распределенной БД с единым центром, в который стекаются данные, начиная с уровня районов. В год в системе регистрируется порядка 400 ООО случаев заболеваний.

В задачи аналитического модуля системы, используемого на государственном и региональных уровнях, входят:

1. Поиск факторов, коррелирующих с появлением заболевания.

2. Прогнозирование возможных вспышек заболеваний.

3. Анализ качества постановки диагнозов.

4. Исследование факторов передачи зоонозных заболеваний.

5. Уточнение карт эпидемиологического расследования случаев.

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

Для примера на рис. 4 показано, что в результате использования разработанного ИС удалось сократить объем исходного набора данных на 60%, снизив время выполнения запросов на 52%, при этом погрешность вычисления суммы исходных элементов составила 5.8% при прогнозе 6.2%. Здесь и далее используется доверительный интервал на уровне <т.

Пример исследования Какова зависимость количества выздоровевших от выбранного типа лечения в различных возрастных группах по стране?

Измерения Диагноз Пол Исход

Статус случая Госпитализация Тип вакцнации Тип печения Возрастная группа Род занятий Район

Квартал регистрации/^ случая_

Количество случаев заболевания

Рис. 4. Пример результатов использования ИС

Разработанное ИС позволило провести исследование качества предложенных методов оценки погрешностей, а также проанализировать выигрыш в объеме хранилища данных и скорости выполнения запросов.

На рис. 5а представлено сравнение рассчитанной и экспериментальной средней относительной погрешности восстановления единичного значения (элемента данных) для различных степеней сжатия данных. Аналогичное исследование было проведено для суммы значений. При этом помимо объема данных, была рассмотрена зависимость погрешности восстановления суммы значений от количества слагаемых. На рис. 56 представлено сравнение рассчитанной и экспериментальной средней относительной погрешности восстановления суммы значений для различных степеней сжатия и количества слагаемых (в приведенном примере количество слагаемых определяется мерностью суммы I). Как видно, предложенные методы оценки погрешности верны при различных степенях сжатия данных и различном количестве элементов в сумме.

На рис.5в показан выигрыш во времени выполнения запроса вычисления суммы значений в зависимости от степени сжатия данных для различной мерности суммы I.

9

Сокращение времени выполнения запросов: 47%

0-18

18-35 35-45 45-65 Возрастные группы

65+

Средняя относитепьная погрешность: 5.8% (Прогноз: 6.2%)

¡5 5 40%

U X

0 41

1 ™

§ S 30%

i о

í I 25% х х

•5 х 20%

¡3

X к

и X

О X

X ш

5 §

—♦-Эксперимент ■■» г* ^Оценка /

Г

i

1 (-

у!

<г

i I б i

- Эксперимент (t 1 из 3) ' -Оценка (t: 1 изЗ)

- Эксперимент 0; 2 из 3)

- Оценка {t: 2изЗ)

10% 20% 30% 40% 50% 60% 70% 80% Количество отброшенных коэффициентов

а

10% 20% 30% 40% 50% 60% 70% 80% Количество отброшенных коэффициентов

0% 10% 20% 30% 40% 50% 60% 70% 80% Количество отброшенных коэффициентов

Рис. 5. Анализ результатов исследования

Анализ результатов исследования показывает, что при существенном сжатии исходного набора данных (порядка 60%) происходит значительное уменьшение времени выполнения запросов (в среднем на 50%), при этом погрешности вычисления единичного и суммарного значений остаются небольшими (15% и 5% соответственно), что позволяет изучать тенденции поведения исследуемых величин при изменении тех или иных факторов, а в целом говорит о целесообразности применения предложенного метода приближенной обработки запросов.

ЗАКЛЮЧЕНИЕ

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

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

компенсацию коэффициентов и позволяющий вычислять несохраненные вейвлет-коэффициенты.

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

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

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

6. Исследованы результаты использования разработанного инструментального средства и предложенных методов оценки погрешностей. Сжатие данных на 60% уменьшает время выполнения запросов в среднем на 50% при погрешности восстановления исходного элемента и суммы элементов хранилища данных, равной 15% и 5% соответственно.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Григорьев Ю.А., Ухаров А.О. Обзор концепции многомерной модели данных в технологии OLAP // Проблемы построения и эксплуатации систем обработки информации и управления. - 2006. - №4. - С. 15-30.

2. Григорьев Ю.А., Ухаров А.О. Возможности приближенной аналитической обработки многомерных данных на основе вейвлет-преобразования // Проблемы полиграфии и издательского дела. - 2007. -№1. - С. 60-68.

3. Григорьев Ю.А., Ухаров А.О. Распределение ошибки при вейв-лет-сжатии в хранилищах данных OLAP // Информатика и системы управления. - 2008. - №3. - С. 3-14.

4. Григорьев Ю.А., Ухаров А.О., Плутенко А.Д. Использование вейвлет-преобразования для приближенной аналитической обработки многомерных данных // Информатика и системы управления. - 2008. - №1. -С. 3-11.

5. Григорьев Ю.А., Ухаров А.О. Вейвлет-сжатие в хранилищах данных OLAP // Информатика и системы управления. - 2008. - №4. -С. 3-10.

6. Ухаров А.О. Использование вейвлет-преобразования для представления многомерных данных в системах OLAP II Интеллектуальные технологии и системы. - 2005. - №7. - С.256-271.

Подписано к печати 18.04.11. Заказ № 275 Объем 1,0 печ.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 (499) 263-62-01

ВВЕДЕНИЕ.

ГЛАВА 1. Критический анализ существующих методов приближенной обработки запросов в OLAP-системах.

1.1. Системы оперативного анализа данных.

1.2. Концепция приближенной обработки запросов.

1.3. Критический анализ методов выборки.

1.3.1. Однородная случайная выборка (Uniform Random Sampling).

1.3.2. Смещенные выборки (Non-Uniform Biased Sampling).

1.3.3. Прогрессивная выборка (Online Aggregation Sampling).

1.3.4. Динамически используемые смещенные выборки.

1.3.5. Недостатки, присущие методам приближенной обработки запросов на основе выборки.

1.4. Критический анализ методов гистограмм.

1.4.1. Гистограммы равной ширины и глубины. Гистограммы со смещением.

1.4.2. Гистограммы с контролем ошибок.

1.4.3. Многомерные гистограммы.

1.4.4. Гистограммы на основе отношений.

1.4.5. Недостатки, присущие методам приближенной обработки запросов на основе гистограмм.

1.5. Критический анализ методов вейвлет-преобразования.

1.5.1. Вычисление интервальных запросов на основе вейвлет-декомпозиции.

1.5.2. Приближенная обработка произвольных запросов на основе вейвлет-представления Чакрабарти.

1.5.3. Приближенная обработка запросов на основе вероятностного сжатия вейвлет-декомпозиции.

1.6. Постановка задачи.

1.7. Выводы.

ГЛАВА 2. Методы дискретного нестандартного вейвлет-преобразования Хаара для произвольной длины измерения исходного массива данных с возможностью обновления декомпозиции, оценки распределения погрешности восстановления исходных элементов.

2.1. Дискретное нестандартное вейвлет-преобразование Хаара (ДНВПХ) многомерного набора данных.

2.2. Прямая и обратная вей влет-декомпозиция дискретного набора данных» с произвольной длиной измерения.

2.2.1. ДНВПХ Чакрабарти (СЬакгаЬагф.

2.2.2. ДНВПХ с произвольной длиной измерения и уменьшенным количеством операций чтения/записи.

2.2.3. Восстановление исходного элемента данных с помощью обратного ДНВПХ с произвольной длиной измерения.

2.2.4. Восстановление суммы исходных элементов данных с помощью обратного ДНВПХ с произвольной длиной измерения.

2.3. Обновление вейвлет-декомпозиции дискретного набора данных.

2.4. Оценка распределения погрешности восстановления исходного элемента данных и суммы элементов при сжатии вейвлет-декомпозиции.

2.4.1. Оценка распределения погрешности восстановления исходного элемента данных.

2.4.2. Оценка распределения погрешности восстановления суммы исходных элементов данных.

2.4.3. Расчет распределения погрешности при сжатии и обновлении вейвлет-декомпозиции.

2.5. Выводы.

ГЛАВА 3. Разработка инструментального средства приближенной обработки запросов на основе ДНВПХ с произвольной длиной измерения.

3.1. Обоснование создания ИС.

3.2. Концептуальное описание системы.

3.2.1. Функциональное описание системы.

3.2.2. Структурное описание системы.

3.2.3. Описание архитектуры системы.

3.3. Проектирование базы данных.

3.4. Проектирование прикладной части ПО.

3.5. Выводы.

ГЛАВА 4. Использование разработанного средства для создания компонента OLAP-модуля системы "Надзор за заболеваемостью".

4.1. Описание предметной области.

4.2. Реализация подсистемы приближенной обработки запросов.

4.2.1. Комплекс технических средств и топология.

4.2.2. Комплекс программных средств.

4.2.3. Многомерные кубы.

4.3. Анализ результатов использования подсистемы приближенной обработки запросов.

4.4. Выводы.

ВЫВОДЫ.

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

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

В настоящее время распространены три основных подхода к приближенной обработке запросов: методы выборки, методы гистограмм и методы вейвлет-преобразования. Однако существующие подходы обладают рядом недостатков, что сдерживает их применение на практике. Методы выборки и гистограмм ориентированы на получение агрегатных значений с большим количеством элементов. Вычисление же единичных значений или сумм с небольшим числом слагаемых сопровождается значительной погрешностью. Более того с ростом размерности данных (а в современных ОЬАР-системах по оценкам аналитиков количество измерений в кубах достигает 10-15) увеличивается стоимость построения и хранения приближенного представления, обеспечивающего приемлемую погрешность. В этой связи наиболее перспективным представляется подход на основе вейвлет-преобразования, позволяющий вычислять как единичные, так и суммарные значения на основе многомерных данных. Однако существующие методы накладывают ряд ограничений на структуру данных, не позволяют производить обновление значений без полного пересчета всего набора и не предоставляют точных методов оценки погрешностей.

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

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

В работе решаются следующие задачи:

1. Разработка метода вейвлет-преобразования Хаара г-мерного набора данных с произвольной длиной измерений.

2. Разработка метода восстановления исходного элемента и суммы элементов из сжатого хранилища данных с произвольной длиной измерения.

3. Разработка метода обновления сжатого хранилища данных без полного пересчета вейвлет-коэффициентов.

4. Разработка метода оценки погрешностей восстановления исходного элемента данных и суммы элементов.

5. Разработка инструментального средства приближенной обработки запросов.

6. Разработка ОЬАР-системы «Надзор за заболеваемостью» и анализ результатов использования предложенных методов.

Объект исследования. Объектом исследования настоящей работы являются системы оперативного анализа данных (ОЬАР-системы).

Предмет исследования. Предметом исследования являются процессы приближенной обработки запросов на основе вейвлет-преобразования в системах оперативного анализа данных.

Научная новизна. В работе получены следующие новые научные результаты:

1. Разработан метод нестандартного вейвлет-преобразования Хаара, учитывающий произвольную длину измерений, отличную от 2П, и позволяющий уменьшить объем хранимых вейвлет-коэффициентов до объема исходных значений. Доказана лемма о замещении усредненных вейвлет-коэффициентов на разных уровнях детализации вейвлет-преобразования, что позволило сократить количество операций чтения/записи.

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

3. Доказаны леммы и теорема о независимости расчета обновленных значений в разработанных алгоритмах дискретного нестандартного вейвлет-преобразования Хаара и на их основе предложен метод обновления имеющейся вейвлет-декомпозиции без пересчета ранее вычисленных вейвлет-коэффициентов.

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

Методы исследования. Исследования проводились на основе комплексного использования теории вейвлетов, теории вероятности, теории алгоритмов.

Практическая ценность полученных результатов. В настоящей работе для практического использования предложенных методов приближенной обработки запросов на основе вейвлет-преобразования и оценки погрешности восстановления значений разработано инструментальное средство. Оно позволяет сформировать приближенное представление многомерного набора данных (ОЬАР-куба) с произвольной длиной измерения по заданным критериям: допустимая прогнозируемая погрешность вычисления единичного значения, допустимая прогнозируемая погрешность вычисления суммы значений с учетом ее мерности, объем приближенного представления. На основе приближенного представления с помощью инструментального средства можно восстанавливать единичные и суммарные значения. Таким образом, разработанное инструментальное средство предоставляет возможность сформировать приближенное представление данных с прогнозируемой погрешностью и требуемым объемом, и осуществлять аналитическую обработку над ним, получая единичные либо суммарные значения. Приближенное представление при необходимости может быть обновлено. При этом не накладывается ограничение на длину измерений.

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

Публикации по теме. По материалам настоящей работы опубликовано 6 печатных работ, из них 4 — в научных журналах, рекомендуемых ВАК.

Апробация работы. Материалы работы были изложены автором на семинарах кафедры ИУ-5 МГТУ им. Н.Э. Баумана в 2008 и 2009 годах.

Структура диссертационной работы. В первой главе «Критический анализ существующих методов приближенной обработки запросов в ОЬАР-системах» приведено описание концепции приближенной обработки запросов, рассмотрены основные особенности таких систем. Приведен критический анализ существующих подходов на основе методов выборки, гистограмм и вейвлет-преобразования.

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

В третьей главе "Разработка инструментального средства приближенной обработки запросов на основе ДНВПХ с произвольной длиной измерения" разработан проект ИС приближенной обработки запросов на основе методологии объектно-ориентированного анализа и проектирования. Приводится концептуальное, функциональное и структурное описание системы, описание архитектуры ИС, а также формализованное описание схемы БД.

В четвертой главе "Использование разработанного средства для создания компонента ОЬАР-модуля системы "Надзор за заболеваемостью" приведено описание реализации разработанного средства, которое является частью аналитического модуля системы "Надзор за заболеваемостью". Исследованы результаты применения разработанного средства для приближенной обработки запросов.

ВЫВОДЫ

В качестве основных результатов работы определены следующие положения:

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

II

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

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

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

5. Разработано инструментальное средство, реализующее предложенные 1 методы приближенной обработки запросов на основе вейвлет преобразования, которое является частью аналитического модуля системы "Надзор за заболеваемостью".

6. Исследованы результаты использования разработанного инструментального средства и предложенных методов оценки погрешностей. Сжатие данных на 60% уменьшает время выполнения запросов в среднем на 50% при погрешности восстановления исходного элемента и суммы элементов хранилища данных, равной 15% и 5% соответственно.

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

1. Арлоу Д., Нейштадт A. UML 2 и Унифицированный процесс. Практический объектно-ориентированный анализ и проектирование. Второе издание: Пер. с англ.- СПб.: Символ-плюс, 2007,- 624 с.

2. Архипенков С. Я., Голубев Д.В., Максименко О. Б. Хранилища данных.-М.: Диалог-МИФИ, 2002.- 528 с.

3. Асеев М.Г., Баллюзек М.Ф., Дюк В.А. Разработка медицинских экспертных систем средствами технологий Data Mining // Datadiver. 2008. URL.http://www.datadiver.nw.ru (дата обращения 02.08.2008)

4. Боровков А. А. Теория вероятностей: Учеб. пособие для вузов.— 2-е изд., перераб. и доп.— М.: Наука. Гл. ред. физ.-мат. лит., 1986.- 432 с.

5. Буч Г., Рамбо Д., Якобсон И. Язык UML. Руководство пользователя: Пер. с англ.-М.: ДМК пресс, 2007.- 496 с.

6. Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем // Citforum.ru. 2008. URL.http://www.citforum.ru/database/case/index.shtml (дата обращения 14.07.08)

7. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. СПб.: Изд-во ВУС, 1999. - 208 с.

8. Гашков С.Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений. -М.: Дрофа, 2005. -320 с.

9. Гмурман В.Е. Теория вероятностей и математическая статистика. Изд. 4-е. Учеб. пособие для вузов.- М.: Высшая школа, 1972.- 368 с.

10. Гнеденко Б.В. Курс теории вероятностей: Учебник- Изд. 6-е, перераб. и доп.- М.: Наука, гл. ред. физ.-мат. лит., 1988.- 448 с.

11. Гордиенко И. OLAP. Часть II. Разведка на местности // Компьютера (М.).- 2002.- №9.- С. 53-59.

12. Григорьев Ю.А., Ухаров А.О. Вейвлет-сжатие в хранилищах данных OLAP // Информатика и системы управления (Благовещенск). 2008. -№4. - С.3-10.

13. Григорьев Ю.А., Ухаров А.О. Возможности приближенной аналитической обработки многомерных данных на основе вейвлет-преобразования // Проблемы полиграфии и издательского дела (М.). -2007. №1. - С.60-68.

14. Григорьев Ю.А., Ухаров А.О. Обзор концепции многомерной модели данных в технологии OLAP // Проблемы построения: и эксплуатации систем обработки информации и управления (М.). — 2006. №4. - С. 1530.

15. Григорьев Ю.А., Ухаров А.О. Распределение ошибки при вейвлет-сжатии в хранилищах данных OLAP // Информатика и системы управления (Благовещенск). 2008. - №3. - С.3-14.

16. Григорьев Ю.А., Ухаров А.О., Плутенко А.Д. Использование вейвлет-преобразования для приближенной аналитической обработки многомерных данных // Информатика и системы управления (Благовещенск). 2008. -№1. - С.3-11.

17. Добеши И. Десять лекций по вейвлетам: Пер. с англ.- Ижевск: НИЦ Регулярная и хаотическая динамика, 2001. 464 с.

18. Дьяконов В. Вейвлеты. От теории к практике.- М.: СОЛОН Р, 2004.400 с.

19. Заботнев М.С. Методы представления информации в разреженных гиперкубах данных // OLAP.ru. 2008. URL.http://www.olap.ru/basic/theory.asp (дата обращения 19.01.08)

20. Инмон У. Типы Хранилищ данных // ISO.ru. 2001. URL. http://www.iso.ru/journal/articles/181.html (дата обращения 01.08.2007)

21. Истомина Т.В.,Чувыкин Б.В., Щеголев В.Е. Применение теории wavelets в задачах обработки информации: Монография. — Пенза: Изд-во Пенз. гос. ун-та, 2000. 188 с.

22. Ким. В. Три основных недостатка современных хранилищ данных // Открытые системы (М.).- 2003.- №2.- С.46-52.

23. Киммел П. UML. Универсальный язык программирования: Пер. с анг. -М.: НТ-Пресс, 2008.- 272 с.

24. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах // Открытые системы (М.).- 1997.- № 4.- С. 41-44.

25. Кнут Д. Искусство программирования, том 1. Основные алгоритмы: Пер. с анг. 3-е изд.- М.: Вильяме, 2006. - 720 с.

26. Кобринский Б.А. Ретроспективный анализ медицинских экспертных систем // Новости искусственного интеллекта (М.).- 2005.- №2,- С. 6-17.

27. Кудрявцев Ю. Обзор алгоритмов MOLAP // Citforum.ru. 2007. URL. http://www.citforum.ru/consulting/Bl/molapoverview (дата обращения 03.12.07)

28. Кузнецов С. Крупные проблемы и текущие задачи исследований в области баз данных // Citforum.ru. 2007. URL. http://www.citforum.ru/database/articles/problems (дата обращения 17.09.2007)31.

29. Леоненков A.B. Объектно-ориентированный анализ и проектирование с использованием UML и IBM Rational Rose. -M.: Бином, 2006.- 320 с.

30. Леоненков A.B. Самоучитель UML2.-OT6.: БХВ-Петербург, 2007.-576 с.33* Леоненков A.B. Самоучитель UML.-СПб.: БХВ-Петербург, 2002.-304 с. 34. Малла С. Вэйвлеты в обработке сигналов.-М.: Мир, 2005.-672 с.

31. Мартиросян С. OLAP-системы: обзор лидеров рынка // Gnews.ru. 2006. URL. http://cnews.ru/reviews/index.shtml72006/07/20/2063102 (Дата обращения 2.02.2007)

32. Математическая статистика: учеб: для вузов/ В.Б. Горяинов и др.; Под ред. B.C. Зарубина, А.П. Крищенко.- 2-е изд.- М.: Изд-во МГТУ им. Н.Э. Баумана; 2002.- 424 с.

33. Мацяшек JI.Ä. Анализ и проектирование информационных систем с помощью UML 2.0: Пер. с англ.- М.: Изд. Дом Вильяме, 2008. 816 с.

34. Методология IDEFlx. Стандарт. Русская версия.- М.: Метатехнология, 1993.- 108 с.

35. Некипелов Н., Арустамов А. Методика анализа данных // Basegroup. 2008. URL. http://www.basegroup.ru/library/methodology/base/ (дата обращения 02:08.2008)

36. Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. М.: МГУ, 1992. - 140 с.

37. Объектно-ориентированный анализ и проектирование с примерами приложений/Г. Буч и др.: Пер. с англ.- М.: Вильяме, 2008,- 720 с.

38. Овчинников В. Г. Методология проектирования автоматизированных информационных систем. Основы системного подхода. М.: Компания Спутник +, 2005.- 286 с.

39. Петухов А.П. Введение в теорию базисов всплесков. СПб.: Изд-во СПбГТУ, 1999. - 132 с.

40. Сахаров А. А. Концепция построения и реализации информационных систем, ориентированных на анализ данных // СУБД (М.).- 1996. № 4.-С. 55-70.

41. Сахаров А. А. Принципы проектирования и использования многомерных баз данных (на примере Oracle Express Server) // СУБД (М.).- 1996.- № 3. С. 44-59.

42. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB.-M.:1. ДМК пресс, 2005.- 304 с.

43. Спирли Э. Корпоративные хранилища данных. Планирование, разработка, реализация: Пер. с англ.- М.: Изд. дом Вильяме, 2001. —Том 1.- 400 с.

44. Стивене P. Visual Basic. Готовые алгоритмы: Пер. с анг.- М.: ДМК, 2000.- 377 с.

45. Столниц Э., Дероуз Т., Салезин Д. Вейвлеты в компьютерной графике. Теория и приложения: Пер. с англ.- Ижевск: НИЦ Регулярная и хаотическая динамика, 2002. 272 с.

46. Стулов А. Особенности построения информационных хранилищ //OSP.ru: Открытые системы. 2007. URL. http://www.osp.ai/os/2003/04/182942/ (дата обращения 23.05.2007)

47. Управление научными данными в следующем десятилетии/ Д. Грэй и др. // ACM SIGMOD Record.- 2005.- Vol. 34(4).- P. 34-41.

48. Ухаров А.О. Использование вейвлет-преобразования для представления многомерных данных в системах OLAP // Интеллектуальные технологии и системы (М.). 2005. - №7. - С.256-271.

49. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии: Пер. с англ.- М.: Триумф, 2003. 320 с.

50. Фалевич Б.Я. Теория алгоритмов. -М.: Машиностроение, 2004. 160 с.

51. Фаулер М., Скотт К. UML. Основы: Пер. с англ.- СПб.: Символ-Плюс, 2002. 192 с.

52. Федоров А., Елманова Н. Введение в OLAP // КомпьютерПресс (М.).-2000.-№3.- С. 37-42.

53. Фрост Р., Дей Д, Слайк К.В. Базы данных. Проектирование и разработка.- M.: HT Пресс, 2007.- 592 с.

54. Чуи Ч. Введение в вейвлеты: llep. с анг.-М.: Мир, 2001 г. 412 с.

55. Шапот М. Интеллектуальный анализ данных; в системах поддержки принятия решений // Открытые системы (М.).- 19981- №1,- С. 30-35.

56. Шроэк М. Зинн Д. Интегрированная аналитика. Как извлечь максимальную выгоду из ERP-систем // Gitforum.ru. 2007. URL. http://www.citforum.ru/database/articles/erp-system (дата обращения 17.09.2007)

57. Шуленин А. Масштабируемость аналитических сиситем // Windows IT Pro (М.).- 2002. № 1. - С. 15-22.

58. Щавелёв JI.B. Оперативная аналитическая обработка данных: концепции и технологии// Citforum.ru. 1999. URL. http://www.citforum.ru/seminars/cis99/sch.shtml (дата обращения 09.04.2007)

59. A Taxonomy of Dirty Data / W. Kim and other. // Data Mining and Knowledge Discovery (Hingham).- 2003.- Vol. 7(1).- P. 81-99.

60. Aboulnaga A., Chaudhuri S. Self-tuning Histograms: Building Histograms Without Looking at Data // Proceedings of the 1999 ACM SIGMOD international conference on Management of data;- New York, 1999.- P. 181192.

61. Acharya S., Gibbons P. В., Poosala V. Congressional Samples for Approximate Answering of Group-By Queries // ACM SIGMOD Record.- 2000.- Vol. 29(2).- P. 487-498.

62. Acharya S., Gibbons P. В., Poosala V. Join Synopses for Approximate Query Answering//ACM SIGMOD Record.- 1999.- Vol. 28(2).- P. 275-286.

63. Aftari F.N., Lekeas P.V., Li С. Answering Aggregation Queries on Hierarchical Web Sites Using Adaptive Sampling // Proceedings of the 14th ACM international conference on Information and knowledge management.- New York, 2005.- P. 237-238.

64. Babcock В., Chaudhuri S. Das G. Dynamic sample selection for approximate query processing // Proceedings of the 2003 ACM SIGMOD international conference on Management of data.- New York, 2003.- P. 539-550.

65. Bruno N., Chaudhuri S., Gravano L. STHoles: A Multidimensional Workload-Aware Histogram // Proceedings of the 2001 ACM SIGMOD international conference on Management of data.- New York, 2001.- P. 211222.

66. Chakrabarti K., Garofalakis M., Rastogi R. Approximate query processing using wavelets // The VLDB Journal — The International Journal on Very Large Data Bases.- 2001.- Vol. 10(2).- P. 199-223.

67. Chaudhuri S., Das G., Datar M. Overcoming Limitations of Sampling for Aggregation Queries // Proceedings of the 17th International Conference on Data Engineering.- Washington, 2001.- P. 534-542.

68. Chaudhuri S., Das G., Narasayya V. Optimized Stratified Sampling for Approximate Query Processing // ACM Transactions on Database Systems (TODS).- 2007.- Vol. 32(2).- P. 17-25.

69. Codd E. F., Codd S. В., Salley С. T. Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate // Informatik. 2006. URL. Http://www.informatik.uni-jena.de (дата обращения 17.10.2006)

70. Das G. Sampling Methods in Approximate Query Answering Systems // Uta.edu. 2008. URL. http://ranger.uta.edu/~gdas/website-pages/preprints-papers/data-warehouse.pdf (дата обращения 17.04.2008)

71. Data Warehouse Design Solutions / C. Adamson and other.- Hoboken: Wiley, 1998.- 523 p.

72. ERWin'Methods Guide / bogie Works Inc.- Princeton, 1997. 105 p.

73. Fast; Small-Space Algorithms for Approximate Histogram Maintenance / A. Gilbert and. other. // Proceedings of the thiry-fourth annual ACM symposium on Theory of computing.- Motreal, 2002.- P. 389-398.

74. Foote К. E., Huebner D. J. Error, Accuracy, and Precision // Colorado.edu. 2000: URL. http://www.colorado.edu/geography/gcraft/notes/error/error.html (дата обращения 02.08.2008)

75. Forsman S. OLAP Council White Paper // OLAPCouncilicom. 2007. URL. http://www.olapcouncil.org/research/whtpaply.htm (дата обращения 21.2.2007)

76. Franklin M., Halevy A., Maier D. From Databases to Dataspaces: A New Abstraction for Information Management // SIGMOD Record.- 2005.- Vol. 34(4).- P. 27-33.

77. Fryzlewicz P. Unbalanced Haar technique for nonparametric function estimation // wavelet.org. 2007. URL. http://www. wavelet. org/phpBB2/viewtopic.php?t=l06565 (дата обращения 17.09.2007)

78. Garofalakis M. Wavelet-Based Approximation Techniques in Database Systems // IEEE Signal Processing Magazine.- 2006.- VoL 23(6).-P. 54-58.

79. Garofalakis M., Gibbons P.B. Probabilistic Wavelet Synopses // ACM Transactions on Database Systems (TODS).- 2004.- Vol. 29(1).- P. 43-90.

80. Garofalakis M., Gibbons P.B. Wavelet Synopses with Error Guarantees // Intel-Research. 2007. URL. http://www.pittsburgh.mtel-research.net/people/gibbons/papers/wavelets-sigmod02.pdf (дата обращения 17.04.07)

81. Garofalakis M., Kumar A. Deterministic Wavelet Thresholding for Maximum Error Metrics // Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.- New York, 2004.-P. 166-176.

82. Gibbons P. B. Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports // Proceedings of the 27th International Conference on Very Large Data Bases.- San Francisco, 2001.- P. 541-550.

83. Gibbons P., Matias Y., Poosala V. Fast Incremental Maintenance of Approximate Histograms // ACM Transactions on Database Systems (TODS).- 2002.- Vol. 27(3).- P. 261-298.

84. Gibbons P.B., Matias Y. New Sampling-Based Summary Statistics for Improving Approximate Query Answers // Proceedings of the 1998 ACM SIGMOD international conference on Management of data.- New York, 1998.- P. 331-342.

85. Gunopulos D., Kollios G., Tsotras V. Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes // ACM SIGMOD Record.- 2000.- Vol. 29(2).- P. 463-474.

86. Haas P.J. Large-Sample and Deterministic Confidence Intervals for OnlineAggregation // Proceedings of the Ninth International Conference on Scientific and Statistical Database Management.- Washington, 1997.-P. 51-63.

87. Helberg С. Pitfalls of Data Analysis // Execpc.com. 2008. URL. http://www.My.execpc.com /-helberg/ (дата обращения 02.08.2008)

88. Hellerstein J. M., Haas P.J., Wang HJ. Online Aggregation // Proceedings of the 1997 ACM SIGMOD international conference on Management of data.-New York, 1997.-P. 171-182.

89. Holt J. UML (Unified Modelling Language) for Systems Engineering.-Stevenage: Institution of Engineering and Technology, 2001.- 296 c.

90. Inmon W.H. Building the Data Warehouse. Fourth Edition.- Hoboken: Wiley, 2005.- 543 p.

91. Ioannidis Y. The History of Histograms // Proceedings of the 29th international conference on Very large data bases.- Berlin, 2003.- Vol. 27 (l).-P. 19-30.

92. Ioannidis Y., Christodoulakis S. On the propagation of errors in the size of join results // Proceedings of the 1991 ACM SIGMOD international conference on Management of data.- New York, 1991.- P. 268-277.

93. Ioannidis Y., Poosala V.: Balancing Histogram Optimality and Practicality for Query Result Size Estimation // Proceedings of the 1995 ACM SIGMOD international conference on Management of data.- New York, 1995.- P. 233244.

94. Jagadish H. V., Jin H., Ooi B. C., Tan K.-L. Global Optimization of Histograms // Proceedings of the 2001 ACM SIGMOD international conference on Management of data.- Santa Barbara, 2001.- P. 223-234.

95. Kimball R. A Dimensional modeling // DBMS Magazine. 2007. URL.http://www.dbmsmag.com (дата обращения 08.03.2007)

96. Kimball R. Help for Hierarchies // DBMS Magazine. 2007.

97. URL.http://www.dbmsmag.com (дата обращения 08.03.2007)

98. Kimball R., Ross M. The Data Warehouse Toolkit: The Complete Guide to Dimensional Modeling. Second Edition.- Hoboken: Wiley, 2002.- 464 p.

99. Koudas N., Muthukrishnan S., Srivastava D. Optimal Histograms for Hierarchical Range Queries // Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.- Dallas, 2000.-P. 196-204.

100. Lee J.-H., Kim D.-H., Chung C.-W. Multi-Dimensional Selectivity Estimation Using Compressed Histogram Information // ACM SIGMOD Record.- 1999.- P. 205-214.

101. Lemire D. Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes // Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research.- Toronto, 2002.- P. 6-7.

102. Luo J., Zhou J., Zhang Y. Selectivity Estimation by Batch-Query based Histogram and Parametric Method // Proceedings of the eighteenth conference on Australasian database.- Durlinghurst, 2007.- Vol. 63.- P. 93102.

103. Lynch J. F. Analysis and Application of Adaptive Sampling // Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.- New York, 2000.- P. 260-267.

104. Matias Y., Vitter J.S., Wang M. Wavelet-Based Histograms for Selectivity Estimation // The IBM Research.com. 2007. URL. http://www.research.ibm.com/people/rn/minwang/publications/sigmod98.pdf (дата обращения 21.11.07)

105. MDX Description // Microsoft Developer Network. 2007. URL. http://msdn.microsoft.com/en-us/library/aa216767(SQL.80).aspx (дата обращения 13.06.2007)

106. Muralikrishna M., DeWitt D. Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries // ACM SIGMOD.1998.-Vol. 1(1).-P. 28-36.

107. Nailen R. Does precision imply accuracy? // BNet.com. 2008. URL. http://www.findarticles.eom/p/articles/miqa3726/is200105 (дата обращения 02.08.2008)

108. Optimal Histograms with Quality Guarantees / H. V. Jagadish and other. // Proceedings of the 24rd International Conference on Very Large Data Bases.- San Francisco, 1998.- P. 275-286.

109. Pendse N. Database Explosion // Olap Report. 2006. URL. http://olapreport.com (дата обращения 11.11.2005)

110. Pendse N. Multidimensional Data Structures // Olap Report. 2006. URL. http://olapreport.com (дата обращения 19.03.2006)

111. Pendse N. The OLPA Survey 5 // Olap Report. 2006. URL. http://olapreport.com (дата обращения 15.11.2005)

112. Poosala V., Ganti V., Ioannidis Y. Approximate Query Answering using Histograms // Journal of Intelligent Information Systems.- 2002.- Vol. 19(2).-P. 145-167.

113. Poosala V., Ioannidis Y. Histogram-Based Approximation of Set-Valued Query Answers // Proceedings of the 25th International Conference on Very Large Data Bases.- San Francisco, 1999.-P. 174-185.

114. Poosala V., Ioannidis Y. Selectivity Estimation Without the Attribute Value Independence Assumption // Proceedings of the 23rd International Conference on Very Large Data Bases.- San Francisco, 1997.- P. 486-495.

115. Poosala V., Ioannidis Y., Haas P. Improved Histograms for Selectivity Estimation of Range Predicates // ACM SIGMOD Record.- 1996.- Vol. 25(2).- P. 294-305.

116. Potgieter. J. OLAP Data Scalability // Information-management.com. 2006. URL. http://www.information-management.com/infodirect/20031031/763 6-l.html (дата обращения 10.12.2006)

117. Prasad Y. Z., Deshpande M., Naughton J.F., Shukla A. Simultaneous Optimization and Evaluation of Multiple Dimensional Queries // ACM SIGMOD Record.- 1998.- Vol. 27(2).- P. 271-282.

118. Raghuveer M. Rao, Ajit S. Bopardikar. Wavelet Transforms: Introduction to Theory & Applications.-Boston:Prentice Hall PTR, 1998. 310 p.

119. Redbook. Data Modeling Techniques for Data Warehousing // IBM.com. 2008. URL. http://www.redbooks.ibm.com (дата обращения 12.02.2008)

120. Runapongsa К., Nadeau T.P., Teorey T.J. Storage estimation for Multidimensional aggregates in OLAP // Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research.- Mississauga, 1999.- P.10-11.

121. Sarawagi S. Indexing Olap Data // Bulletin of the IEEE Computer Society Technical Committee on Data Engineering.- Los Alamitos, 1996.- P. 1-9.

122. Sherman R. Data Integration Advisor: The Enterprise Data Warehouse Strikes Again. Part 1 // DM Review. 2006. URL.http://www.athena-solutions.com/library-dmreview.shtml (дата обращения 11.05.2006)

123. Soni S., Kurtz. W. Analysis Services: Optimizing Cube Performance Using Microsoft SQL Server 2000 Analysis Services // Unisys. 2006. URL http://www.unisys.com (дата обращения 03.01. 2006)

124. Thomsen E. OLAP Solutions: Building Multidimensional Information Systems. Second Edition.- Hoboken: Wiley, 2005,- 728 p.

125. Vitter J. F., Wang M., Iyer B. Data Cube Approximation and Histograms via Wavelets // Proceedings of the seventh international conference on Information and knowledge management-Bethesda, 1998.- P. 96-104.

126. Vitter J.S., Wang M. Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets // Proceedings of the 1999 ACM SIGMOD international conference on Management of data.- New York, 1999:- P. 193-204.

127. Vonesch C., Unser M. A Fast Thresholded Landweber Algorithm for Wavelet-Regularized Multidimensional Deconvolution // IEEE Transactions on Image Processing.- 2008.- Vol. 17 ( 4).-P. 539-549

128. Wang H., Sevcik K.C. A multidimensional histogram for selectivity estimation and fast approximate query answering // Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research.-Toronto, 2003.- 328-342.

129. Whitehorn M, Zare R., Pasumansky M. Fast Track to MDX.-Berlin: Springer, 2004.- 266 p.

130. Wu Y.L., Amr El Abbadi D.A. Using Wavelet Decomposition to Support Progressive and Approximate Range-Sum Queries over Data Cubes // Proceedings of the ninth international conference on Information and knowledge management.- MCLean, 2000.- P. 414-421.

131. Yen J., Zhong N., Pal S.K. Wavelet Analysis And Its Applications, And Active Media Technology // Proceedings Of The International Computer Congress 2004.- Beijing: Logistical Engineering University, 2004.-Vol.2.- P. 713-729.