ПРОГРАММИРОВАНИЕ, 2012, No 3, с. 11-23
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
НОВЫЙ АЛГОРИТМ РАЗДЕЛЕНИЯ УЗЛА ДЛЯ Я-ДЕРЕВА, ОСНОВАННЫЙ НА ДВОЙНОЙ СОРТИРОВКЕ
© 2012 г. А.Е. Коротков Национальный исследовательский ядерный университет «МИФИ» 115552 Москва, пр-т Пролетарский, д. 6, к. 3 E-mail: aekorotkov@gmail.com Поступила в редакцию 27.04.2012 г.
Хранение пространственных запросов и обработка пространственных запросов - важные задачи современных баз данных. Эффективное выполнение пространственных запросов зависит от используемой индексной структуры. И-дерево - широко известная пространственная индексная структура. Существуют различные версии И-дерева, и одно из наиболее частых отличий версий между собой - алгоритм разделения узла. Проблема разделения узла в одномерном И-дереве может показаться слишком тривиальной, чтобы рассматриваться отдельно. Одномерные интервалы могут быть легко разделены на основе сортировки. Некоторые алгоритмы разделения узла для И-дерева для двух и более измерений содержат в своем составе одномерное разделение. Однако, если рассмотреть вопрос более детально, существующие алгоритмы для одномерного разделения работают не идеально в некоторых сложных случаях. В данной работе вводится новый алгоритм разделения узла, основанный на двух сортировках, которые позволяет обрабатывать некоторые сложные одномерные разделения лучше. Также вводится алгоритм разделения узла для двух-и более мерных И-деревьев, который основан на предложенном одномерном алгоритме. Тесты выявляют значительно лучшее поведение предложенных алгоритмов по сравнению с известными в случае сильно пересекающихся данных.
Обработка пространственных данных -актуальная задача для современных баз данных. Поскольку объем информации в базах данных постоянно увеличивается, системам управления базами данных (СУБД) требуются пространственные индексные структуры для того, чтобы обрабатывать пространственные запросы эффективно. Проблема пространственных индексов состоит в том, что не существует упорядочивания, которое отображало бы близость пространственных объектов [6]. Поэтому такие структуры, как например, В-дерево [4] не позволяют работать с пространственными объектами эффективно. И-дерево [9] - наиболее известная индексная структура для пространственных данных. И-дерево представляет собой сбалансированное
1. ВВЕДЕНИЕ
по высоте дерево, подобно В-дереву, которое иерархически разделяет пространство на подпространства, которые могут пересекаться между собой. Пространственные объекты в И-дереве аппроксимируются виде минимальных ограничивающих прямоугольников (МОП). Элемент листового узла И-дерева содержит МОП пространственного объекта и ссылку на соответствующий объект базы данных. Элемент внутреннего узла И-дерева содержит ссылку на дочерний узел и МОП всех прямоугольников, расположенных в этом узле. Поскольку прямоугольники одного узла И-дерева могут пересекаться, поиск по точному совпадению может потребовать сканирования нескольких путей в дереве (многопутевой поиск). В этом состоит существенное отличие И-дерева от таких структур данных, как В-дерево. Число путей, и в свою очередь доступов к узлам, которые
Рис. 1. MBR illustration
требуются для поиска не по точному совпадению так же сильно зависит от степени пересечения прямоугольников. И-дерево было изначально предназначено для доступа к многомерным данным, но существуют его применения для одномерных интервалов [12].
Качество И-дерева сильно зависит от алгоритма разделения узла. Задача разделения узла состоит в том, чтобы разделить записи переполненного узла на две группы, которые затем образуют два новых узла. Алгоритм разделения узла во многом определяет площадь и степень пересечения прямоугольников дерева. В свою очередь эти параметры определяют вероятность того, что запрос будет использовать сканирование дерева по нескольким путям. Существуют следующие параметры, с помощью которых можно оценить качество разделения узла:
• Степень пересечения ограничивающих прямоугольников. Меньшая степень пересечения прямоугольников приводит к меньшей вероятности многопутевого поиска.
• Покрытие ограничивающих прямоугольников. Покрытие разделения - это общая площадь ограничивающих прямоугольников. В целом, меньшее покрытие приводит к меньшей вероятности многопутевого поиска в том случае, когда запрашиваемая площадь относительно большая [2].
• Эффективность хранения. В качестве меры эффективности хранения может быть использовано соотношение между числом элементов в меньшей и большей
группах. Обычно на этот параметр вводится ограничение в виде минимально числа элементов в меньшей группе т. Ограничение на этот параметр очень уместно, однако этот параметр также может выступать и в качестве цели оптимизации. Лучшее соотношение при разделении ведет к меньшей балансировке дерева в процессе его создания, что, в свою очередь, влияет на его качество.
На рис. 2 представлена иллюстрация дилеммы между выбором меньшего покрытия и меньшего пересечения.
Данная работа организована следующим образом. В разделе 2 описываются алгоритмы разделения узла, известные на данный момент. Раздел 3 вводит алгоритм одномерного разделения узла, основанный на двух сортировках, и его обобщение на многомерный случай. В разделе 4 представлено экспериментальное сравнение предложенного алгоритма с другими существующими алгоритмами. В разделе 5 подводится итог.
2. СВЯЗАННЫЕ РАБОТЫ
Изначально Гутманом в [9] были введены 3 алгоритма разделения узла:
• Экспоненциальный алгоритм. Этот алгоритм ищет глобальный минимум площади, покрываемой прямоугольниками, путём перебора всех возможных разделений. Этот метод является чрезмерно вычислительно дорогим, потому что требует экспоненциальное время для своего выполнения.
• Квадратичный алгоритм. Этот алгоритм состоит из двух шагов. На первом шаге выбираются два семени будущих групп. Семена выбираются как прямоугольники, для которых разница между площадью их МОП и их собственной площадью максимальна. На втором шаге все оставшиеся прямоугольники последовательно присоединяются к одной из групп. Каждый раз тот прямоугольник, у которого максимальная разница между приращениями площади МОП групп, при
Рис. 2. Иллюстрация дилеммы: прокрытие против пересечения
его присоединении, присоединяется к той из групп, приращение площади МОП которой меньше.
• Линейный алгоритм. Этот алгоритм похож на квадратичный, но имеет два отличия, которые делают его линейным. Во-первых, семена выделяются вдоль осей, что позволяет избежать сравнения всех пар прямоугольников. Во-вторых, прямоугольники присоединяются к группам в произвольном порядке.
В работе [8] был предложен алгоритм Грина. Этот алгоритм похож на линейный алгоритм Гуттмана, но он использует сортировку вдоль осей и разделяет элементы пополам между группами в соответствии с этой сортировкой.
В работе [5] предложен алгоритм разделения И*-дерева. Важной особенностью этой работы является использование периметра прямоугольника в качестве критерия оптимизации. Этот алгоритм похож на алгоритм Грина, однако содержит два отличия. Во-первых, для разделения выбирается ось с минимальной суммой всех периметров МОП групп, для всех возможных разделений на основе сортировки вдоль данной оси. Во-вторых, в этом алгоритме элементы не делятся пополам, а ищется минимум пересечения между всеми возможными разделениями, основанными на сортировке вдоль данной оси. В [15] проводится детальный анализ производительности И*-дерева. Оптимизация И*-дерева для неравномерно распределенных данных представлена в [11].
В работе [3] предложен новый линейный алгоритм. Этот алгоритм делает разделение прямоугольников вдоль осей, основанное на близости прямоугольников границам области значений по этой оси. После этого делается выбор между полученными разделениями на основе степени пересечения и соотношения распределения элементов.
В работе [2] предложен новый алгоритм, который сосредоточен на уменьшении общей площади МОП групп. Поэтому этот алгоритм показывает превосходство в том случае, когда запрашиваемая площадь относительно велика.
Существует также недавнее исследование в этой области [7], где алгоритм разделения узла принимает решение о том, разделить ли узел на два или три узла.
В работах [1] и [13] представлены варианты И-дерева, где предлагается допускать мягкую разбалансировку взамен на значительное улучшение свойств дерева.
Поскольку существуют применения И-де-рева для одномерного случая, то одномерное разделение для И-дерева может быть рассмотрено как отдельная проблема. Одна из негативных сторон применения И-дерева в одномерном случае - это его слабая производительность для сильно пересекающихся данных, таких как интервалы времени актуальности или интервалы транзакционного времени [14]. Этот аспект может быть частично нивелирован введением нового алгоритма разделения узла для одномерного случая, который может лучше обрабатывать случай сильно пересекающихся данных.
I_ 1 _!
2
Рис. 3. Разделение, для которого существует разделяющая пара
Рис. 4. Разделение, для которого не существует разделяющая пара
Квадратичный и линейный алгоритмы Гуттмана могут быть легко применены к одномерному случаю. Для квадратичного алгоритма Гуттмана нет причин использовать квадратичный алгоритм для выбора семян, потому что в качестве наиболее удаленных интервалов можно взять те интервалы, которые содержат общую нижнюю и верхнюю границы. Алгоритмы Грина и И*-дерева содержат одномерное разделение в качестве составной части. Новый линейный алгоритм может быть также применен к одномерному случаю, но в данном случае есть только одна пространственная ось, и поэтому не приходится выбирать между разделениями вдоль разных осей.
3. ПРЕДЛАГАЕМЫЙ АЛГОРИТМ
3.1. Определения
В одномерном алгоритме разделения входные элементы содержат множество I интервалов Хг. I = {хг}. Определяется своими верхней и нижней границами. хг = (¡г,щ). Общая нижняя граница - это I = тт{1г}, а общая верхняя граница - и = тах{иг}. Вначале мы ограничим
рассмотрение теми разделениями, где одна из групп содерж
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.