PH-дерево
-
Структура PH-дерева
- PH-дерево — это древовидная структура данных для пространственной индексации многомерных данных.
- Использует политику разделения на основе битов, аналогичную битовым деревьям Crit.
- Каждый узел разделяет пространство на 2^d квадрантов.
-
Стратегия разделения
- Каждый узел имеет до 2^d подузлов, по одному для каждого квадранта.
- Ключи определяются по битам многомерных ключей.
- Все ключи с одинаковыми начальными битами хранятся в одной ветви дерева.
-
Пример в 1D
- Пример с тремя одномерными ключами показывает, как дерево растет и разделяется.
- Добавление ключей приводит к появлению новых узлов и квадрантов.
-
Двумерный пример
- Каждый узел имеет 2^d квадрантов, образующих гиперкуб.
- Положение квадранта определяется по битам ключей.
-
Структура узла
- Записи хранятся в массивах фиксированного размера или отсортированных коллекциях.
- Фиксированные массивы обеспечивают быстрый поиск, но требуют больше памяти.
- Сортированные коллекции сокращают потребление памяти, но замедляют поиск.
-
Операции
- Поиск, вставка и удаление работают аналогично.
- Оконные запросы и поиск по k ближайшим соседям сложнее.
-
Минимальное время работы и максимальное время работы
- Идея состоит в использовании адресов квадрантов для оптимизации поиска.
- Минимальное время работы достигается за счет избегания квадрантов, не пересекающихся с полем запроса.
- Максимальное время работы достигается за счет полного обхода всех записей в узле.
-
Обход узла PH-дерева
- Обход узла начинается с определения минимального и максимального значений h.
- Квадранты с h < hmin или h > hmax не пересекаются с полем запроса.
- Вычислительный hmin и hmax имеет сложность O(2d) = O(d).
-
Проверка квадрантов на совпадение
- Между hmin и hmax могут быть квадранты, не пересекающиеся с полем запроса.
- Идея: hmin и hmax содержат биты для каждого измерения, указывающие на перекрытие.
- Проверка перекрытия выполняется быстро, сложность O(d+nnode_entries).
-
Пересечение квадрантов
- Для более высоких измерений можно избежать повторения всех h и вычислить следующую h, совпадающую с полем запроса.
- Первый шаг: добавление 1-битов в h для квадрантов, не пересекающихся с полем запроса.
- Второй шаг: увеличение адаптированного h и удаление нежелательных битов.
- Сложность: O(d+noverlap_quadrants).
-
k-ближайшие соседи
- Поиск ближайших соседей может быть реализован с использованием стандартных алгоритмов.
-
Ключи с плавающей запятой
- PH-дерево может хранить только целочисленные значения.
- Значения с плавающей запятой можно преобразовать в целые числа без потери точности.
- Преобразование выполняется без потерь для всех значений с плавающей запятой.
-
Ключи от гипербокса
- Для сохранения объемов используются угловое представление.
- Оконные запросы требуют преобразования из d-мерных векторов в 2d-мерные.
-
Масштабируемость
- При больших габаритах PH-дерево может иметь только один узел.
- Операции добавления/удаления/поиска остаются O(log n), оконные запросы могут использовать фильтры квадрантов.
- PH-анализ не избегает проклятия размерности для высокоразмерных данных.
-
Использование
- PH-дерево подходит для использования в памяти.
- Размер узлов фиксирован, что ограничивает использование в постоянном хранилище.
-
Реализации
- Java: репозиторий на GitHub от оригинального разработчика.
- C++: репозиторий на GitHub от оригинального разработчика и других разработчиков.
-
Смотрите также
- Разделение двоичного пространства
- Бинарная черепица
- дерево k-d
- Восьмиугольное дерево
- Квадрантное дерево
- R-дерево
- UB-дерево
- Пространственная база данных