Покровное дерево
-
Описание дерева обложек
- Дерево обложек — структура данных для ускорения поиска ближайшего соседа.
- Усовершенствование структуры данных Navigating Net.
- Связано с другими структурами данных для индексации данных с низкой размерностью.
-
Структура дерева обложек
- Иерархия уровней, где верхний уровень содержит корневую точку, а нижний — все точки в метрическом пространстве.
- Каждому уровню C соответствует целочисленное значение i, уменьшающееся по мере спуска по дереву.
- Свойства уровней: гнездование, покрытие, разделение.
-
Сложность поиска
- Поиск ближайших соседей в O(η ∗ log n), где η — константа, связанная с размерностью набора данных, а n — мощность.
- В высокоразмерных метрических пространствах η константа нетривиальна.
- Ограничение по времени поиска: O(c12 log n), где c — константа расширения набора данных.
-
Сложность вставки
- Добавление новой точки в дерево обложек занимает O(c6 log n) времени.
- Существуют методы, улучшающие производительность на практике.
-
Сложность пространства
- Дерево обложек использует неявное представление для отслеживания повторяющихся точек.
- Требуется всего лишь O(n) пространства.
-
Дополнительные ресурсы
- Поиск ближайшего соседа, kd-дерево, М-дерево.
- Рекомендации: Алина Бейгельзимер, Шам Какаде и Джон Лэнгфорд.
- Страница с деревом обложек JL.
- Реализация дерева обложек на C++ и Java.