PH-дерево

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

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 -ближайших соседей более сложны.

Поиск

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

function lookup(key) is
    entry ← get_root_entry()    // if the tree is not empty the root entry contains a root node
    while entry != NIL && entry.is_subnode() do 
        node ← entry.get_node()
        entry ← node.get_entry(key)  
    repeat
return entry                    // entry can be NIL

function get_entry(key) is
    node ← current node
    h ← extract_bits_at_depth(key, node.get_depth()}
    entry ← node.get_entry_at(h)  
return entry                    // entry can be NIL

Вставить

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

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

function insert(node, key, value)
    level ← node.get_level()            // Level is 0 for root
    h ← extract_bits_at_level(key, level)
    entry ← node.get_entry(h)
    if entry == NIL then
        // Case 1.
        entry_new ← create_entry(key, value)
        node.set_entry(h, entry_new)       
    else if !entry.is_subnode() && entry.get_key() == key then
       // Case 2. Collision, there is already an entry
       return ← failed_insertion        
    else
        // Case 3.
        level_diff ← get_level_of_difference(key, entry.get_key()) 
        entry_new ← create_entry(key, value)
        // new subnode with existing entry and new entry
        subnode_new ← create_node(level_diff, entry, entry_new) 
        node.set_entry(h, subnode_new)     
    end if
return

Удалить

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

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

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

function query(node, min, max, result_list) is
    foreach entry ← node.get_entries() do
        if entry.is_subnode() then
            if entry.get_prefix() >= min and entry.get_prefix() <= max then
                query(entry.get_subnode(), min, max, result_list)
            end if
        else
            if entry.get_key() >= min and entry.get_key() <= max then
                result_list.add(entry)
            end if
        end if
    repeat
return

Чтобы точно оценить сложность времени запроса, анализ должен включать размерность $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}$ не пересекаются с полем запроса. Доказательство доступно в. Благодаря этому приведенную выше функцию запроса можно улучшить до:

function query(node, min, max, result_list) is
    h_min ← calculate h_min
    h_max ← calculate h_max
    for each entry ← node.get_entries_range(h_min, h_max) do
        [ ... ]
    repeat
return

Расчет $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)$.

function is_overlap(h, h_min, h_max) is
return (h | h_min) & h_max == h            // evaluates to 'true' if quadrant and query overlap.

function query(node, min, max, result_list) is
    h_min ← calculate h_min
    h_max ← calculate h_max
    for each entry ← node.get_entries_range(h_min, h_max) do
        h ← entry.get_h();
        if (h | h_min) & h_max == h then   // evaluates to 'true' if quadrant and query overlap.
           [ ... ]
        end if
    repeat
return

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

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

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

function increment_h(h_input, h_min, h_max) is
    h_out = h_input | (~ h_max )        // pre - mask
    h_out += 1                          // increment
    h_out = ( h_out & h_max ) | h_min   // post - mask
return h_out

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

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

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

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

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

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

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

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

long encode(double value) {
    long r = Double.doubleToRawLongBits(value);
    return (r >= 0) ? r : r ^ 0x7FFFFFFFFFFFFFFFL;
}

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

std::int64_t encode(double value) {
    std::int64_t r;
    memcpy(&r, &value, sizeof(r));
    return r >= 0 ? r : r ^ 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 с подробным описанием, примерами и сравнением производительности