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

правах рукописи

БОРОДИН Андрей Михайлович

РАЗРАБОТКА БЫСТРЫХ АЛГОРИТМОВ ДОСТУПА К МНОГОМЕРНЫМ ДАННЫМ В ОЬАР-СИСТЕМАХ

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

1 6 июн 2011

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

Новосибирск - 2011

4850079

Работа выполнена на кафедре «Автоматика и информационные технологии» ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина».

Научный руководитель: доктор тех. наук, профессор

ПОРШНЕВ Сергей Владимирович

Официальные оппоненты: доктор тех. наук, профессор

ЗЫКИН Сергей Владимирович

доктор тех. наук, профессор СЕДИНИН Валерий Иванович

Ведущая организация: Федеральное государственное унитарное

предприятие «Научно-производственное объединение автоматики им. академика H.A. Семихатова» Федерального аэрокосмического агентства

Защита состоится июня 2011 г. в часов минут на заседании диссертационного совета Д.219.005.02 при Государственном

образовательном учреждении высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики» по адресу 630102, г. Новосибирск, ул. Кирова, 86, ауд. 625.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного университета телекоммуникаций и информатики по адресу 630102, г. Новосибирск, ул. Кирова, 86.

Отзывы на автореферат просьба высылать по адресу: 630102, г. Новосибирск, ул. Кирова, 86, заместителю декана ИВТ Резвану И.И,

Автореферат разосланмая 2011 г.

Ученый секретарь диссертационного совета, к.т.н., доцент

И.И. Резван

Общая характеристика работы

Актуальность темы исследования. Сегодня разработка программных средств, предназначенных для хранения и обработки больших объемов разнородных данных, является одним из активно развиваемых направлений ИТ-отрасли, которые дают возможность проводить комплексный многомерный анализ больших объемов различного типа информации (финансовой, статистической, операционной и т.п.) и представлять полученные результаты в виде различных консолидированных отчетов. Основным инструментом, используемым для решения задач обработки многомерных данных, являются OLAP-системы (Online Analytical Processing (OLAP) - оперативная аналитическая обработка, русскоязычный синоним — аналитические информационные системы - АИС). OLAP-технология обработки информации, включающая составление и динамическую публикацию отчётов и документов.

Сегодня в соответствующем сегменте рынка программного обеспечения (ПО) представлено множество OLAP-систем различных производителей: от проприетарных систем (Microsoft Analysis Services, Oracle OLAP Option и т.п.) до свободного программного обеспечения с открытым программным кодом (Mondrian, Palo). Производительность любой СУБД, в том числе и OLAP-системы, напрямую зависит от эффективности применяемого метода доступа к данным - механизма поиска данных, используемых в определённом аналитическом запросе. Например, традиционный для СУБД метод индексирования данных <К,А>, где K={hvh2,..hD} - набор элементов из D иерархий {Hi,Н2>..Нп} реализуется следующими преобразованиями:

<p:K-+R',R' з[0,1],

ц \Н!-».«'.[O.iL^i^.-D,

<p(h) = d° ■ ц(й,) + dl ■ и2(Л,) + d2 • ц(А,) +...,d «1,d > 0.

Как следствие, количество отрезков из Л1, которые необходимо рассмотреть при расчёте агрегатного запроса Q{h), экспоненциально быстро увеличивается при увеличении размерности данных D.

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

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

з

пока не создано. В то же время необходимо отметить, что за прошедшие 30 лет активно велись работы по разработке теории и методов практического использования пространственного индексирования данных геоинформационных систем (ГИС). (Размерность данных ГИС принимает значение от 2 до 4). Здесь решён целый ряд проблем, связанных с организацией быстрого доступа к многомерным данным, в том числе разработаны эффективные а^гЛрИГМЬ1 пространственного индексирования. При этом задачи обработки данных, р* шаемые ГИС, в целом оказываются схожими с задачами обработки данных ОЬАР-систем.

В связи с этим, разработка на основе идей пространственного индексирования, используемых в ГИС, алгоритмов доступа к многомерным данным в ОЬАР-системах, зависимость вычислительной сложности которых от размерности данных не выше полиномиальной, является актуальной задачей. (Далее, проводя аналогию с быстрым преобразованием Фурье, для краткости будем называть данные алгоритмы быстрыми алгоритмами доступа к многомерным данным.)

Объект исследования: методы анализа многомерных данных.

Предмет исследования: алгоритмы доступа к многомерным данным в ОЬАР-системах.

Цель диссертационной работы: разработка быстрых алгоритмов доступа к многомерным данным в ОЬАР-системах, основанных на использовании пространственных индексов.

Для достижения поставленной цели решаются следующие основные задачи исследования:

1. Провести анализ методов доступа к данных! в ГИС-системах с точки зрения возможности их использования в ОЬАР-системах.

2. Разработать быстрые алгоритмы доступа к многомерным данным АИС, основанные на принципах пространственного индексирования данных ГИС.

3. Получить теоретические оценки эффективности быстрых алгоритмов доступа к многомерным данным АИС.

4. Разработать программные реализации быстрых алгоритмов доступа к многомерным данным АИС.

5. Провести анализ результатов внедрения программных реализаций быстрых алгоритмов доступа к многомерным данным АИС.

Методы исследования. В работе были использованы методы теории вероятности, математической статистики, теории кодирования, теории параллельного программирования, теории систем управления базами данных (СУБД).

Научная новизна полученных результатов. К основным новым результатам, полученным в диссертации, можно отнести следующие:

1. Обоснование возможности и целесообразности использования пространственных индексов, применяемых в ГИС-системах, для индексирования данных в OLAP-системах.

2. Быстрые алгоритмы доступа к многомерным данным АИС, основанные на принципах пространственного индексирования данных ГИС.

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

Практическая значимость работы

1. Разработана программная реализация быстрых алгоритмов доступа к многомерным данным АИС - открытая программная библиотека «Индексирование многомерных классифицированных данных» (ИМКД), которая использована при разработке ПК «САПФИР», программной платформы (ПП) «Сектор», ПК «Карбон». Анализ результатов ее использования подтверждает высокую эффективность предложенного в диссертации подхода.

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

3. Описаны особенности практического применения пространственного индексирования и структурирования запросов, а также их использования для решения типовых задач OLAP-систем.

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

На защиту выносятся:

1. Быстрые алгоритмы доступа к данным OLAP-систем, основанные на методах пространственного индексирования данных ГИС.

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

3. Теоретические и экспериментальные результаты оценки эффективности быстрых алгоритмов доступа к данным АИС.

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

Внедрение результатов диссертационного исследования

Результаты диссертационного исследования использованы в ООО «Ок-тоника», ООО «Научно-производственное объединение «Сапфир» при разработке программной библиотеки «ИМКД», ПК «САПФИР», ПК «Карбон» и ПП «Сектор», а также в ФГОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина» в учебном процессе при под-

готовке бакалавров и магистров по направлению «Информатика и вычислительная техника».

. Результаты диссертационного исследования были включены в инновационный проект, представленный на конкурсе, проводимом в 2010 г. Фондом содействия развитию малых форм предприятий в научно-технической сфере. По результатам конкурса проект стал победителем программы «Участник Молодежного Научно-Инновационного Конкурса» («УМНИК») 2010 г.

Апробация работы

Материалы работы докладывались на следующих научных конференциях: Международной научно-ггра^-пгческой конференции «СВЯЗЬ-ПРОМЭКСПО 2008», Екатеринбург, 6-8 м« 2008 г.; Седьмой Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур», Томск, 2-5 сентября 2008 г.; Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2009», Екатеринбург, 17—19 марта 2009 г.; Межвузовской научной конференции по проблемам информатики «СПИСОК 2009», Екатеринбург, 20-23 апреля 2009 г.; Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2010», Екатеринбург, 5-7 мая 2010 г.

Публикации по теме диссертации. По результатам исследований опубликовано 8 печатных работ, из которых в рекомендованных ВАК РФ периодических изданиях - 4, получено свидетельство о регистрации электронного ресурса, а также свидетельство о регистрации программы для ЭВМ.

Структура диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованных источников, содержащего 105 наименований, и 2-х приложений. Общий объем работы составляет 163 страницы, в том числе 26 рисунков, 8 таблиц.

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

В первой главе рассмотрено современное состояние OLAP-систем и ГИС, в том числе:

1) Проведен сравнительный анализ данных ГИС и OLAP-систем, позволивший сделать обоснованный вывод о том, что, в целом, алгоритмы доступа к данным, используемые в ГИС, решают задачи, схожие с задачами доступа к данным в АИС. Отмеченное сходство позволило выдвинуть гипотезу о том, что использование этих алгоритмов в OLAP-технологиях позволит увеличить скорость доступа к данным. Однако, очевидно, что они не могут быть применены непосредственно ввиду различий в структуре ключей индексируемых данных. В этой связи сделан обоснованный вывод о необходимости разработки соответствующих подходов, позволяющих адаптировать методы доступа к данным, используемым в ГИС, к технологиям OLAP.

2) Рассмотрены алгоритмы доступа к данным в ГИС (R-дерево, R*-дерево, Ra^-дерево, VAM-Split алгоритм, KDB-дерево) и СУБД.

3) Проведен сравнительный анализ OLAP и OLTP (Online transactional processing - оперативная обработка транзакций) подходов, результаты которого позволили сделать обоснованный вывод о том, что целесообразна разработка динамического алгоритма индексирования аналитических данных, объединяющего функциональность OLAP-систем и OLTP-систем.

4) Сформулированы основные задачи диссертационного исследования.

Во второй главе разработаны быстрые алгоритмы доступа к данным АИС, основанные на использовании пространственных индексов.

На первом этапе разработки быстрых алгоритмов доступа к данным АИС предложен способ преобразования аналитических данных и запросов, соответственно, в пространственные данные и запросы. Для этого поставлена и решена задача отображения иерархии аналитических данных на числовую ось. (Пример иерархии измерения аналитических данных, используемой в ПК «САПФИР» представлен на рис. 1).

Рисунок 1. Пример иерархии измерения аналитических данных, используемой в ПК

«САПФИР»

Рассматриваемая задача формулируется следующим образом. Дана иерархия Н, состоящая из элементов Ь\._х и имеющая корневым узлом /г,- (рис. 2). Необходимо сопоставить каждому элементу иерархии отрезок где

i Имя

& ii ода

Все

— ti 213 Начислен«! на выплаты по оплате труда

ал <Ь, а^Ъ, е[0,1]. Для любых двух элементов иерархии кх и 1гу, если элемент Их в иерархии является потомком ку, то ах> ау и ¿>х < Ъу. Если элементы Их и ку являются несвязанными элементами иерархии, то [яЛА] П = 0: корневому элементу к,- ставится в соответствие отрезок [Мт2,Мах7\, где Мт2 и МахХ- минимальное и максимальное число, имеющее представление в выбранном типе данных #(целые или действительные).

Для решения данной задачи предложено использовать следующие алгоритмы, ставящие в соответствие каждому элементу кс, отрезок [д„6,] по известному отрезку [ар, ¿>р] и номеру i.

-----А/

И

■ ги • !и ;)

h- -[- h. •■ *5

* "А

MinZ

MaxZ

Ч а, Ьх Ъу

Рисунок 2. К постановке задачи отображения элементов иерархии на числовую ось

1. Рекурсивный алгоритм отображения иерархии на числовую ось (РАОИ) (рис. 3), приведенный ниже в виде псевдокода:

РАОИ для узла иерархии кр с границами ар, Ьр Вычислить (Ьс Переменная С = ар Для каждого ¡гх дочернего Нр ах = С+с1х Ьх - С+2-(1х

Вызвать РАОИ для Л„ а„Ьх С=С+2-с1х Конец цикла Конец алгорипта РАОИ

<*>.

a-) bо

н—I—I-

аг Ъг

н—(-

ч—ъ

Ор сп Ъ\ ОпЪп ЬР

Рисунок 3. Иллюстрация рекурсивного алгоритма отображения иерархии на числовую ось Здесь ¿х вычисляется по формуле

где ар, Ьр - границы элемента, для дочерних элементов которого проводится отображения, п - количество дочерних элементов. При отображении корневого элемента иерархии аг = Мт2, Ь, = Мах!.

2. Линейный алгоритм отображения иерархии на числовую ось (ЛАОИ) (рис. 4), приведенный ниже в виде псевдокода:

ЛАОИ для иерархии с корневым элементом кг Переменная С = М'т2 Вычислить (¿с

Вызвать операцию маркировки для узла Иг Конец алгоритма ЛАОИ Операция маркировки для узла Их ах = С С = С + (1х

Для каждого элемента Ну дочернего в Их вызвать операцию маркировки для Ну Конец цикла Ьх = С С-С+(1х

Конец операции маркировки

Здесь длина сЬс вычисляется по формуле:

Рисунок 4. Иллюстрация линейного алгоритма отображения иерархии на числовую ось

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

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

Мах2~Мт2

где .(V- общее количество элементов иерархии.

" -'Ъи «12^12 '112 / / /

"Ьо

где/: - коэффициент расширения,/ > 1,1, -длина отрезка, соответствующего у'-тому уровню иерархии, для каждого пустого отрезка выделяется не больше //' от оставшегося свободного места.

Так как максимальное число отрезков на выбранном интервале, на которые можно спроецировать элементы иерархии, 1пшх, растёт линейно с расширением то, используя ЛАОИ или РАОИ, можно, как минимум, удвоить количество дочерних элементов для каждого из узлов иерархии при условии, что сЬс > те (/ие-машинный эпсилон). Этого оказывается достаточно для решения практических задач по динамическому расширению иерархии.

Далее рассмотрены методы внутристраничного индексирования, применимые, когда физическая организация памяти системы требует использования древовидной структуры с большим фактором ветвления. Здесь, в частности, получены оценки количества узлов дерева ОА, которые необходимо рассмотреть при выполнении запроса, который найдёт ровно одну запись данных:

ВЛ~Г-1о8^. (1)

Из (1), очевидно, что вне зависимости от М, значение ОА оказывается наименьшим при Р= 2,728 = 3. Таким образом, для поиска, эффективного по количеству рассмотренных узлов, необходимо минимизировать ветвление индексирующего дерева, либо оптимизировать поиск внутри одного узла, вместо линейного перебора .Р внутренних записей. Принимая во внимание полученный результат, а также то, что при использовании страничной организации памяти выбор Г значительно ограничивается техническими характеристиками используемого компьютера, становится понятной целесообразность использования для оптимизации перебора записей внутристраничного индексирования.

В этой связи проведен анализ методов поиска данных внутри страницы, в том числе: метод деления пополам и метод секущих, использующиеся для традиционного индекса БД на основе В+-дерева, метод поиска по кривым Пе-ано и Гильберта, метод вложенного Я*-дерева, методы БцЛ-декомпозиции и БяП-куб декомпозиции, и сделан вывод о том, что из всех рассмотренных методов наиболее эффективными оказываются методы БцЛ-декомпозиции и БцЛ-куб декомпозиции.

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

ю

чёта аналитических запросов за счет уменьшения количества обращений к дисковой памяти.

В третьей главе разработаны аналитические способы оценки предсказания эффективности при выполнении аналитических запросов R*-дерева, Ка*-дерева и KDB-дерева. В процессе разработки аналитического способа оценки введено понятие равномерно распределенный отрезок: отрезок s = [j0> 5,] является равномерно распределённым, если

e[0,l],s-0 <s,.s, =s0+lsln so -случайное число с равномерным законом распределения на интервале [o,1-|j|] и доказан ряд лемм и теорем.

Лемма 1. Вероятность р пересечения отрезков s = = та-

ких, что ¡j|,|?| - заданные числа, s и g - равномерно распределённые отрезки, и + s 1. Тогда р вычисляется по формуле

„ru ну М+Ы-МН-Н'-М2 'М-™- (i-H)(i-M) '

Лемма 2. Дано множество взаимно непересекающихся отрезков S = {j„jj.jw}, гдел, =[s0j,s1;], равномерно распределённый отрезок,

у = 1,2средняя длина которых равняется s. Пусть u = {ul,u2,.-.,«„} — множество, составленное из непересекающихся отрезков, таких, что каждый отрезок и, включает в среднем/отрезков из множества S (w, является выпуклой оболочкой нескольких Sj). При этом п - Nif, где N— достаточно велико, чтобы можно было не учитывать, что интервалов между отрезками на 1 больше, чем N. (Если N не кратно// = int (Л'//)+1,здесь int - функция, возвращающая значение целой части числа.) Тогда средняя длина отрезков, принадлежащих множеству U, ¡7 равна

- /-1 -U = --+ S.

N

Иллюстрация процедуры группировки отрезков множества S в отрезки множества U для N= 8, /= 3 приведена на рис. 5.

S1 S2 S3 S4 S5 S6 Sj SB

щ ¿72 иг

Рисунок 5. К лемме 2

Лемма 3. Вероятность Ьгс того, что подотрезок q = [?(,,?,] полностью включает отрезок $ = [*„,.$,], где ¡$|,|9| - заданные числа, ¿о

-случайное число с равномерньм законом распределения на интервале

[о,1-|.г|], до -случайное число с равномерным законом распределения на интервале [0,1-|*|] вычисляется по формуле

М-

1пс(\дЩ) =

если ,

1-И

0, если

Теорема 1. Количество узлов Л*-дерева, затронутых запросом д, может быть вычислено по следующей формуле:

-1

Где ^(о,|$|) = |5|, Р7(х + 1,|$|) = ^==+^г(х,|$|), х - номер уровня группировки,

N

я - средняя длина ребра узла по рассматриваемому измерению, Ы(х) = ■—■

Теорема 2. Количество узлов 11а*-дерева, затронутых запросом д, может быть вычислено по следующей формуле:

1 ( О , , , ч 0 I , . Л

1 [т-г („,( I 1М ТТ, ./„,/.. I 1\ I Л (3)

Теорема 3. Количество узлов КОВ-дерева, затронутых запросом д, вычисляется по следующей формуле

»■П/и)"

где

"п

На основании приведенных выше теорем предложено использовать в качестве количественного показателя эффективности отношение количества узлов, затронутых запросом д (вычисляемых, соответственно, по (2), (3), (4)), к ожидаемому количеству элементов Т, участвующих в расчёте результирующего агрегатного значения,

]• I

Например, для К.а*-дерева соответствующее выражение записывается следующим образом:

РА _ 1 ___/5-,

г" "Гй/И^М

Из (5) видно, что ЗА* имеет сложность Логарифм в данном

случае появляется вследствие границ сложения от 1 до И. Линейная зависи-

12

мость ОЛ* от N вызвана тем, что Г линейно зависит от N. Таким образом, можно говорить о том, что соотношение 1)Л'¡Т ~ /о^Л'. Иными словами, сложность расчёта запроса с фиксированным размером результирующей выборки растёт логарифмически с ростом N. При этом, как показано в разделе 3.5, для расчёта предполагаемой сложности выполнения запроса требуется сравнительно небольшой объём статистических данных.

Проведено тестирование модели эффективности Л*-дерева, в котором использовались данные налоговых поступлений БД ПК САПФИР, представляющей собой ОЬАР-систему, в которой реализована модель данных «звёздного» соединения. Данные были классифицированы по 8 измерениям. Общий объём данных составлял 1.96 миллионов записей. По составленному индексу данных рассчитывались запросы со случайными границами агрегации и агрегирующей функцией расчёта количества записей.

Здесь был использован следующий метод выбора случайных границ запроса. Иерархия каждого измерения разворачивалась в множество элементов без учёта иерархических связей. Из этого множества выбирался один случайный элемент, при этом вероятность его выбора была пропорциональна его весу. Эта операция производилась для каждого измерения данных. Таким образом формировалась граница рассчитываемого случайного запроса. Далее, если сформированный запрос имел пересечения с интервалом [А, Д] данного измерения, он отбрасывался как несущественный. Запросы, признанные значимыми, далее передавались для расчёта в индекс данных. При этом для каждого расчёта запроса подсчитывалось количество узлов, рассмотренных при выполнении запроса.

Затем для 11*-дерева рассчитывался целевой показатель Е - отношение предсказанной сложности выполнения запроса к фактической:

^■^фактич^схос

Целевой показатель рассматривался как последовательность, состоящая из 1000 случайных чисел, со средним значением С = 1,027 и среднеквад-ратическим отклонением 0,520. Гистограмма распределения обсуждаемой случайной последовательности представлена на рис. 6.

Рисунок, б. Частоты распределения случайной последовательности Е

Анализ распределения изучаемой случайной последовательности позволил выдвинуть гипотезу о возможности ее описания гамма-распределением с параметрами к= 5,39 и 9=0,2. Проверка данной гипотезы в соответствии с критерием согласия Пирсона подтвердила ее истинность (экспериментальное значение х2~ 20,13 оказалось меньше соответствующего критического значения Хкр2= 22,71, вычисленного для 22 интервалов, двух степеней свободы распределения и уровня статистической значимости 0,25).

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

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

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

В четвертой главе проведен анализ результатов практического применения разработанных в диссертации быстрых алгоритмов доступа к данным в ОЬАР-системах, в том числе в:

1) ПК «САПФИР», представляющем собой аналитическую систему. Система предназначена для решения всего спектра задач, возникающих при планировании бюджетов субъектов Российской Федерации (РФ).

2) ПП «СЕКТОР», предназначенной для организации распределённого сбора данных, валидации данных, в том числе решения проблемы обнаружения конфликтных строк данных, и передачи данных (в случае отсутствия

конфликтов) для последующего анализа в любую OLAP-систему, в качестве которой в большинстве практических случаев выступает ПК «САПФИР».

3) ПК «Карбон», предназначенном для экспорта данных, не только из IM «Сектор», но и из Microsoft Excel, Microsoft CRM, а также для получения данных из хранилищ более ранних версий ПК «САПФИР», которые не имеют механизмов доступа к данным, разработанным в рамках данной работы.

Отметим, что для решения задачи выявления конфликтных данных автором была разработана специализированная программная библиотека «ИМКД», позволяющая проводить обработку значительного объёма многомерных данных, в том числе на клиентской стороне АИС. Программная библиотека ИМКД состоит из двух основных модулей;

1. Модуля индексирования пространственных данных.

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

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

Модуль пространственного индексирования, реализующий быстрые алгоритмы доступа к многомерным данным АИС, предоставляет разработчику возможность управления набором многомерных пространственных данных, в том числе выполнения поиска по оконному запросу - поиск данных в диапазоне, заданном интервалами в нескольких измерениях. Работа этого модуля основана на алгоритмах проецирования иерархического классификатора аналитических данных на числовую ось, описанных в главе 2, а также алгоритмах, использующих разновидности индексирующей структуры R*-дерева. Объём памяти индексированных данных при этом, как показывают результаты экспериментов, увеличивается не более, чем на 10% от объёма изначальных данных. Алгоритм размещения индексированных данных адаптирован для применения на клиентских рабочих станциях и не требует серверного компьютера. Тестирование программной библиотеки «ИМКД» на тестовых наборах данных объёмом в 100 тысяч записей показал, что время поиска конфликтов не превышает 10 секунд при использовании компьютера с тактовой частотой 2 ГТц. Данная программная библиотека была использована при разработке ПП «СЕКТОР», ПК «Карбон».

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

Таблица 1. Сравнение производительности ПК «САПФИР» до и после внедрения быстрых алгоритмов доступа к данным ОЬАР-системах

Показатель производительности Результат до внедрения Результат после внедрения

1. Время расчёта агрегирующих запросов расчётной таблицы 1.1. Первое открытие 1.2. Следующие открытия 5 часов 5 часов 72 секунды 12 секунд

2. Время внесения изменений в ячейку таблицы более 1 минуты 4 секунды

3, Блокирование конкурирующих изменений данных Есть Нет

Из табл. 1. видно, что время расчёта агрегирующих запросов расчётной таблицы, в целом, сократилось, в том числе первое открытие - с 5 часов до 72 с, второе и последующие открытия - с 5 часов до 12 с, время внесения изменений - с одной минуты и более до 4 с.

Принимая во внимание существующую в последние годы тенденцию повышения производительности компьютеров за счет увеличения количества процессоров в вычислительной системе, проведена экспериментальная проверка метода параллельной загрузки данных в OLAP-системах. Для проведения эксперимента была реализована синхронизированная версия программной библиотеки «ИМКД». Данные загружались из MS SQL Server, связь с которым осуществлялась через 100 Мбит/с Ethernet. Загружаемые данные имели единственный атрибут типа decimal и были классифицированы по 12 измерениям.

200 -------

lso -—трщ

150 ......-

140 - в J

120.....—Лей

100

V&. 1ЩЯ

рш i li*

г Г;-'. 'Ж 1 _____

Ни

Л! Jl 1' 1 ш1.

1 набор (4-Ю записей) ^2нэборэ !2 ло2-506зэлйсвй)

Рисунок 7, Зависимость времени загрузки данных от числа процессоров Результаты эксперимента показали, что (см. рис. 7): - при загрузке 4 млн. записей данных, имеющих один атрибут типа decimal и классифицированных по 12 измерениям, время загрузки на 1 процессоре составило 182 секунды, на 2-х процессорах - 107 секунд, на 4-х процессорах - 83 секунды;

- при загрузке двух аналогичных по структуре наборов данных объёмом 2 млн. записей время загрузки на одном процессоре составило 185 секунд, на 2-х процессорах -92 секунды и на 4-х пропсеvu^a/w -71 —, „

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

Также проведен сравнительный анализ скоростей построения индексов и расчетов агрегатных запросов, выполняемых программной надстройкой Power Pivot, OLAP-системой, использующей быстрые алгоритмы доступа к данным, и OLAP-системы Jedox Palo на следующем наборе аналитических данных. Каждая запись набора характеризовалась четырьмя плоскими классификаторами. Каждый из классификаторов принимал одно из тысячи возможных значений. Требовалось построить индексирующую структуру и рассчитать 100 ООО агрегатных значений по первым двум классификаторам. При этом значения выбирались так, чтобы каждый элемент данных один раз попал в один из агрегатных запросов. Тестирование проводилось на системе с одним центральным процессором с тактовой частотой 1.7 ГТц, 2 Гб ОЗУ под управлением 32-х разрядной ОС Microsoft Windows ХР Professional Edition.

Результаты анализа показали, что на данных объемом до 250 тысяч записей эффективность OLAP-системы Jedox Palo сопоставима с другими рассмотренными АИС, однако на объёме данных в области 300 тысяч записей начинается резкое падение ее производительности. Похожая ситуация наблюдается и с OLAP-системой, использующей быстрые алгоритмы доступа к данным, на тестовом наборе данных только в районе 900 тысяч записей. Эффективность программной надстройки Power Pivot оказывается практически линейно зависящей от количества данных в исходном наборе, однако на объёмах более полумиллиона записей ее поведение становится нестабильным и проведение экспериментов оказывается невозможным. При этом несмотря на то, что программная надстройка Power Pivot решает более частную задачу (агрегации по плоским спискам), время, затрачиваемое этой системой на полное решение задачи оказывается больше, чем время решения задачи АИС на основе программной библиотеки «ИМКД», на всех объемах данных, на которых программная надстройка Power Pivot смогла решить эту задачу.

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

ки динамического алгоритма индексирования аналитических данных, объединяющего функциональность OLAP и ГИС-систем.

2.'Разработаны-быстрые., алгоритмы доступа к многомерным данным АИС, основанные на использовании принципов пространственного индексирования данных ГИС-систем.

3. Получены теоретические оценки эффективности разработанных алгоритмов доступа к многомерным данным АИС.

4. Разработаны программные реализации быстрых алгоритмов индексирования данных АИС, в том числе программная библиотека «Индексирование многомерных классифицированных данных».

5. Проведен анализ результатов внедрения разработанных программных реализаций быстрых алгоритмов доступа к многомерным данным АИС в ПК «САПФИР», ПК «Сектор», ПК «Карбон», свидетельствующий об эффективности развитых в работе подходов.

Публикации по теме диссертации

Статьи, опубликованные в журналах из списка ВАК

1. Бородин A.M. Использование пространственных индексов для обработки аналитических запросов и агрегирования многомерных данных в ИАС [Текст] / Бородин А.М, Поршнев C.B., Сидоров М.А. // Известия Томского политехнического университета. 2008. Т. 313. -№ 5. -С. 64-67.

2. Бородин A.M. Сравнительный анализ возможностей и скорости обработки многомерных данных программными средствами бизнес-аналитики на основе индексирующих структур основной памяти [Текст] / Бородин A.M., Поршнев C.B. // Научно-технические ведомости СПбГТУ. Серия «Информатика, Телекоммуникации, Управление». -№ 1(93). -2010. -С. 99-102.

3. Бородин A.M. О параллельном построении пространственных индексов основной памяти в OLAP-системах [Текст] / Бородин A.M., Поршнев C.B. // Научно-технические ведомости СПбГТУ. Серия «Информатика, Телекоммуникации, Управление». № 1(97). -2011. -С.72—74.

4. Бородин А.М. Аналитические способы оценки эффективности применения пространственных индексов в OLAP-системах [Текст] / Бородин A.M., Поршнев C.B. // Научно-технические ведомости СПбГТУ. Серия «Информатика, Телекоммуникации, Управление». № 2 (120).—2011. -С. 93-100.

Другие пубпикагрли

1. Бородин A.M. Технологии доступа к многомерным данным [Текст]/ Бородин A.M., Сидоров М.А. // Научные труды международной научно-практической конференции «СВЯЗЬ - ПРОМ 2008» в рамках 5го ЕвроАзиатского форума «СВЯЗЬПРОМЭКСПО 2008». -Екатеринбург: ЗАО «Компания Реал-Медиа», 2008. -С. 199-201.

2. Бородин А.М Агрегирование многомерных данных в аналитических системах на основе пространственных индексов [Текст] / Бородин А.М, Поршнев C.B., Сидоров М.А. // Сборник тезисов 7-й Российской конферен-

ции с международным участием «Новые информационные технологии в исследовании сложных структур». Томск, 2008. -С. 10.

3. Бородин A.M. Методы оценки эффективности R-TREE индекса агрегирующих запросов в OLAP-системах [Текст] / Бородин А.М, Поршнев C.B., Сидоров М.А. // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМ 2009» в рамках 6-го Международного форума «СВЯЗЬПРОМЭКСПО 2009», посвященного 150-легию со дня рождения изобретателя радио A.C. Попова. - Екатеринбург :УрТИСИ ГОУ ВПО «Сиб-ГУТИ», 2009. -С. 59-66.

4. Бородин A.M. Проблема агрегатных конфликтов данных в системах анализа многомерных данных [Текст] / Бородин A.M., Королёв A.B., Мирво-да С.Г.// Научные труды международной научно-практической конференции «СВЯЗЬ - ПРОМ 2010» в рамках 7го Евро-Азиатского форума «СВЯЗЬПРОМЭКСПО 2010». -Екатеринбург: ЗАО «Компания Реал-Медиа», 2010.-С. 229-231.

Свидетельства о регистрации электронного ресурса

1. Бородин A.M. Программная библиотека «Индексирование многомерных классифицированных данных» / Бородин A.M., Поршнев C.B., Мирвода С.Г.// Свидетельство об отраслевой регистрации № 14197 в отраслевом фонде электронных ресурсов науки и образования (госрегистрация № 50200900990 от 10.11.2009).

Свидетельства о регистрации программ для ЭВМ

1. Бородин А.М.Программный комплекс «Сапфир-3» /Ведьманов К.Г., Решетарь Д.Н., Кузьмин В.А., Бородин A.M.// Свидетельство о государственной регистрации программы для ЭВМ № 2009610771 от 3 февраля 2009.

Подписано в печать "17" мая 2011 г. Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд.л.1,6, заказ № 31, тираж 100 экз., ГОУ ВПО "СибГУТИ". 630102, г. Новосибирск, ул. Кирова, д. 86.

Список сокращений.

Введение.

Глава 1. Анализ проблемной ситуации. Постановка задач исследования

1.1. Современное состояние ОЬАР-систем.

1.2. Современное состояние геоинформационных систем.

1.3. Алгоритмы доступа к данным в ГИС системах.

1.4. Особенности организации методов доступа к данным в СУБД.

1.5. Постановка задач исследования.

Глава 2. Разработка быстрых алгоритмов доступа к данным в ОЬАР-системах, основанных на принципах пространственного индексирования

2.1. Алгоритмы преобразования аналитических данных и запросов в пространственные данные и запросы.

2.2. Внутристраничное индексирование в древовидных структурах.

2.3. Применение арифметического кодирования для сокращения длины пространственного ключа.

2.4. Быстрый алгоритм доступа к многомерным данным в ОЬАР-системах.

2.5. Методика группировки аналитических запросов.

2.6. Выводы.

Глава 3. Аналитические способы оценки эффективности быстрых алгоритмов доступа к многомерным данным в ОЬАР-системах.

3.1. Оценка количества узлов, затрагиваемых запросом при использовании 11*-дерева.

3.2. Оценка количества узлов, затрагиваемых запросом при использовании 11а*-дерева.

3.3. Оценка количества узлов, затрагиваемых зап осом при использовании KDB-дерева.

3.4. Оценка ожидаемой эффективности алгоритмов пространственного индексирования.

3.5. Уточнение модели оценки эффективности алгоритмов быстрого доступа к многомерным данным.

3.6. Оценивание точности способа оценки эффективности быстрых алгоритмов доступа к многомерным данным в OLAP-системах.

3.7. О битовых картах.

3.8. Обоснование подходов повышения эффективности быстрых алгоритмов доступа к многомерным данным в OLAP-системах.

3.9. Выводы.

Глава 4. Анализ результатов практического использования алгоритмов быстрого доступа к многомерным данным в OLAP-системах.

4.1. Анализ результатов использования быстрых алгоритмов доступа к многомерным данным в ПК «САПФИР».

4.2. Анализ результатов применения алгоритмов быстрого доступа к многомерным данным в ПП «Сектор».

4.3. Разработка на основе программной библиотеки «ИМКД» ПК «Карбон».

4.4. Сравнение производительностей OLAP-системы, использующей быстрые алгоритмы доступа к данным, OLAP-системы Jedox Palo и программной надстройки Power Pivot.

4.5. Выводы.

Актуальность темы исследования. Сегодня разработка программных средств, предназначенных для хранения и обработки больших объемов разнородных данных, является одним из активно развиваемых направлений ИТ-отрасли, которые дают возможность проводить комплексный многомерный анализ больших объемов различного типа информации (финансовой, статистической, операционной и т.п.) и представлять полученные результаты в виде различных консолидированных отчетов. Основным инструментом, используемым для решения задач обработки многомерных данных, являются OLAP-системы (Online Analytical Processing (OLAP) — оперативная аналитическая обработка, русскоязычный синоним — аналитические информационные системы — (АИС)), OLAP-технология обработки информации, включающая составление и динамическую публикацию отчётов и документов.

Сегодня в соответствующем сегменте рынка прикладного программного обеспечения (ПО) представлено множество OLAP-систем различных производителей [1]: от проприетарных систем (Microsoft Analysis Services [2], Oracle OLAP Option [3] и т.п. [4]) до свободного программного обеспечения с открытым программным кодом (Mondrian, Palo [5]).

Производительность любой СУБД, в том числе и OLAP-систем напрямую зависит от эффективности применяемого метода доступа к данным — механизма поиска данных, используемых в определённом аналитическом запросе [2]. Например, традиционный для СУБД метод индексирования данных <К^4>, где K={h\,Ii2,.hD} - набор элементов из D иерархий {H\,H2,.HD} реализуется следующими преобразованиями:

OjiHj->^,[0,1],у=1,2,.Д p(h) = d° -ц (/?,) + dl-и2 (h2) + d2 -цСЛ,) + ., d «\,d> 0.

Как следствие, количество отрезков из Л1, которые необходимо рассмотреть при расчёте агрегатного запроса <2{к}, экспоненциально быстро увеличивается при увеличении размерности данных £).

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

В данный момент большинство исследований ОЬАР-систем, главным образом, направлено на изучение различных прикладных аспектов, связанных с проектированием и эксплуатацией ОЬАР-систем [7] и, в первую очередь, различных способов их применения. Вместе с тем, устоявшихся принципов построения ОЬАР-систем, закреплённых соответствующими стандартами, пока не создано. В то же время необходимо отметить, что в прошедшие 30 лет активно велись работы по разработке теории и методов практического использования пространственного индексирования данных геоинформационных систем (ГИС) [8]. (Размерность данных ГИС принимает значение от 1 до 4). Здесь решён целый ряд проблем, связанных с организацией быстрого доступа к многомерным данным. При этом задачи обработки данных, решаемые ГИС, в целом оказываются схожими с задачами обработки данных ОЬАР-систем.

В связи с этим, разработка на основе идей пространственного индексирования, используемых в ГИС, алгоритмов доступа к многомерным данным в 8

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

Объект исследования: методы анализа многомерных данных.

Предмет исследования: алгоритмы доступа к многомерным данным в ОЬАР-системах.

Цель диссертационной работы: разработка быстрых алгоритмов доступа к многомерным данным в ОЬАР-системах, основанных на использовании пространственных индексов.

Для достижения поставленной цели решаются следующие основные задачи исследования:

1. Провести анализ методов доступа к данным в ГИС-системах с точки зрения возможности их использования в ОЬАР-системах.

2. Разработать быстрые алгоритмы доступа к многомерным данным АИС, основанные на принципах пространственного индексирования данных ГИС.

3. Получить теоретические оценки эффективности быстрых алгоритмов доступа к многомерным данным АИС.

4. Разработать программные реализации быстрых алгоритмов доступа к многомерным данным АИС.

5. Провести анализ результатов внедрения программных реализаций быстрых алгоритмов доступа к многомерным данным АИС.

Методы исследования. В работе были использованы методы теории вероятности, математической статистики, теории кодирования, теории параллельного программирования, теории систем управления базами данных (СУБД).

Научная новизна полученных результатов. К основным новым результатам, полученным в диссертации, можно отнести следующие:

1. Обоснование возможности и целесообразности использования пространственных индексов, применяемых в ГИС-системах, для индексирования данных АИС.

2. Быстрые алгоритмы доступа к многомерным данным АИС, основанные на принципах пространственного индексирования данных ГИС.

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

4. Результаты оценки эффективности разработанных быстрых алгоритмов доступа к многомерным данным АИС.

5. Результаты сравнительного анализа разработанных быстрых алгоритмов доступа к многомерным данным АИС с известными алгоритмами, не использующими методы пространственного индексирования данных.

Практическая значимость работы

1. Разработана программная реализация быстрых алгоритмов доступа к многомерным данным АИС — открытая программная библиотека «Индексирование многомерных классифицированных данных» (ИМКД).

2. Проведена апробация разработанных быстрых алгоритмов доступа к многомерным данным АИС в ПК «САПФИР», программной платформе (ПП) «Сектор», ПК «Карбон», анализ результатов которой подтверждает высокую эффективность предложенного в диссертации подхода.

3. Описаны особенности практического использования пространственного индексирования и структурирования запросов, а также их использования для решения типовых задач ОЬАР-систем.

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

На защиту выносятся:

1. Быстрые алгоритмы доступа к многомерным данным в ОЬАР-системах, основанные на методах пространственного индексирования данных ГИС.

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

3. Теоретические и экспериментальные результаты оценки эффективности быстрых алгоритмов доступа к данным в ОЬАР-системах.

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

Внедрение результатов диссертационного исследования

Результаты диссертационного исследования использованы в ООО «Ок-тоника», ООО «Научно-производственное объединение «Сапфир» при разработке программной библиотеки «ИМКД», ПК«САПФИР», ПК «Карбон» и ПП Сектор», а также в учебном процессе при подготовке бакалавров и магистров по направлению «Информатика и вычислительная техника».

Результаты диссертационного исследования были включены в инновационный проект, представленный на конкурсе, проводимом в 2010 г. Фондом содействия развитию малых форм предприятий в научно-технической сфере. По результатам конкурса проект стал победителем программы «Участник Молодежного Научно-Инновационного Конкурса» («УМНИК») 2010 г.

Апробация работы

Материалы работы докладывались на следующих научных конференциях: Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2008», Екатеринбург, 6-8 мая 2008 г.; Седьмой Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур», Томск, 2—5 сентября 2008 г.; Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2009», Екатеринбург, 17—19 марта 2009 г.; Межвузовской научной конференции по проблемам информатики «СПИСОК 2009», Екатеринбург, 20—23 апреля 2009 г.; Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2010», Екатеринбург, 5-7 мая 2010 г.

Публикации по теме диссертации

Статьи, опубликованные в журналах из списка ВАК

1. Бородин A.M. Использование пространственных индексов для обработки аналитических запросов и агрегирования многомерных данных в ИАС [Текст] / Бородин А.М, Поршнев C.B., Сидоров М.А. // Известия Томского политехнического университета. -2008. Т. 313. —№ 5. -С. 64—67.

2. Бородин A.M. Сравнительный анализ возможностей и скорости обработки многомерных данных программными средствами бизнес-аналитики на основе индексирующих структур основной памяти [Текст] / Бородин A.M., Поршнев C.B. // Научно-технические ведомости СПбГТУ. Серия «Информатика, Телекоммуникации, Управление». —№ 1(93). -2010. -С. 99-102.

3. Бородин A.M. О параллельном построении пространственных индексов основной памяти в OLAP-системах [Текст] / Бородин A.M., Поршнев C.B. // Научно-технические ведомости СПбГТУ. Серия «Информатика, Телекоммуникации, Управление». № 1(97). —2011. -С.72-74.

4. Бородин A.M. Аналитические способы оценки эффективности применения пространственных индексов в OLAP-системах [Текст] / Бородин

A.M., Поршнев C.B. // Научно-технические ведомости СПбГТУ. 2011. Серия

12

Информатика, Телекоммуникации, Управление». № 2 (120). —2011. —С. 93-100.

Другие публикации

1. Бородин A.M. Технологии доступа к многомерным данным [Текст]/ Бородин A.M., Сидоров М.А. // Научные труды международной научно-практической конференции«СВЯЗЬ — ПРОМ 2008» в рамках 5го Евро-Аз атского форума «СВЯЗЬПРОМЭКСПО 2008». -Екатеринбург: ЗАО «Компания Реал-Медиа», 2008. -С. 199-201.

2. Бородин А.М Агрегирование многомерных данных в аналитических системах на основе пространственных индексов [Текст] / Бородин А.М, Поршнев C.B., Сидоров М.А. // Сборник тезисов 7-й Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур». -Томск, 2008. -С. 10.

3. Бородин A.M. Методы оценки эффективности R-TREE индекса агрегирующих запросов в OLAP-системах [Текст] / Бородин А.М, Поршнев C.B., Сидоров М.А. // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМ 2009» в рамках 6-го Международного форума «СВЯЗЬПРОМЭКСПО 2009», посвященного 150-летию со дня рождения изобретателя радио A.C. Попова. - Екатеринбург : УрТИСИ ГОУ ВПО «СибГУТИ», 2009. -С. 59-66.

4. Бородин A.M. Проблема агрегатных конфликтов данных в системах анализа многомерных данных [Текст] / Бородин A.M., Королёв A.B., Мирво-да С.Г.// Научные труды международной научно-практической конференции «СВЯЗЬ - ПРОМ 2010» в рамках 7го Евро-Азиатского форума «СВЯЗЬПРОМЭКСПО 2010». -Екатеринбург: ЗАО «Компания Реал-Медиа», 2011.-С. 229-231.

Свидетельства о регистрации электронного ресурса

1. Бородин A.M. Программная библиотека «Индексирование многомерных классифицированных данных» / Бородин A.M., Поршнев C.B., Мирвода

13

С.Г.// Свидетельство об отраслевой регистрации № 14197 в отраслевом фонде электронных ресурсов науки и образования (госрегистрация № 50200900990 от 10.11.2009).

Свидетельства о регистрации программ для ЭВМ 2. Бородин A.M. Программный комплекс «Сапфир-3» / К.Г.Ведьманов, Д.Н.Решетарь, В.А.Кузьмин, А.М.Бородин // Свидетельство о государственной регистрации программы для ЭВМ № 2009610771 от 3 февраля 2009.

Структура диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованных источников, содержащего 105 наименований, и 2-х приложений. Общий объем работы составляет 163 страницы, в том числе 26 рисунков, 8 таблиц.

4.5. Выводы

1. Описан ПК «САПФИР», включение в который подсистемы, реализующей созданные в работе быстрые алгоритмы доступа к многомерным данным АИС и оптимизации запросов, позволили сократить время расчёта агрегирующих запросов расчётной таблицы, в том числе первое открытие с 5 часов до 72 с, второе и последующие открытия с 5 часов до 12 с, а также уменьшить время внесения изменений с одной минуты и более до 4 с. б i

5 - -I

2. Разработана программная библиотека «Индексирование многомерных классифицированных данных», на основе которой разработана подсистема проверки конфликтов и классифицирования данных для ПП «Сектор».

3. На основе ПБ «Индексирование многомерных классифицированных данных» разработана расчётная структура ПК «Карбон».

4. На основе результатов изучения методов синхронизации R-дерева при использовании многопоточного программирования, обоснована целесообразность использования на многопроцессорных системах параллельных загрузок данных.

5. Проведена экспериментальная проверка метода параллельной загрузки данных, результаты которой показывают, что:

- при загрузке 4 млн. записей данных, имеющих один атрибут типа decimal и классифицированных по 12 измерениям, время загрузки на 1 процессоре составило 182 секунды, на 2-х процессорах — 107 секунд, на 4-х процессорах - 83 секунды;

- при загрузке двух аналогичных по структуре наборов данных объёмом 2 млн. записей время загрузки на одном процессоре составило 185 секунд, на 2-х процессорах-92 секунды и на 4-х процессорах—71 секунду.

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

7. Сравнительный анализ производительностей, проведенный на тестовом наборе данных, показал преимущество OLAP-системы, использующей быстрые алгоритмы доступа к данным, по сравнению с OLAP-системой Jedox Palo и программной надстройкой Power Pivot.

Заключение

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

2. Разработаны быстрые алгоритмы доступа к многомерным данным в OLAP-системах, основанные на использовании принципов индексирования данных ГИС-систем.

3. Получены теоретические оценки эффективности разработанных быстрых алгоритмов доступа к многомерным данным в OLAP-системах.

4. Разработаны программные реализации быстрых алгоритмов доступа к многомерным данным в OLAP-системах, в том числе программная библиотека «Индексирование многомерных классифицированных данных».

5. Проведен анализ результатов внедрения разработанных программных реализаций быстрых алгоритмов доступа к многомерным данным в OLAP-системах в ПК «САПФИР», ПК «Сектор», ПК «Карбон», свидетельствующий об эффективности развитых в работе подходов.

1. Рынок BI-платформ. Результаты исследований за 2008 год Электронный ресурс.// http://citcity.ru/21333/

2. Бергер, А.Б. Microsoft SQL Server 2005. Analysis Services. OLAP и многомерный анализ данных Текст. / Бергер А.Б., Горбач И.В., Ме-ломед Э.Л., Щербинин В.А., Степаненко В.П. // СПб.:БХВ-Петербург, 2007. -С. 928.

3. Архипенков, С. Аналитические системы на базе ORACLE Express OLAP. Проектирование, создание, сопровождение Текст. / Архипенков С. // М.: Диалог-МИФИ, 2000. С.320

4. Сравнение OLAP-серверов Электронный ресурс. // http://ru.wikipedia.org/wiki/CpaBHeHHeOLAP-cepBepoB

5. Mondrian OLAP сервер Электронный ресурс.// http://ru.wikipedia.org/wiki/Mondrian

6. MOLAP, ROLAP, And HOLAP Электронный ресурс.// http ://w ww. 1 ke ydata. со m/datawareho us in g/mo 1 ар ro lap. htm 1

7. Data Warehousing and OLAP: A Research-Oriented Bibliography Электронный ресурс. // http://www.daniel-lemire.com/OLAP/index.html

8. Dassau О. A Gentle Introduction to GIS Текст./ Sutton Т., Dassau O., Sutton M. // -Eastern Cape, South Africa. -2009. C. 106

9. Devlin, В.A. An Architecture For A Business And Information System Текст./ Devlin B.A., Murphy P.T// IBM Systems Journal.-1988. -Vol 17, No 1. -C. 60-80.

10. Codd, E.F. Normalized data base structure: a brief tutorial TeKCT./Codd E.F. I I Proc. ACMSIGFIDET. -1971.- San Diego, Calif. -C. 1-18.

11. Туманов, В.Е.Системы складирования данных. Архитектура, продукты и подходы к реализации Текст./ Туманов В.Е.// Машиностроитель. — 2003. —№ 8. -С. 58-65.

12. Бородин, А.М.Технологии доступа к многомерным данным Текст./ Бородин A.M., Сидоров М.А., // Сборник трудов конференции СВЯЗЬ-ПРОМ 2008, с. 199-201.

13. Rainardi, V. Building a Data Warehouse: With Examples in SQL Server TeKCT./Rainardi V.// APRESS -2008. -C. 541.

14. Posumansky, M. Fast Track to MDX Текст. / Posumansky M., White-horn M., ZareR. // Springer. -2005. -C. 310.

15. Баранов, Ю.Б. Геоинформатика. Толковый словарь основных терминов Текст. / Ю.Б. Баранов, A.M. Берлянт, Капралов Е.Г. II— М.: ГИС-Ассоциация.—1999. —С.204. , .

16. Goodchild, М. (2010). Twenty years of progress: GIScience in 2010 Текст. / Goodchild, M. // Journal of spatialin formational science —1 — July 27, 2010.-C. 3-20.

17. Codd, E.F. Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate TeKCT./Codd E.F., Codd S.B. and Salley C.T. // Technical report, 1993.

18. Coppock, J. T. The history of GIS. Geographical Information Systems: principles and applications Текст. / Coppock J. Т., Rhind D. W. // Longman Scientific & Technical. -Essex. -1991. -C. 21-43.

19. Thurston, J. Integrated Geospatial Technologies: A Guide to GPS, GIS, and Data Logging Текст./ Thurston, J., Poiker, Т.К., Moore J.P. //—Wiley. -Hoboken, New Jersey. -2003. C.280

20. Tinghua, A. Multi-scale representation of building feature in urban GIS Текст. / Tinghua A., Hong W., Yaolin L. // -Geo-Spatial Information Science. -Volume 5, Number 2. -1999. C.37-^4

21. Berge, С. Théoriedes graphesetses applications Текст./ BergeC.// -Dunod, Paris. Collection Universitaire de Mathématiques, II.—1958. —C.277

22. Chang, К. T. Introduction to Geographical Information Systems/Chang, К. T. //-New York: McGraw Hill.-2008.-C. 184

23. Туманов, B.E. Типовая модель бизнес-процесса разработки хранилища данных Текст./ Туманов, В.Е.//— Машиностроитель. -2005. —№ 10. С. 27-31.

24. Gaede, V. Multidimensional Access Methods Текст./Gaede V., Gunther О. // -ACM Computer Surveys. Vol.30 No.2. -New York, USA. -1998.-C. 170-231.

25. Greene, D. An implementation and performance analysis of spatial data access methods Текст. / Greene, D. // -In Proceedings of the Fifth IEEE International Conference on Data Engineering. -1989. -C.606-615.

26. Gunther, O.Tree-based access methods for spatial databases: Implementation and performance evaluation Текст. / Gunther, O. Bilmes, J. // IEEE Trans. Knowl. Data Eng. -1991. -C.342-356.

27. Kriegel, H.-P. Performance comparison of index structures for multikey retrieval Текст. / Kriegel, H.-P. // Proceedings of the ACM SIGMOD International Conference on Management of Data.-1984. -C. 186-196.

28. Papadopoulos, A. Performance of nearest neighbor queries in R-trees Текст./ Papadopoulos, A., Manolopoulos, Y.// Proceedings of the International

29. Conference on Database Theory. — Springer-Verlag, -1997. -C.394-408.148

30. Guttman, A. R-trees: A dynamic index structure for spatial search-ing/Guttman A. // Proc. of the ACM SIGMOD Intern. Conf. on Management of Data. -1984.-C. 47-54.

31. Beckmann, N. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles Текст. / N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger // Praktuche Informatlk, Universitaet Bremen -1991. C. 322-331.

32. Shekhar, S. Encyclopedia of GIS TeKCT./Shekhar, S.,Xiong, H.// -Springer.-2008.-C. 1377

33. Jain, R. Similarity Indexing: Algorithms and Performance Текст. / Jain R, White D.A.: //- Proceedings SPIE Storage and Retrieval for Image and Video Databases IV, Vol. 2670. San Jose, USA. -1996.-C.62-75.

34. Leutenegger, S.T STR: A Simple and Efficient Algorithm for R-Tree Packing Текст. / Leutenegger S.T., Edgington J.M., Lopez M.A.//-NASA Contractor Report 201661. Langley Research Center, Hampton, USA. -1997. - C.34.

35. Graefe, G. Implementing Sorting in Database Systems Текст. / Graefe G. // -ACM Computing Surveys-Volume 38 Issue 3. -New York, USA. -2006. -C.l-37.

36. Bentley, J. L. Multidimensional binary search trees used for associative searchingTeKCT./ Bentley, J. L. // Communication of the ACM. —Vol. 18 No. 9. -1975. -C. 509-517.

37. Robinson, J. T. The K-D-B-tree: A search structure for large multidimensional dynamic indexes Текст./ Robinson, J. T. // In Proceedings of the ACM SIGMOD International Conference on Management of Data. -1981. - C. 1018.

38. Зубов, В. С. Глава 6. Поиск в недвоичных деревьях В-деревьях Текст./ Зубов В. С., Шевченко И. В. // Структуры и методы обработки данных. Практикум в среде Delphi. - Филинъ. 2004. - С. 144-164.

39. Chou, Н.-Т. An Evaluation of Buffer Management Strategies for Relational Database Systems/ Chou H.-T., Dewitt D.J.// -In Proceedings of VLDB Conference.-1985.-C. 127-141.

40. Sacco, G.-M. Buffer Management in Relational Database Systems Текст. / Sacco G.-M., Schkolnick M.// —ACM Transactions on Database Sys-tems.-Vol. 11, No. 4.-1986. C. 473-498.

41. Keyes, R.W.The Impact of Moore's Law Текст./ Keyes, R.W. //-Solid State Circuits Newsletter. -28.-2008. -C.25-27.

42. Таненбаум Э. Архитектура компьютера = Structured Computer Organization / Таненбаум Э. // -5-е изд. -СПб.:Питер. -2007. -С. 848

43. Рихтер, Дж. Windows. Создание эффективных \¥т32-приложений с учетом спецификации 64-разрядной версии Windows Текст. / Рихтер, Дж. И? М.: Питер, Русская редакция. —2001. -С. 752

44. Ramakrishnan R. Database Management Systems / R. Ramalcrishnan, J. Gehrke //-McGraw-Hill,Wisconsin. -2002. C.899

45. What is the Difference between OLTP and OLAP? Электронный pe-cypc.// http ://www.coolinterview.com/interview/413/

46. Database size Vs performance degradation Электронный ресурс.// http://archives.postgresql.org/pgsql-performance/2008-07/msg00244.php

47. Bernstein, P. Concurrency Control in Distributed Database Systems Текст. / Bernstein P., Goodman N. //—ACM Computing Surveys. —Volume 13, Issue 2.-198l.-C. 186-223.

48. Кожухова, O.E. Методы регулирования межбюджетных отношений в Свердловской области Текст. / Кожухова О.Е., Третьяков А.В., Серазиде-нов Р.Г., Серова М.А., Серова М.А. // —Финансы. —Екатеринбург. -2006. -С.18-19.

49. Hollasch, S. Floating point numbers Текст. / Hollasch S. // IEEE Standard 754

50. Dawson, В. Comparing floating point numbers Текст./ Dawson В.// — Cygnus-software. -1996.

51. Dawson, B. x86 Processors and Infinity Текст./ Dawson B.// -Cygnus-software. -1997.

52. Goldberg, D. What Every Computer Scientist Should Know About Floating-Point Arithmetic Текст. / Goldberg D. // -ACM Computing Surveys. -23.-1991. —C.5-48.

53. Hellerstein, J. Generalized Search Trees for Database Systems Текст. / Hellerstein J., Naughton J., Pfeffer A. // -Proc. 21st Int'l Conf. on Very Large DataBases. -Zürich -September 1995. C.562-573.

54. Kornacker, M. Concurrency and Recovery in Generalized Search Trees Текст. / Kornacker M., Mohan С., Hellerstein J.// Proc. ACM SIGMOD Conf. on Management of Data. -Tucson, AZ,USA. -May 1997. - C.62-72.

55. Амосов, A.A. Вычислительные методы для инженеров Текст. / Амосов A.A., Дубинский Ю. А., Копченова Н.П.// М.: Мир. -1998. - С.544

56. Вирт Н. Алгоритмы + структуры данных = программы / Вирт Н. // -М.: «Мир».-1985.-С.28

57. Sagan, Н. Space-Filling Curves Текст. / Sagan Н. // -Springer-Verlag. -1994. -С.193

58. Peano, G. Sur une courbe, qui remplit toute une aire plane Текст. / Peano, G. // -Mathematische Annalen. -36. -1890. C. 157-160.

59. Hilbert, D. Ueber die stetige Abbildung einer Line auf ein Flächenstück

60. Текст. / Hilbert, D. // -Mathematische Annalen. -38.-1891. -C.459^160.151

61. Шестаков, Н.А. Индексирование пространственных данных в MSSQL 2000 Текст. / Шестаков Н.А. // -Известия Томского политехнического университета. -2006. —Т. 309. № 4. -С.157-162.

62. Гулаков, В.К. Использование многомерных деревьев для обработки данных Текст. / Гулаков В.К., Трубаков А.О., Трубаков Е.О. // -Вестник Брянского государственного технического университета. -2007. —№ 3(15). С.46-55.

63. Sqrt-декомпозиция Электронный ресурс.// http ¡//informatics. mccme.ru/moodle/mod/resource/view.php?id=l 577

64. Fenwick, P.M. A new data structure for cumulative frequency tables Текст. / Fenwick P.M. // -Software: Practice and Experience. -24 (3). -1994 -C.327-336.

65. Rissanen, J.J. Arithmetic coding Текст. / Rissanen, J.J., Langdon,

66. G.G. //-IBM Journal of Research and Development. -23 (2). -1979. -C. 149-162.

67. Gray, J. Writing Faster Managed Code: Know What Things Cost Электронный ресурс. / Gray J. // http://msdn.microsoft.com/en-us/library/ms973852.aspx

68. Pas, R. Memory Hierarchy in Cache Based Systems Текст. / Ruud van der Pas // -Sun Microsystems, Inc. -2002. -C.26.

69. Frigo, M. Cache-Oblivious Algorithms / Frigo M., Leiserson C., Prokop

70. H., Ramachandran S. //-In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science. -1999. -C.285-297.

71. Chou, H.-T. An Evaluation of Buffer Management Strategies for Relational Database Systems Текст. / Chou H.-T., Dewitt D.J. // -In Proceedings of VLDB, Stockholm. -1985 -C. 127-142.

72. Емеличев, В. А. Лекции по теории графов Текст. / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. // -М.: Наука. -1990. -С.384

73. Theodoridis, Y. A model for the prediction of R-tree performance Текст. / Yannis Theodoridis , Timos Sellis // Материалы конференции ACM-SIGACT-SIGMOD-SIGART symposium on Principle soft database systems, 04-06 июня 1996. -С.161-171

74. Manolopoulos, Y. R-trees: Theory and Applications Текст. / Y. Mano-lopoulos, A. Nanopoulos, A. Papadopoulos, Y. Theodoridis // -Springer, 2006. -C. 194

75. Райзберг, Б. А. Современный экономический словарь Текст. / Рай-зберг Б. А., Лозовский Л. Ш., Стародубцева Е. Б. // 5-е изд., перераб. и доп. - М.: ИНФРА-М. -2007. -С.495

76. Fowler, М. UML Distilled: A Brief Guide to the Standard Object Modeling Language (2nd Edition) / Fowler M., Scott K., Jacobson I. // -Addison-Wesley Professional. -1999. -C.185

77. Klosterman, R. E. TIGER products for planning Текст. / Klosterman R. E., Lew A. A. // —Journal of the American Planning Association. —58 (3). -1992. -C.379

78. Choi S. C.Maximum Likelihood Estimation of the Parameters of the Gamma Distribution and Their Bias Текст. / Choi S. C.,Wette R. //— Technometrics.-l 1(4). -1969. -C.683-690.

79. Кендалл M. Статистические выводы и связи Текст. / Кендалл М., Стьюарт А. //-М.: Наука, 1973. -С.900

80. Feinberg, D. Magic Quadrant for Data Warehouse Database Management Systems Текст. / Feinberg D., Beyer M.A. // -Gartner RAS Core Research Note G00209623. -28 January 2011.

81. Johnson, T. Performance Measurements of Compressed Bitmap Indices Текст. / Johnson T. // -Proceedings of 25th International Conference on Very Large Data Bases, September 7-10 1999. -1999. -C. 278-89.

82. Посуманский, M. Хроника номер 9."Мы великие умы" Электронный ресурс. / Посуманский М. // http://www.mosha.com/XRONIKI/win-xronika9.html

83. Pedersen, Т. Multidimensional Database Technology Текст. / Peder-sen Т., Jensen С. //-Distributed Systems Online (IEEE). -2001. -C.40-46.

84. Becker, B. An asymptotically optimal multiversion B-tree / Becker В., Gschwind s., Ohler Т., Seeger В., Widmayer P. // -The VLDB Journal. -Volume 5, Number 4. -1996.-C.264-275.

85. Ford, W. Data Structures with С++ using STL Second Edition Текст. / Ford W., Topp W. // -Prentice-Hall. -2002. -C.466-467.

86. Ельцин, Б.Н. Бюджетный кодекс РФ Текст. / Ельцин Б.Н. //31 июля 1998 годаИ 145-ФЗ.-С.185

87. Spofford, G. MDX Solutions: With Microsoft SQL Server Analysis Services 2005 and Hyperion Essbase Текст. / Spofford G., Harinath S., Webb C., Huang D., Civardi F. // -Wiley. -2006. -C.744

88. Валиков, А. Технология XSLT Текст. / Валиков А. //-BHV-СПб—2001.-С.544

89. Лёве Дж. Создание служб WCF Текст. / Лёве Дж., Маннинен. П. // -Санкт-Петербург: ООО "Питер Пресс". -2008. -С.592

90. Kimball, R. The Data Warehouse Toolkit: The Complete Guide to Dimensional Modeling (2nd edition ed.) Текст./ Kimball R. , Ross M. //-Wiley.2002.-C.358—362.

91. Beynon-Davies, P. Database Systems 3rd Edition Текст. / Beynon-Davies P. //-Palgrave, Basingstoke, UK. -2004. C.616

92. Бородин Я.М. Аналитические способы оценки эффективности применения пространственных индексов в OLAP-системах Текст. / Бородин A.M., Поршнев С.В., // Научно-технические ведомости СПбГТУ. 2011. -С. 93-100.

93. Brinkhoff, Т. Efficient processing of spatial joins using R-trees Текст. / Brinkhoff, Т., Kriegel H., Seeger B. // -In Proceeding of ACM SIGMOD. -1993. -C.237-246.

94. SQL DISTINCT Электронный ресурс. // http://www.sql-tutorial.com/sql-distinct-sql-tutorial/

95. Stokes, J. SIMD Architectures Электронный ресурс. / Stokes J.//http://arstechnica.com/old/content/2000/03/simd.ars/155

96. Berillo, A. NVIDIA CUD A: Non-graphic computing with graphics processors Электронный ресурс. / Berillo A. // http://ixbtlabs.com/articles3/video/cuda-l-pl.html

97. Бородин A.M. О параллельном построении пространственных индексов основной памяти в OLAP-системах Текст. / Бородин A.M., Поршнев С.В., // Научно-технические ведомости СПбГТУ. Серия «Информатика, Телекоммуникации, Управление». № 1(97). —2011. —С.72—74.

98. Bercken, J. An Evaluation of Generic Bulk Loading Techniques Текст. / Bercken J., Seeger B. // -Proceedings of the 27th VLDB Conference. —Roma, Italy. -2001. —C.471-480.

99. Marshall, D. Mutual Exclusion Locks Электронный ресурс. / Marshall, D. // http://www.cs.cf.ac.Uk/Dave/C/node31 .html

100. Analysis Services in VertiPaq mode Электронный ресурс. // http://technet.microsoft.com/ru-ru/library/ee637273(SQL.105).aspx

101. Palo for Excel Open Source Business Intelligence for Planning, Analysis, Reporting and Consolidation Электронный ресурс. // http://www.jedox.com/en/products/palo-for-excel/palo-for-excel.html