Разработка быстрых алгоритмов доступа к многомерным данным в OLAP-системах тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Бородин, Андрей Михайлович

• Бородин, Андрей Михайлович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Бородин, Андрей Михайлович

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

Введение.

Глава 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-системах»

Актуальность темы исследования. Сегодня разработка программных средств, предназначенных для хранения и обработки больших объемов разнородных данных, является одним из активно развиваемых направлений ИТ-отрасли, которые дают возможность проводить комплексный многомерный анализ больших объемов различного типа информации (финансовой, статистической, операционной и т.п.) и представлять полученные результаты в виде различных консолидированных отчетов. Основным инструментом, используемым для решения задач обработки многомерных данных, являются 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-системах в ПК «САПФИР», ПК «Сектор», ПК «Карбон», свидетельствующий об эффективности развитых в работе подходов.

Список литературы диссертационного исследования кандидат технических наук Бородин, Андрей Михайлович, 2011 год

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