Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Теоретические основы информатики

Диссертационная работа:

Бородин, Андрей Михайлович. Разработка быстрых алгоритмов доступа к многомерным данным в OLAP-системах : диссертация ... кандидата технических наук : 05.13.17 / Бородин Андрей Михайлович; [Место защиты: Сиб. гос. ун-т телекоммуникаций и информатики].- Екатеринбург, 2011.- 163 с.: ил. РГБ ОД, 61 11-5/2987

смотреть введение
Введение к работе:

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

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

иерархий {Hi,H2,..HD} реализуется следующими преобразованиями:

(p:K^R\Rl=[0M

Oj-.Hj >R\[OMJ = 1,2,. .D,

(p(h) = d -v^ih^ + d1 -v^h^ + d2 -v^h^)+ ...,d «\,d >0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net