автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы пространственного индексирования в СУБД

Р Г 5 ОД

САНКТ-ЦЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

- - ! • УНИВЕРСИТЕТ

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

Мартынов Максим Геннадьевич

Методы пространственного индексирования в СУБД

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени

кандидата физико-математических наук

Санкт-Петербург 1998

Работа выполнена в Санкт-Петербургском государственном университете.

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

Новиков Борис Асенович

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

• доктор технических наук С.Д. Кузнецов

• кандидат физико-математических наук М.Б. Округин

Ведущая организация — Институт проблем информатики Российской академии наук

Защита диссертации состоится « / » яс^а^М 199/ г. в час. И1 мин. на заседании диссертационного совета К 063.57.54 по защите диссертации на соискание ученой степени кандидата наук в Санкт-Петербургском государственном университете по адресу: 198904 Санкт-Петербург, Старый Петергоф, Библиотечная пл. 2.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского университета по адресу:

199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан « /У » ^Л-^ата, 199/ г.

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

Б.К. Мартыненко

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

Актуальность темы. Пространственные методы доступа являются основой геоинф'ормайибнных систем, а также широко используются в других областях применения СУБД, таких как временные базы данных. компьютерное зрение, базы знаний. САПР и др., требующих многоатрибутного индексирования.

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

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

Все это делает необходимым использование специальных методов доступа к данным в таких системах.

Поэтому разработка пространственных методов индексирования для СУБД представляется весьма актуальной.

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

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

фикаций проводились вычислительные эксперименты, и выполнялись аналитические оценки. Реализация системы сравнения прототипов методов индексирования выполнена на языке программирования С,

Научная новизна. Научную новизну составляют предложенные в диссертационной работе метод хранения пространственных ключей It-дерева, использующий локальные координаты узла; модификация алгоритма динамического удаления и вставки R'-дерева, улучшающая пространственную структуру индекса; динамически создаваемый локальный клеточный индекс, позволяющий сократить время поиска пути при вставке объекта в дерево; комбинированный алгоритм выполнения фильтрующего шага пространственного соединения R-деревьев, обеспечивающий низкую стоимость операций ввода/вывода при контролируемом использовании оперативной памяти и процессорного времени; клеточная эвристика, ускоряющая нахождение релевантных пар записей узлов соединяемых деревьев при выполнении операции пространственного соединения; использование ориентированных многоугольников для внутренних и внешних аппроксимаций пространственных объектов и для TR'-дерева, а также быстрый способ тестирования ориентированных многоугольников на пересечение; алгоритм, использующий пространственные методы доступа для индексирования текстов.

Практическая ценность. Практическая ценность работы определяется возможностью ее использования в любой СУБД, использующей пространственные методы доступа к данным.

Апробация работы. Основные результаты диссертации докладывались на семинарах лаборатории исследования операций, на ежемесячном семинаре Московской секции ACM SIGMOD в ноябре 1996 года, на международных симпозиумах "Advances in Databases and Information Systems" в 1994, 1995, 1996 годах. По теме диссертации опубликованы работы [1-4].

Структура и объем работы. Диссертация состоит из 6 глав, в

том числе введения и заключения. Объем диссертации составляет 78

машинописных листов. Список литературы содержит 63 наименования.

Содержание работы

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

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

В третьей главе описываются предлагаемые улучшения алгоритмов обработки Н-дерева.

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

Это достигается с использованием следующей структуры узла: (/>, Хер. .\Ь[,..., Xbn, (Sobj', Ср)*). где Nop — начало локальных координат, Nb; — количество битов для представления величин пространственных ключей вдоль г-ой оси, a Sobj' обозначает представление Sobj

в новых (локальных) координатах. Здесь Sobj — пространственный ключ записи, а Ср — ссылка на поддерево. Каждый узел имеет флаг /г, показывающий какое представление используется для пространственных ключей в данном узле — обычное или компактное.

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

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

Далее описывается модификация алгоритма динамического удаления и вставки 11*-дерева, улучшающая пространственную структуру индекса.

Алгоритм динамического удаления и вставки [ВКББЭО] используется при добавлении записи в 1Г-дерево и состоит в следующем: записи переполненного узла, чьи пространственные ключи наиболее удалены от центра ограничивающего объекта узла, удаляются из индекса, а затем вставляются в дерево снова. В исходном алгоритме при добавлении одной записи данных в дерево динамическое удаление и вставка осуществляются только один раз на каждом уровне дерева, в остальных случаях производится расщепление. Предлагаемая модификация алгоритма состоит в выполнении динамического удаления и вставки более одного раза на каждом уровне дерева.

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

Четвертая глава посвящена алгоритмам пространственного соединения с использованием 11-деревьев. В ней подробно рассматриваются существующие методы соединения. Пространственное соединение двух множеств пространственных объектов — это множество всех пар пересекающихся объектов из разных множеств. Проводится классификация алгоритмов пространственного соединения [ВКБ93, ВКБ894, Ы194, 2] в зависимости от наличия пространственных индексов соединяемых множеств объектов.

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

Далее описывается комбинированный алгоритм выполнения фильтрующего шага пространственного соединения [3], основанный на двух алгоритмах, описанных ранее в [2].

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

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

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

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

Защита от переполнения буфера осуществляется путем использования второго алгоритма для обработки записей из буфера первого алгоритма.

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

Затем описывается использование многоугольников с ориентированными сторонами для внутренних и внешних аппроксимаций объектов данных, а также в ТГГ-дереве при их декомпозиции. Такой тип описания пространственных объектов является привлекательным, так как с одной стороны имеет низкую стоимость выполнения теста на пересечение (2 * тг сравнений для ориентированных п-угольннков в худшем случае), а с другой стороны путем изменения п можно выбирать нужную точность описания.

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

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

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

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

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

Для каждого вхождения ключевого слова в индексируемый документ инвертированный список слова содержит запись, включающую номер документа и, возможно, позиционную информацию. В случае отсутствия позиционной информации список слова содержит одну запись для всех вхождений слова в конкретный документ. Для ускорения доступа и уменьшения использования памяти записи инвертированных списков упорядочены по номерам документов. Это позволяет использовать сжатие с помощью хранения закодированных разностей соседних номеров в списке. Списки хранятся в упакованном виде, а для доступа к их элементам используется однопроходный алгоритм распаковки, описанный в [гМ8092].

Алгоритм, описанный в [Z:\ISD92], позволяет выполнять только последовательные просмотры списка, что может привести к значительным накладным расходам при обработке больших инвертированных списков.

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

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

Данная структура, названная SB-деревом, может рассматриваться как одномерное R-дерево [BKSS90] с дополнительной информацией и узлами-листьями специального вида или как усложненное В-дерево.

Каждый промежуточный узел такой структуры, содержит записи вида (min, max, ds, те}), где min и max — минимальный и максимальный номера документов поддерева, на которое указывает ссылка ге/, a ds — мертвое пространство узлов-сыновей. Мертвое пространство узла определяется как сумма длин отрезков протяженности узла, не покрытой протяженностями узлов-сыновей. Протяженность узла — минимальный отрезок номеров документов, содержащий все номера документов поддерева, корнем которого является данный узел.

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

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

Далее описывается алгоритм слияния инвертированных списков на основе предлагаемой структуры.

Сначала рассматривается выполнение запросов следующего вида: найти все документы t, где A"=1V^i1f>(u;y,i). Здесь P(w, t) — предикат: ключевое слово ги содержится в документе t.

Пусть Q = U"=1 U™!] Wij — множество всех ключевых слов, участвующих в запросе.

Для вычисления запроса описываемый алгоритм использует ¡(51 сте-

ков, элементами которых являются записи SB-деревьев, соответствующих словам из О. Записи располагаются в порядке возрастания номеров документов. Также используется дополнительный стек PosZones для хранения отрезков, показывающих возможные зоны номеров документов, релевантных запросу.

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

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

Затем проводится анализ возможного выигрыша в производительности при использовании предлагаемых алгоритмов, и приводятся результаты вычислительных экспериментов.

Глава б является заключительной. В ней кратко обобщаются и суммируются полученные результаты.

Основные результаты

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

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

2. Предложена модификация алгоритма динамического удаления и вставки R'-дерева, улучшающая пространственную структуру индекса.

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

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

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

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

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

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

Библиография

[BKS93] T. Brinkhoff. H.-P. Kriegel. and B. Seeger. Efficient processing of spatial joins using R-trees. Proc. ACM SIGMOD Int. Conf. 017 Management of Data, pages 237-246, 1993.

[BKSS90] N. Beekmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proc. A CM SIGMOD Int. Conf. on Management of Data, pages 322-331, Atlantic City, NJ, 1990.

[BKSS94] T. Brinkhoff, H.-P. Kriegel, R. Schneider, and B. Seeger. Multistep processing of spatial joins. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 197-208. 1994.

[LR94] Ming-Ling Lo and C.V. Ravishankar. Spatial join using seeded trees. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 209- 220. 1994.

[ZMSD92] Justin Zobel, Alistair Moffat, and Ron Sacks-Davis. Efficient

indexing technique for full-text database systems. In Proc. 18th Intnl. Conf. on VLDB. Vancouver, British Columbia, Canada, 1992., pages 352-362, 1992.

Работы автора по теме диссертации

[1] М.Г. Мартынов. Пространственные методы доступа. Программирование. 1998. 3. С.59-69.

[2] М. Martynov. Variations of R-tree structure for indexing of spatial objects. In Proc. of the Intnl. Workshop on Advances in Databases and Information Systems - ADBIS'94, pages 217-221, Moscow, May 23-26 1994.

[3] M. Martynov. Spatial joins and R-trees. In Proc. of the Second Intnl. Workshop on Advances in Databases and Information Systems - AD-BIS'95, pages 295-304, London etc., 1996. Springer-Verlag.

[4] M. Martynov and B. Novikov. An indexing algorithm for text retrieval. In Proc. of the Third Intnl. Workshop on Advances in Databases and Information Systems - ADBIS'96, pages 171-175, Moscow, Sept. 1013 1996. МЕРЫ.

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Мартынов Максим Геннадьевич

Методы пространственного индексирования в СУБД

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д.ф.-м.н. Б.А. Новиков

I/

л.

Санкт-Петербург 1998

Содержание

1 Введение 4

2 Пространственные методы доступа 8

2.1 Области применения..............................................9

2.2 Типы хранимых данных ........................................11

2.3 Пространственные запросы......................................13

2.4 Методы индексирования ........................................15

2.4.1 Методы индексирования точечных объектов..........15

2.4.2 Методы индексирования протяженных объектов ... 16

2.4.3 Пространственные деревья..............................17

2.5 Я-деревья..........................................................20

3 Улучшения алгоритмов обработки Я-дерева 25

3.1 Локальные координаты..........................................25

3.2 Модификация алгоритма динамического удаления и вставки 31

3.3 Временный локальный клеточный индекс......................32

4 Пространственное соединение с использованием II-деревьев 37 4.1 Комбинированный алгоритм пространственного соединения 41

4.1.1 Алгоритм пространственного соединения, использующий свойство асимметрии чтения страниц..........41

4.1.2 Алгоритм пространственного соединения, использующий попеременный спуск в деревьях ................45

4.1.3 Комбинированный алгоритм............................47

4.2 Клеточная эвристика............................................48

4.3 Использование ориентированных многоугольников..........51

5 Использование алгоритмов пространственных методов для индексирования текстов 54

5.1 Индекс для инвертированных списков..........................58

5.2 Алгоритм обработки инвертированных списков..............61

5.3 Оценка выигрыша в производительности......................65

6 Заключение 69

1 Введение

Пространственные методы доступа [5, 48, 1] являются основой геоинформационных систем, а также широко применяются в других областях, таких как временные базы данных [8], компьютерное зрение [27], базы знаний, САПР [7] и др., требующих многоатрибутного индексирования [48]. Важным требованием к таким системам является необходимость эффективной обработки очень больших объемов данных, имеющих пространственную природу, что делает необходимым использование специальных методов доступа к данным в таких системах.

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

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

Обычные методы индексирования— В+-деревья [25], различные варианты линейного хэширования — не подходят для таких систем. Они позволяют выполнять индексирование только по одному атрибуту, что делает их неэффективными для пространственных запросов, особенно если множество поиска очень велико.

Хранение линейных индексов по каждому атрибуту в отдельности

также не является решением проблемы [5], так как при выполнении многоатрибутного запроса [48] в такой системе необходимо сначала выполнить вспомогательные запросы по каждому атрибуту для получения множеств объектов, удовлетворяющих ограничениям основного запроса по соответствующим атрибутам, а затем выполнить пересечение полученных множеств. Результирующие множества промежуточных запросов обычно содержат намного больше элементов, чем результирующее множество основного запроса, что и является причиной неэффективности данного метода.

Все это привело к созданию специальных методов индексирования для пространственных данных [5, 48, 1], сущность которых состоит в том, что объекты, близкие в исходном пространстве, хранятся вместе во вторичной памяти. Это и позволяет быстро производить поиск.

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

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

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

Среди методов пространственного индексирования выделяются древовидные методы хранения, которые являются многомерным аналогом В+-деревьев. Узел такого дерева представляет собой некоторое разбиение области, содержащей объекты узла, на подобласти, содержащие объекты узлов ниже лежащих уровней и набор ссылок на следующий уровень дерева.

Наиболее известными структурами такого типа являются различные модификации 11-деревьев [13, 59, 36], а также С-деревья [35]. Эти методы основаны на аппроксимации реальных пространственных объектов ограничивающими объектами: прямоугольниками со сторонами параллельными осям координат или произвольными выпуклыми многоугольниками соответственно.

В данной работе рассматривается более узкий класс таких методов, в которых не используется техника дублирования данных, применяемая в 11+-деревьях [59], так как требуются большие вычислительные затраты на модификацию дерева при сильном разбросе максимальных размеров пространственных объектов [48].

Как и в одномерном случае над пространственными деревьями выполняются операции вставки и удаления объектов, а также различные виды запросов: диапазонные, точечные и соединения (см. раздел 2.3). Однако, в отличие от В-деревьев, алгоритм построения пространственного дерева

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

Наиболее важным видом запросов, выполняемых над пространственными деревьями, является пространственное соединение [22]. Примером такого запроса может служить нахождение всех городов, находящихся на реках, при наличии пространственных индексов городов и рек некоторого района. Выполнение таких запросов является наиболее трудоемкой операцией с вычислительной точки зрения. Это привело к созданию достаточно сложных методов выполнения пространственных соединений [34, 22, 21, 47, 2], использующих для оптимизации различные особенности обрабатываемых данных и соединяемых индексов.

Диссертация состоит из б глав.

Глава 1 представляет собой введение. В главе 2 дается обзор пространственных методов доступа. В ней приводится классификация пространственных методов по типам хранимых данных, видам пространственных запросов и методам индексирования. Кроме того, рассматривается наиболее важная группа методов под общим названием Я-деревья. В главе 3 описываются предлагаемые улучшения алгоритмов обработки И-дерева. Глава 4 посвящена алгоритмам пространственного соединения с использованием 11-деревьев. В ней подробно рассматриваются существующие методы соединения. Описывается комбинированный алгоритм выполнения фильтрующего шага пространственного соединения и эвристики, позволяющие улучшать производительность существующих методов. В главе 5 описывается разработанный алгоритм индексирования текстов, использующий пространственные методы индексирования. Заключение кратко обобщает и суммирует полученные результаты.

2 Пространственные методы доступа

Метод доступа — совокупность алгоритмов и условий их применения, определяющих способ хранения и обработки данных в СУБД и других системах обработки информации. Способ хранения данных в СУБД определяет формат, в котором хранятся данные и связанная с ними дополнительная информация, использующаяся в алгоритмах обработки данных. Примером вспомогательных данных являются индексы, позволяющие ускорять выполнение различных операций с данными, таких как запросы.

Метод индексирования — часть метода доступа, предназначенная для обеспечения более эффективной обработки данных. Наиболее важным типом обработки данных в СУБД является выполнение запросов, когда необходимо извлечь информацию из СУБД по некоторым условиям поиска, составляющим запрос. В процессе выполнения запроса может многократно выполняться операция нахождения подмножества некоторого множества объектов данных, удовлетворяющего критериям промежуточных стадий запроса. При этом метод индексирования определяет способ хранения данных и алгоримты работы с ними, позволяющие сократить перебор объектов при определении искомого подмножества объектов данных.

Пространственные методы доступа [5, 48, 1] — это методы доступа, которые позволяют эффективно выполнять операции с данными, использующие пространственные отношения объектов, такие как отноше-

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

2.1 Области применения

Пространственные методы доступа применяются в самых различных областях [58]. Вот некоторые из областей применения:

• Географические базы данных [46, 10]. Это традиционная область применения пространственных методов. Именно она дала толчок к созданию этих методов, благодаря необходимости достаточно эффективно обрабатывать огромные объемы пространственных данных. Примером географической базы данных может являться электронная карта некоторого района, в которой можно выполнять пространственные запросы типа: "найти все аэродромы на карте, пересекающие прямоугольник запроса".

• Временные базы данных (объекты, протяженные во времени). В таких системах [9, 11, 38] одним из атрибутов данных является момент времени или отрезок времени, к которому относятся эти данные. Например, в системе слежения за движением спутников хранится информация об их положении через определенные интервалы времени. В такой системе можно выполнять пространственно-временные запросы типа: "найти спутники, находившиеся над заданным районом в заданный отрезок времени". Время может рассматриваться как дополнительный пространственный атрибут, имеющий определенную специфику. Так, записи о прошлых моментах времени не могут меняться и могут храниться на ROM оптических дисках [56].

• Компьютерное проектирование (САПР/САБ) [29]. В таких системах при разработке некоторого агрегата хранится местоположение и ориентация деталей, составляющих агрегат. Могут выполняться пространственные запросы для нахождения всех деталей в некоторой части агрегата.

• Компьютерная обработка изображений [53] и робототехника. При обработке изображений, а также при анализе сцен, наблюдаемых роботами, изображение разбивается на большое число составляющих-объектов. При этом нужно выполнять пространственные запросы для выяснения пространственных отношений объектов.

• Традиционные базы данных (многоатрибутное индексирование). В обычных СУБД часто выполняются многоатрибутные запросы, в которых одновременно накладываются условия на значения нескольких атрибутов сразу. Примером может служить запрос к базе данных сотрудников некоторого предприятия: "найти всех сотрудников в возрасте от 25 до 35 лет ростом выше 2 метров весом от 75 до 90 килограммов". Если база данных содержит большой объем информации, и в ней часто выполняются многоатрибутные запросы, то применение пространственных методов может дать значительный выигрыш в производительности по сравнению с обычными методами.

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

2.2 Типы хранимых данных

Основными характеристиками пространственных данных являются:

• размерность исходного пространства,

• типы хранимых объектов:

1. протяженные объекты (объекты, размерами которых нельзя пренебречь в условиях задачи),

2. точечные объекты (объекты, размерами которых можно пренебречь в условиях задачи и представить их п-мерными точками),

3. разбиение (объекты, образующие разбиение некоторой связной области исходного пространства),

4. сеть (объектами являются пути в исходном пространстве),

• распределение данных и их характеристик,

• объемы хранимых данных.

Примеры объектов различных типов в двумерном варианте изображены на рисунке 2.1.

Рассмотрим подробнее перечисленные характеристики.

Размерность исходного пространства — одна из самых важных характеристик, определяющих используемые методы хранения.

Так, отдельно можно рассматривать одномерный случай, где уже давно существуют достаточно хорошо разработанные методы (В-деревья и т.д.). Следующая категория — небольшие размерности (в пределах 10). Для них существует огромное количество различных пространственных методов и их вариаций, о которых речь пойдет позднее. Почти все эти методы теоретически годятся для любых размерностей, однако на практике в случае больших размерностей (100, 1000, и более) существуют более эффективные методы (например Х-деревья [19] и другие [17, 15, 18]).

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

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

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

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

Еще одной характеристикой данных является распределение объектов данных в исходном пространстве, а также распределение характеристик

объектов данных. В реальных задачах данные обычно имеют сильно неравномерное распределение, иногда наблюдается кластеризация данных. По мнению авторов [14], в большинстве задач распределение данных имеет фрактальную природу [50], что позволяет делать более точные оценки селективности диапазонных запросов и пространственного соединения.

Распределение характеристик данных, так же как и распределение данных, влияет на используемые методы индексирования. Так, например, в случае наличия сильно различающихся по размерам объектов данных, б�