PH-дерево

PH-дерево
Тип	дерево, карта
Изобретенный	2014
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск О( журнал n ) О( журнал n ) Вставлять О( журнал n ) О( журнал n ) Удалить О( журнал n ) О( журнал n ) Пространственная сложность Космос На ​ ) На ​ )

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

Обзор

Базовое PH-дерево представляет собой пространственный индекс, который сопоставляет ключи, представляющие собой d -мерные векторы с целыми числами, со значениями, определяемыми пользователем. PH-дерево является многомерным обобщением битового дерева Crit в том смысле, что битовое дерево Crit эквивалентно PH-дереву с $1$-мерные ключи. Как и битовое дерево Crit, и в отличие от большинства других пространственных индексов, PH-дерево представляет собой карту, а не мультикарту .

d - мерное PH-дерево — это дерево узлов, в котором каждый узел разделяет пространство, разделяя его на $2^{d}$ квадранты (см . ниже , как масштабируются потенциально большие узлы с многомерными данными). Каждый квадрант содержит не более одной записи : либо пару ключ-значение (листовой квадрант), либо пару ключ-подузел. Для пары ключ-подузел ключ представляет центр подузла. Ключ также является общим префиксом (битовым представлением) всех ключей в подузле и его дочерних подузлах. Каждый узел имеет как минимум две записи, в противном случае он объединяется с родительским узлом.

Некоторые другие структурные свойства PH-деревьев:

• Они есть $2^{n}$-арные деревья.
• Они по своей сути несбалансированы , но дисбаланс ограничен, поскольку их глубина ограничена разрядностью ключей, например 32 для $d$-мерный ключ с 32-битными целыми числами.
• Операции вставки или удаления приводят к изменению ровно одного узла и, возможно, к добавлению или удалению второго узла. Это может быть полезно для параллельных реализаций. Это также означает небольшое изменение стоимости модификации.
• Их структура не зависит от порядка вставки/удаления.

Стратегия разделения

Подобно большинству квадродеревьев , PH-дерево представляет собой иерархию узлов, в которой каждый узел разбивает пространство во всех d измерениях. Таким образом, узел может иметь до $2^{d}$ подузлы, по одному на каждый квадрант.

Адресация гиперкуба с помощью битовых строк

Нумерация квадрантов

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

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

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

1D пример

Пример с тремя одномерными ключами с 8-битными значениями: $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$, $k_{1}=\{4\}_{10}=\{00000100\}_{2}$ и $k_{2}=\{35\}_{10}=\{00100011\}_{2}$. Добавление $k_{0}$ и $k_{1}$ в пустое дерево приводит к одному узлу. Два ключа сначала отличаются своим 6-м битом, поэтому узел имеет уровень $L=5$ (начиная с 0). Узел имеет 5-битный префикс, представляющий общие 5 битов обоих ключей. Узел имеет два квадранта, каждый ключ хранится в одном квадранте. Добавление третьего ключа $k_{3}$ приводит к появлению одного дополнительного узла в $L=2$ с одним квадрантом, содержащим исходный узел в качестве подузла, а другой квадрантом, содержащим новый ключ $k_{2}$.

Пример PH-дерева с двумя 2D-ключами в одном узле

2D-пример

Благодаря 2D-ключам каждый узел имеет $2^{d}=4$ квадранты. Положение квадранта, в котором хранится ключ, извлекается из соответствующих битов ключей, по одному биту от каждого измерения. Четыре квадранта узла образуют двумерный гиперкуб (квадранты могут быть пустыми). Биты, извлеченные из ключей, образуют адрес гиперкуба. $h$, для $k_{0}\rightarrow h=\{00\}_{2}$ и для $k_{1}\rightarrow h=\{01\}_{2}$. $h$ фактически является положением квадранта в гиперкубе узла.

Структура узла

Порядок записей в узле всегда соответствует Z-порядку .Записи в узле могут, например, храниться в массивах фиксированного размера размером $2^{d}$. h тогда фактически является индексом массива квадранта. Это позволяет искать, вставлять и удалять с помощью $O(1)$ и нет необходимости хранить h . Однако космическая сложность $O(2^{d})$ на узел, поэтому он менее подходит для данных большой размерности.

Другое решение — хранить записи в отсортированной коллекции, например в динамических массивах и/или B-деревьях . Это замедляет операции поиска до $O(\log {n_{node\_entries}})$ но снижает потребление памяти до $O(n_{node\_entries})$.

Исходная реализация была нацелена на минимальное потребление памяти за счет переключения между фиксированным и динамическим представлением массива в зависимости от того, какое из них использует меньше памяти. Другие реализации [1] [2] не переключаются динамически, а используют фиксированные массивы для $d\lesssim 4$, динамические массивы для $d\lesssim 8$ и B-деревья для данных большой размерности.

Операции

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

Поиск

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

 функции  (ключ) поиск     запись ← get_root_entry() // если дерево не пусто, корневая запись содержит корневой узел     в то время как  запись != NIL && вход.is_subnode()  сделать          узел ← вход.get_node()        запись ← node.get_entry(ключ)       повторите  возвращаемую  запись // запись может быть NIL 

функция  get_entry(key  )     узел ← текущий узел    h ← extract_bits_at_length(key, node.get_length()}    запись ← node.get_entry_at(h)   возвращаемая  запись // запись может быть NIL 

Вставить

Операция Insert вставляет в дерево новую пару ключ-значение, если только ее ключ еще не существует. Эта операция проходит по дереву, как функция поиска , а затем вставляет ключ в узел. Есть несколько случаев, которые следует учитывать:

1. Квадрант пуст, и мы можем просто вставить в него новую запись и вернуться.
2. Квадрант содержит запись пользователя с ключом, идентичным новой записи. Один из способов справиться с таким конфликтом — вернуть флаг, указывающий на неудачную вставку. Если дерево реализовано как мультикарта с коллекцией в качестве записи узла, новое значение добавляется к этой коллекции.
3. Квадрант содержит запись (запись пользователя или запись подузла) с другим ключом. В этом случае требуется заменить существующую запись новым подузлом, содержащим старую и новую записи.

функция  вставки (узел, ключ, значение)    level ← node.get_level() // Уровень для корня равен 0    h ← extract_bits_at_level(ключ, уровень)    запись ← node.get_entry(h)     если  запись == NIL,  то         // Случай 1.        enter_new ← create_entry(ключ, значение)        node.set_entry(h,Entry_new)            иначе, если  !entry.is_subnode() && enter.get_key() == ключ  , тогда        // Случай 2. Коллизия, запись уже есть        возврат  ← неудачная_вставка             еще         // Случай 3.        level_diff ← get_level_of_difference(key, вход.get_key())         enter_new ← create_entry(ключ, значение)        // новый подузел с существующей записью и новой записью        subnode_new ← create_node(level_diff, вход, вход_новый)         node.set_entry(h, subnode_new)          конец, если  вернуться 

Удалить

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

Оконные запросы

Оконные запросы — это запросы, которые возвращают все ключи, находящиеся внутри прямоугольного гипербокса , выровненного по оси . Их можно определить как две d -мерные точки. $min$ и $max$ которые представляют «нижний левый» и «верхний правый» углы поля запроса. Тривиальная реализация просматривает все записи в узле (начиная с корневого узла), и если запись соответствует, она либо добавляет ее в список результатов (если это пользовательская запись), либо рекурсивно обходит ее (если это подузел).

запрос функции  (узел, мин, макс, список_результатов)  — это      foreach  запись  ← node.get_entries() делать          , если  вход.is_subnode()  , то              если  вход.get_prefix() >= мин и вход.get_prefix() <= макс  , тогда                 запрос (entry.get_subnode(), мин, максимум, result_list)             конец, если          еще              , если  вход.get_key() >= мин и вход.get_key() <= макс  , тогда                 result_list.add(запись)             конец, если          конец, если      повторить  возврат 

Чтобы точно оценить сложность времени запроса, анализ должен включать размерность $d$.Обходя и сравнивая все $n_{node\_entries}$ записи в узле имеют временную сложность $O(d\cdot n_{node\_entries})$ потому что каждое сравнение $d$-мерный ключ с $min/max$ берет $O(d)$ время. Поскольку узлы могут иметь до $2^{d}$ записи, это плохо масштабируется с увеличением размерности $d$. Существуют различные способы улучшения этого подхода, используя адрес гиперкуба h .

Мин. ч и макс. ч

Идея состоит в том, чтобы найти минимальные и максимальные значения адресов квадранта. $h$ так, чтобы при поиске можно было избежать некоторых квадрантов, которые не перекрываются с полем запроса.Позволять $C$ быть центром узла (это равно префиксу узла) и $h_{min}$ и $h_{max}$ быть двумя битовыми строками с $d$ бит каждый. Кроме того, пусть индекс $i$ с $0\leq i<d$ указать $i$немного $h_{min}$ и $h_{max}$ и $i$'-е измерение $min$, $max$ и $C$.

Позволять $h_{min,i}=(min_{i}\leq C_{i})$ и $h_{max,i}=(max_{i}\geq C_{i})$. $h_{min}$ тогда есть ` $1$` для каждого измерения, где «нижняя» половина узла и все квадранты в нем не перекрываются с полем запроса. Сходным образом, $h_{min}$ имеет ` $0$` для каждого измерения, где «верхняя» половина не пересекается с полем запроса.

$h_{min}$ и $h_{max}$ затем представьте самое низкое и самое высокое $h$ в узле, который необходимо пройти. Квадранты с $h<h_{min}$ или $h>h_{max}$ не пересекаются с полем запроса. Доказательство доступно в. Благодаря этому приведенную выше функцию запроса можно улучшить до:

запрос функции  (узел, мин, максимум, список_результатов  )     h_min ← рассчитать h_min    h_max ← рассчитать h_max     для каждой  записи ← node.get_entries_range(h_min, h_max)  do         [ ... ]     повторный  возврат 

Расчет $h_{min}$ и $h_{max}$ является $O(2d)=O(d)$.В зависимости от распределения занятых квадрантов в узле этот подход позволит избежать от «нет» до почти всех ключевых сравнений. Это уменьшает среднее время обхода, но результирующая сложность по-прежнему остается низкой. $O(d+d\cdot n_{node\_entries})$.

Проверьте квадранты на предмет совпадения с полем запроса

Между $h_{min}$ и $h_{max}$ все еще могут быть квадранты, которые не перекрываются с полем запроса.Идея: $h_{min}$ и $h_{max}$ каждый имеет один бит для каждого измерения, который указывает, перекрывается ли поле запроса с нижней/верхней половиной узла в этом измерении. Это можно использовать для быстрой проверки того, является ли квадрант $h$ перекрывается с полем запроса без необходимости сравнения $d$-пространственные ключи: квадрант $h$ перекрывается с полем запроса, если для каждого ` $0$` немного вошел $h$ есть соответствующий ` $0$` немного вошел $h_{min}$ и для каждого ` $1$` немного вошел $h$ есть соответствующий ` $1$` немного вошел $h_{max}$. Таким образом, на ЦП с 64-битными регистрами можно проверить перекрытие до $64$-мерные ключи в $O(1)$.

функция  is_overlap(h, h_min, h_max)  возвращает  (h | h_min )  & h_max == h // оценивается как «истина», если квадрант и запрос перекрываются. 

запрос функции  (узел, мин, максимум, список_результатов  )     h_min ← рассчитать h_min    h_max ← рассчитать h_max     для каждой  записи ← node.get_entries_range(h_min, h_max)  do         ч ← вход.get_h();         if  (h | h_min) & h_max == h  then  // оценивается как «истина», если квадрант и запрос перекрываются.           [ ... ]         закончить, если      повторить  возврат 

Результирующая временная сложность равна $O(d+n_{node\_entries})$ по сравнению с $O(d\cdot n_{node\_entries})$ полной итерации.

Обход квадрантов, пересекающихся с полем запроса

Для более высоких измерений с более крупными узлами также можно избежать повторения всех $h$ и вместо этого напрямую рассчитать следующую более высокую $h$ который перекрывается с полем запроса. Первый шаг ставит ` $1$`-биты в заданное $h_{input}$ для всех квадрантов, которые не пересекаются с полем запроса. Второй шаг увеличивает адаптированный $h$ и добавленный ` $1$`-биты вызывают переполнение, так что непересекающиеся квадранты пропускаются. Последний шаг удаляет все нежелательные биты, используемые для запуска переполнения. Логика подробно описана в . Расчет работает следующим образом:

функция  приращения_h(h_input, h_min, h_max  )     h_out = h_input | (~ h_max) // предварительная маска    h_out += 1 // приращение    h_out = (h_out & h_max) | h_min // сообщение — маска вернуть  h_out 

Опять же, для $d\leq 64$ это можно сделать на большинстве процессоров в $O(1)$.Результирующая временная сложность прохождения узла равна $O(d+n_{overlapping\_quadrants})$. Это работает лучше всего, если большая часть квадрантов, пересекающихся с полем запроса, занята записью.

k- ближайшие соседи

Поиск k ближайших соседей может быть реализован с использованием стандартных алгоритмов.

Клавиши с плавающей запятой

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

Преобразование без потерь

Преобразование значения с плавающей запятой без потерь в целое значение (и обратно) без потерь, если точность может быть достигнута путем простой интерпретации 32 или 64 бит значения с плавающей запятой как целое число (с 32 или 64 битами).Благодаря тому, как IEEE 754 кодирует значения с плавающей запятой, результирующие целочисленные значения имеют тот же порядок, что и исходные значения с плавающей запятой, по крайней мере, для положительных значений. Упорядочение отрицательных значений может быть достигнуто путем инвертирования беззнаковых битов.

Пример реализации на Java :

длинное   кодирование  (  двойное   значение  )   {      long   r   =   Double  .  DoubleToRawLongBits  (  значение  );      возврат   (  р   ​​>=   0  )   ?   р   :   р   ^   0x7FFFFFFFFFFFFFFFL  ;  } 

Пример реализации на C++ :

std  ::  int64_t   кодировать  (  двойное   значение  )   {      std  ::  int64_t   r  ;      memcpy  (  &  r  ,   &  value  ,   sizeof  (  r  ));      вернуть   р   >=   0   ?   р   :   р   ^   0x7FFFFFFFFFFFFFFFL  ;  } 

Кодирование (и обратное декодирование) осуществляется без потерь для всех значений с плавающей запятой. Порядок хорошо работает на практике, в том числе $\pm \infty$ и $-0.0$. Однако целочисленное представление также превращается $NaN$ в нормальное сравнимое значение (меньше бесконечности), бесконечности сравнимы друг с другом и $0.0$ больше, чем $-0.0$. Это означает, что, например, диапазон запроса $[0.0,10.0]$ будет не соответствовать значению $-0.0$. Чтобы соответствовать $-0.0$ диапазон запроса должен быть $[-0.0,10.0]$.

Клавиши гипербокса

Чтобы хранить объемы (гиперблоки, выровненные по осям) в качестве ключей, реализации обычно используют угловое представление. который преобразует два $d$-размерные минимальные и максимальные углы коробки в единый ключ с $2d$ размеры, например, путем их чередования: $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$.

Это тривиально работает для операций поиска, вставки и удаления. Оконные запросы необходимо преобразовать из $d$-мерные векторы в $2d$-мерные векторы. Например, для запроса окна, который соответствует всем полям, полностью находящимся внутри поля запроса, ключи запроса:

$k_{min}=\{min_{0},min_{0},min_{1},min_{1},...,min_{d-1},min_{d-1}\}$

$k_{max}=\{max_{0},max_{0},max_{1},max_{1},...,max_{d-1},max_{d-1}\}$

Для операции запроса окна, которая соответствует всем полям, пересекающимся с полем запроса, ключи запроса:

$k_{min}=\{-\infty ,min_{0},-\infty ,min_{1},...,-\infty ,min_{d-1}\}$

$k_{max}=\{max_{0},+\infty ,max_{1},+\infty ,...,max_{d-1},+\infty \}$

Масштабируемость

В больших размерах с менее чем $2^{d}$ записей, PH-дерево может иметь только один узел, эффективно «вырождаясь» в B-дерево с кривой Z-порядка . Операции добавления/удаления/поиска остаются $O(\log {n})$ и оконные запросы могут использовать фильтры квадрантов . Однако это не может избежать проклятия размерности , поскольку для данных большой размерности $d=50$ или $d=100$ PH-дерево лишь незначительно лучше полного сканирования.

Использует

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

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

Реализации

• Java: репозиторий GitHub от оригинального изобретателя.
• C++: репозиторий GitHub от оригинального изобретателя
• C++: репозиторий GitHub.
• C++: репозиторий GitHub.

См. также

• Разделение двоичного пространства
• Бинарная мозаика
• k -d дерево
• Октри
• Четырехдерево
• R-дерево
• UB-дерево
• Пространственная база данных

Внешние ссылки

• Сайт PH-tree с подробным описанием, примерами и сравнением производительности.