Василий Константинович Гулаков , Андрей Олегович Трубаков , Евгений Олегович Трубаков - Структуры и алгоритмы обработки многомерных данных: монография

В. К. ГУЛАКОВ, А. О. ТРУБАКОВ, Е. О. ТРУБАКОВ

СТРУКТУРЫ
И АЛГОРИТМЫ
ОБРАБОТКИ
МНОГОМЕРНЫХ
ДАННЫХ
Монография
Издание второе, стереотипное

•САНКТПЕТЕРБУРГ•
•МОСКВА•
•КРАСНОДАР•
2021

УДК 004.657
ББК 32.81я73
Г 94

Гулаков В. К. Структуры и алгоритмы обработки много
мерных данных : монография / В. К. Гулаков , А. О. Трубаков,
Е. О. Трубаков. — 2е изд. стер. — СанктПетербург : Лань,
2021. — 356 с. : ил. — Текст : непосредственный.

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

УДК 004.657
ББК 32.81я73

Рецензенты:
В. И. АВЕРЧЕНКОВ — доктор технических наук, профессор, заслуженный
деятель науки РФ, почетный работник высшего профессионального обра
зования;
В. В. МИРОШНИКОВ — доктор технических наук, профессор, действи
тельный член Академии проблем качества, почетный работник высшего
профессионального образования РФ.

Обложка
Е. А. ВЛАСОВА

© Издательство «Лань», 2021
© Коллектив авторов, 2021
© Издательство «Лань»,
художественное оформление, 2021

3

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ ........................................................................................... 5
ВВЕДЕНИЕ ................................................................................................... 8
ГЛАВА 1. ОСНОВНЫЕ ПОЛОЖЕНИЯ ................................................. 10
1.1. Понятие многомерного объекта .................................................. 10
1.2. Виды запросов к многомерным хранилищам данных ............... 14
1.3. Расстояние между многомерными объектами ........................... 18
1.4. Минимальный описывающий регион (MBR) ............................ 21
1.5. Области использования многомерных структур ....................... 25
Резюме.................................................................................................... 31
ГЛАВА 2. ТОЧЕЧНЫЕ МЕТОДЫ ДОСТУПА ...................................... 32
2.1. Классификация точечных методов доступа ............................... 33
2.2. Иерархические методы доступа .................................................. 36
2.2.1. K-D-дерево ............................................................................ 36
2.2.2. K-D-B-дерево ........................................................................ 56
2.2.3. LSD-дерево ........................................................................... 81
2.2.4. Quad-дерево ........................................................................ 103
2.3. Многомерное хеширование ....................................................... 120
2.3.1. Файл-решетка ..................................................................... 122
2.3.2. Хеширование EXCELL ...................................................... 152
2.3.3. Многомерное линейное хеширование с частичным
расширением (MOLHPE) .............................................................. 158
2.3.4. Многомерное линейное хеширование с сохранением
порядка - PLOP .............................................................................. 179
2.4. Кривые, заполняющие пространство ........................................ 189
2.4.1. Упорядочивание по ключам .............................................. 191
2.4.2. Кривая z-порядка................................................................ 195
2.4.3. Кривая Гильберта ............................................................... 198
2.4.4. Кривая, основанная на кодах Грея ................................... 201
Резюме.................................................................................................. 202
ГЛАВА 3. ПРОСТРАНСТВЕННЫЕ МЕТОДЫ ДОСТУПА ............... 203
3.1. Методы преобразования пространственных объектов ........... 205
3.1.1. Преобразование в пространство большей размерности . 205
3.1.2. Кривые, заполняющие пространство для объемных
объектов ......................................................................................... 210
3.2. Структуры с перекрытием областей ......................................... 214

4
3.2.1. R-дерево .............................................................................. 215
3.2.2. R-дерево Грина ................................................................... 250
3.2.3. R*-дерево --">