Использование многомерных деревьев для обработки многомерной информации

Размещено на http://www.allbest.ru/

Использование многомерных деревьев для обработки многомерной информации

Математическое моделирование и информационные технологии

УДК 004.651.4

В.К. Гулаков, А.О. Трубаков, Е.О. Трубаков

13.07.07

Аннотация

Рассмотрена проблема выбора и использования многомерных структур данных в качестве основы системы хранения многомерной информации. Исследовано реальное быстродействие часто используемых алгоритмов. Даны рекомендации по выбору многомерной структуры при определенных начальных условиях.

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

Многомерные структуры хранения информации - наиболее динамически развивающаяся область. В последнее время появилось много разных алгоритмов и методов [5,9]. Однако в отечественной литературе данных по этому вопросу не так уж и много. К тому же чрезвычайно сложно выполнить сравнительный анализ и оценку производительности этих алгоритмов в тех или иных случаях. Между тем, при выборе внутренних структур системы бывает крайне необходимо изначально проанализировать этот выбор [6]. Неправильно выбранный способ хранения информации может привести к частичной или даже полной неработоспособности системы в естественных условиях эксплуатации (например, очень большое время поиска интересующей информации и как следствие большое время отклика системы).

Многомерная информация. Пусть имеется множество записей, каждая из которых характеризуется n ключами: K₀, K₁, … , K_n-1. Множество значений любого ключа можно рассматривать как измерение. Таким образом, получаем данные в n измерениях, или многомерные данные. При этом сама запись может рассматриваться как точка в n-мерном пространстве.

Характерными возможностями многомерной информации можно считать:

- поддержку различных типов запросов;

- возможность динамической реорганизации;

- небольшое число обращений к диску при выполнении простых операций;

- высокий коэффициент использования памяти (не менее 70%);

- отсутствие «предпочтительных» измерений.

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

- запросы по точному совпадению (exact-match queries): все координаты (атрибуты) зафиксированы в запросе;

- запросы по частичному совпадению (partial-match queries): в запросе указываются t из n координат, остальные координаты могут принимать произвольные значения;

- пространственные запросы (range queries): для каждого измерения указан диапазон значений (в случае точного совпадения - диапазон [c,c], в случае частичного - () для незаданной координаты);

- запросы по наилучшему совпадению (best-match queries): найти ближайшего соседа для указанной точки/области.

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

KD-деревья. Если данные, используемые в системе, являются точечными (каждая запись представляет собой «кортеж» из n элементов, который геометрически можно представить в виде точки в n-мерном пространстве), то для их хранения удобно применять так называемые KD-деревья [2-4].

Каждой вершине Т, входящей в KD-дерево, соответствует некоторое значение DIMENSION(T) (это значение для корня равно нулю, для всех его сыновей - единице и т.д.). В общем случае DIMENSION вершины T_i рассчитывается по формуле

DIMENSION(T_i) = L_Тi mod N,

где L_Тi - уровень, на котором расположена данная вершина, считая от корня (корень находится на нулевом уровне, его сыновья - на первом и т.д.); N - количество измерений.

С учетом введенной величины, приняв j = DIMENSION(T_i), получим следующие правила KD-дерева: левый потомок вершины T_i имеет j-й ключ, меньший, чем j-й ключ данного узла, а правый потомок - j-й ключ, больший, чем j-й ключ данного узла, т.е.

K_j(Left(T_i)) < K_j(T_i) < K_j(Right(T_i)),

где Left(T_i) - левый потомок вершины T_i; Right (T_i) - правый потомок вершины T_i; K_j(T_i) - j-й ключ вершины T_i.

В случае равенства j-х ключей наиболее полезной в большинстве систем может оказаться следующая стратегия. Для вершины T_i определяют некоторый суперключ SuperK_j(T_i):

SuperK_j(T_i) = K_j(T_i) K_j+1(T_i) … K_n-1(T_i) K₀(T_i) K₁(T_i) … K_j-1(T_i).

Таким образом, в качестве суперключа принимают циклическую конкатенацию ключей, начинающуюся с ключа K_j. Тогда описанное условие заменяется следующим: левый потомок вершины T_i имеет j-й суперключ, меньший, чем j-й суперключ данного узла, а правый потомок - j-й суперключ, больший, чем j-й суперключ данного узла.

SuperK_j(Left(T_i)) < SuperK_j(T_i) < SuperK_j(Right(T_i)).

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

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

Вершиной дерева была выбрана точка, соответствующая г.Москве. Уровень этой вершины равен 0, DIMENSION - тоже 0, следовательно, она разбивает пространство на две половины в зависимости от первой координаты их расположения. В левое поддерево помещаются города, расположенные западнее Москвы (Брянск, Санкт-Петербург, Орел), а в правое - восточнее (Липецк, Воронеж, Рязань). Следующая вершина разбивает каждое из поддеревьев снова на две части, но уже в зависимости от другой координаты: севернее или южнее находятся города относительно данного, - и т.д.

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

а) б)

Рис. 1. Пример KD-дерева: а - карта городов; б - построенное KD-дерево

Деревья Z-порядка. Еще одним вариантом деревьев, используемых для хранения n-мерной информации, являются деревья Z-порядка. В этих структурах использована идея отображения многомерной величины в одномерное пространство. Одномерное пространство проще при реализации и для него существуют эффективные структуры данных, например бинарные деревья, или B-деревья. Эти структуры требуют линейного выравнивания элементов и характеризуются логарифмическим временем доступа к элементам дерева.

Для того чтобы отобразить многомерный элемент T, характеризующийся n ключами (K₀, K₁, … , K_n-1), введем функцию перемешивания MIX. Данная функция разбивает каждый ключ на m частей. Получаем величину, у которой каждый ключ, в свою очередь, также является составным:

K_i = <K_i,0 , K_i,1 , K_i,2 , … , K_i,m-2 , K_i,m-1>.

Чаще всего такое разбиение связано с принципами хранения информации. Например, если ключи вершины T являются четырехбайтовыми числами, а m=32, то разбиение происходит по одному биту, т.е. размер величины K_i,j равен одному биту.

Перемешанный суперключ определяется по формуле

MIX(T) = <[K_0,0 , K_0,1 ,…, K_0,m-1], [K_1,0 , K_1,1 ,…, K_1,m-1], … , [K_n-1,0 , K_n-1,1 ,…, K_n-1,m-1]>,

где K_i,j - j-й компонент i-го ключа; [K_1,0 , K_1,1 ,…, K_1,m-1] - сцепление j-х компонентов всех ключей.

Дерево Z-порядка графически можно представить в виде кривой, заполняющей пространство (space filling curves). Пример такой кривой при m=4 изображен на рис. 2.

Кривая, заполняющая пространство, обладает следующими свойствами:

- полностью покрывает все пространство;

- проходит через каждую точку только один раз, но не пересекается сама с собой;

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

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

Рис. 2. Кривая, заполняющая пространство

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

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

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

1. R-деревья. Очень популярная структура, использующаяся в некоторых современных хранилищах данных. Каждый узел такого дерева содержит координаты некоторого n-мерного параллелепипеда (MBR). В поддерево попадают только те вершины, которые находятся в пространстве этого параллелепипеда. R-деревья являются сбалансированными по высоте деревьями с индексными записями в листьях.

В настоящее время существует ряд модификаций R-деревьев, например R*-деревья [9,10].

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

3. Quadro-деревья. Данный вид деревьев похож на KD-деревья, однако здесь каждая вершина имеет четы 2ⁿ потомков, т.е. деление пространства происходит в каждой вершине не по одному измерению, как в KD-дереве, а сразу по всем. Для двухмерного случая каждая вершина разбивает все множество вершин на четыре группы. В первую из них попадают вершины, находящиеся выше и левее данной, во вторую - выше и правее, в третью - ниже и правее, в четвертую - ниже и левее. Таким образом, на первый взгляд данное дерево является более эффективной структурой хранения информации, так как в отличие от предыдущих видов имеет глубину, равную не O(log₂(N)), а O(log₄(N)), что должно привести к многократному уменьшению времени работы системы. Однако для достижения таких показателей дерево должно быть сбалансировано, что не всегда возможно в случае применения Quadro-деревьев [1].

4. Многомерные B-деревья. Данные деревья являются развитием теории KD-деревьев для внешней памяти. Это деревьями с множественным ветвлением, в которых определено два типа узлов:

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

- страницы с точками - листья, непосредственно содержащие точки.

5. TV-деревья (Telescopic-Vector tree). Дерево, специально предназначенное для представления точечных данных большой размерности. В таких случаях появляются некоторые частные ситуации, связанные с конкретной реализацией. Например, при большом количестве измерений наблюдается явление совпадения большой части координатных значений у рядом стоящих точек. Это приводит к неэффективности большинства структур хранения многомерной информации.

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

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

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

KD-дерево и дерево Z-порядка являются бинарными, поэтому теоретически найденная сложность поиска по точному совпадению имеет логарифмический вид O(log₂(N)). Однако, как показывает практика, применение этих деревьев даже в небольших 2- или 3-мерных системах дает разное время поиска и обработки запросов. Такие результаты можно объяснить разной структурой деревьев (расположением вершин в дереве), что играет существенную роль в пространственных запросах.

Для определения практической трудоемкости процедуры поиска был реализован ряд программ в виде консольных приложений. Для экспериментов был выбран двухмерный случай. После многократного запуска программ на разных ЭВМ и с разными начальными условиями, исходными и поисковыми выборками были получены экспериментальные данные, обработанные статистическими методами. Каждый из опытов был проведен тысячу раз. Это необходимо из-за невозможности абсолютно точного измерения времени работы приложения. Поэтому только при большом количестве выборок и проводимых опытов можно говорить о приемлемой точности измерения [8]. Результаты опытов в абсолютных величинах получились различными (в зависимости от ЭВМ, на которой они проводились, а также начального и поискового множества вершин). Однако относительная разница между алгоритмами не зависит от перечисленных факторов, поэтому результаты опытов можно считать адекватными.

Полученные данные имеют экспериментальный характер, следовательно, прежде чем делать какие-либо выводы, необходимо провести их статистическую обработку. Для начала необходимо определить, совпадает ли функция распределения с некоторой вычисленной по выборочным параметрам теоретической функцией эмпирического распределения (проверка статистической теории согласия). Из рис. 3 видно, что в качестве гипотезы стоит принять гипотезу о нормальности распределения. Отклонение от нормального распределения может быть обнаружено только при больших объемах опытных данных, поэтому каждое измерение было проведено многократно. В качестве критерия проверки был выбран критерий Эппса-Палли, предусмотренный ГОСТ Р ИСО 5479-2002 [7]. Отклонение рассчитывалось по формуле

,

где;.

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

Результаты всех опытов не приводятся в данной статье вследствие их малозначительности и ограниченности рамок печатного издания. Ниже будут приведены лишь их обработанные результаты и выводы.

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

1. Запросы по точному совпадению (exact-match queries). Это наиболее распространенный вид запросов. Все координаты (атрибуты) искомого объекта зафиксированы в самом запросе, а процедура поиска считается успешной только в том случае, если найдена вершина в дереве с полным совпадением всех ключей.

,

где - i-й ключ в запросе; - i-й ключ проверяемой вершины.

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

На рис. 4 представлены результаты одной из серий опытов. Было построено дерево, содержащее 100 000 двухмерных вершин, и измерено время поиска 10 000 элементов в нем. Опыт был воспроизведен 1000 раз, результаты обработаны при помощи математического пакета MathCAD.

На рис. 4 слева находится функция распределения плотности вероятности измеренного времени поиска по точному совпадению в KD-дереве, а справа - аналогичное распределение для дерева Z-порядка.

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

,

где - время поиска в i-м опыте по KD-дереву; - количество раз, которое выпало время .

Расчет показал, что относительная разница временной сложности этих алгоритмов приблизительно составляет 3%. Такая разница является не принципиальной для большинства систем, поэтому в системах, преимущественно использующих запросы по точному совпадению, применение любого из этих алгоритмов будет давать приблизительно равное время поиска. Однако, как было замечено в начале статьи, деревья Z-порядка являются более изученными. Для них разработаны эффективные алгоритмы, позволяющие поддерживать дерево в сбалансированном виде при вставке новых и удалении существующих вершин. Для KD-дерева подобные алгоритмы требуют серьезной перестройки всей организации дерева и являются вычислительно сложными. Поэтому в системах, использующих только поиск по точному совпадению, применение деревьев Z-порядка будет более оправданно и эффективно.

2. Пространственные запросы (range queries). Для данного вида запросов характерна установка для каждого измерения диапазона значений. Вершина в дереве считается удовлетворяющей данному запросу только в том случае, если все ее ключи удовлетворяют соответствующим диапазонам значений.

,

где - i-й ключ проверяемой вершины; - левая граница i-го ключа, заданная в запросе; - правая граница i-го ключа, заданная в запросе.

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

Для определения скорости работы алгоритмов было построено дерево с 10 000 вершин и выполнен запрос на поиск элементов, попавших в 1000 регионов поиска. Данный опыт также был повторен 1000 раз. Плотность вероятности измеренного времени поиска изображена на рис. 5.

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

В отличие от предыдущей серии опытов результаты для пространственного поиска являются более впечатляющими. Дерево Z-порядка показало себя хуже на 58%, что очень существенно для многих систем. Поэтому при выборе структуры для системы, в которой пространственные запросы являются неотъемлемой частью, более предпочтительно использование KD-деревьев.

3. Запросы по наилучшему совпадению (best-match queries). Некоторый класс задач нацелен на использование поиска вершины, находящейся на минимальном расстоянии от данной. В одних системах это может быть поиском ближайшего соседа одной из вершин дерева, в других - поиском вершины, находящейся вблизи заданной точки пространства.

Математически данная задача сводится к следующему. Дана некоторая n-мерная запись. Найти в дереве такую вершину , чтобы выполнялось условие многомерный информация пространственный

,

где - вершина, для которой выполняется поиск ближайшего соседа; - искомая вершина; - расстояние между вершинами и , которое можно найти по формуле

.

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

.

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

Серия опытов по сравнению вычислительной эффективности двух структур для алгоритмов поиска ближайшего соседа дала самые впечатляющие результаты. Разница математических ожиданий времени поиска в относительных единицах составила 74%. Поэтому в системах с такими запросами одномерные структуры, подобные деревьям Z-порядка, являются неприменимыми. Это можно объяснить тем, что в KD-дереве, имеющем многомерную структуру, вершины, находящиеся рядом, с большой долей вероятности будут находиться рядом и в пространстве, в то время как для деревьев Z-порядка это справедливо только в случае очень маленького шага разбиения ключей.

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

Список литературы

1. Кнут, Д. Искусство программирования. Т.3. Сортировка и поиск / Д. Кнут. - М.: Вильямс, 2000. - 832 с.

2. Bentley, J.L. Multidimensional binary search trees used for associative searching / J.L. Bentley // Comm. of ACM. - 1975. - P. 509-517.

3. Bentley, J.L. Multidimensional binary search trees in database applications / J L. Bentley // IEEE Trans, on Software Eng. -- 1979. -- Vol. SE-5, N 4. -- P. 333--340.

4. Bentley, J.L. K-d Trees for Semidynamic Point Sets. / J.L. Bentley // SCG '90: Proc. 6th Annual Symposium on Computational Geometry. - 1990. - P. 187.

5. Christian, Duncan A. Balanced aspect ratio trees: combining the advantages of k-d trees and octrees / Duncan A. Christian, Michael T. Goodrich, Stephen Kobourov // Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms. - Baltimore, Maryland, United States, 1999. - P. 300-309.

6. Препарата, Ф. Вычислительная геометрия: Введение: [пер. с англ.] / Ф. Препарата, М. Шеймос. - М.: Мир, 1989. - 478 с.

7. ГОСТ Р ИСО 5479-2002. Статистические методы. Проверка отклонения распределения вероятностей от нормального распределения. - М.: Изд-во стандартов, 2002. - 30 с.

8. Новицкий, П.В. Оценка погрешностей результатов измерений / П.В. Новицкий, И.А. Зограф. - Л.: Энергоатомиздат, 1991. - 303 с.

9. Beckmann, N. The R* tree: An Effecient and Robust Access Method for Points and Rectangles / N. Beckmann, H. Kriegel, R. Schneider, B. Seeger. // ACM. - 1990. - P. 322-331.

10. Kriegel, H. Performance comparison of point and spatial access methods / H. Kriegel, M. Schiwietz, R. Schneider, B. Seeger // Proc. Symp. On the Design and Implementation of Large Spatiol Databases: Lecture Notes in Computer Science. - Santa-Barbara, 1989.

Размещено на Allbest.ru