Дерево обложки

редактировать

Тип структуры данных

Дерево обложки - это тип структуры данных в информатике, которая специально разработана для ускорения поиска ближайшего соседа. Это усовершенствованная структура данных Navigating Net, связанная с множеством других структур данных, разработанных для индексации низкоразмерных данных.

Дерево можно рассматривать как иерархию уровней с верхним уровнем содержащий корневую точку и нижний уровень, содержащий каждую точку в метрическом пространстве. Каждый уровень C связан с целочисленным значением i, которое уменьшается на единицу по мере спуска дерева. Каждый уровень C в дереве обложки имеет три важных свойства:

Вложенность : $C i ⊆ C i - 1 {\ displaystyle C_ {i} \ substeq C_ {i-1}}$ $C _ {{i}} \ substeq C _ {{i-1}}$
Покрытие : Для каждой точки $p ∈ C i - 1 {\ displaystyle p \ in C_ {i-1}}$ $p \ in C _ {{i-1}}$ существует точка $q ∈ C i {\ displaystyle q \ in C_ {i}}$ $q \ in C _ {{i}}$ такое, что расстояние от $p {\ displaystyle p}$ $p$ до $q {\ displaystyle q}$ $q$ меньше или равно $2 i {\ displaystyle 2 ^ {i}}$ $2 ^ { i}$ и ровно один такой $q {\ displaystyle q}$ $q$ является родительским для $p {\ displaystyle p}$ $p$ .
Разделение: Для всех точек $p, q ∈ C i {\ displaystyle p, q \ in C_ {i}}$ $p, q \ in C_ {i}$ , расстояние от $p {\ displaystyle p}$ $p$ до $q {\ displaystyle q}$ $q$ больше, чем $2 i {\ displaystyle 2 ^ {i}}$ $2 ^ { i}$ .

Содержание

1 Сложность
- 1.1 Найти
- 1.2 Вставить
- 1.3 Пробел
2 См. Также
3 Ссылки

Сложность

Найти

Как и другие деревья показателей, дерево покрытия позволяет выполнять поиск ближайшего соседа в $O (η ∗ журнал ⁡ N) {\ Displaystyle O (\ eta * \ log {n})}$ $O (\ eta * \ log {n})$ где $η {\ displaystyle \ eta}$ $\ eta$ - константа, связанная с размерностью набор данных, а n - мощность. Для сравнения, базовый линейный поиск требует $O (n) {\ displaystyle O (n)}$ $O (n)$ , что гораздо хуже зависит от $n {\ displaystyle n}$ $n$ . Однако в многомерных метрических пространствах константа $η {\ displaystyle \ eta}$ $\ eta$ нетривиальна, что означает, что ее нельзя игнорировать при анализе сложности. В отличие от других деревьев показателей, дерево покрытия имеет теоретическую границу своей константы, которая основана на константе расширения набора данных или константе удвоения (в случае приблизительного извлечения NN). Граница времени поиска: $O (c 12 log ⁡ n) {\ displaystyle O (c ^ {12} \ log {n})}$ $O (c ^ {{12}} \ log {n})$ где $c {\ displaystyle c}$ $c$ - константа расширения набора данных.

Insert

Хотя покровные деревья обеспечивают более быстрый поиск, чем наивный подход, это преимущество необходимо сопоставить с дополнительными затратами на поддержание структуры данных. При наивном подходе добавление новой точки в набор данных тривиально, потому что порядок не нужно сохранять, но в дереве обложки это может занять $O (c 6 log ⁡ n) {\ displaystyle O (c ^ {6 } \ log {n})}$ $O (c ^ {6} \ log {n})$ время. Однако это верхняя граница, и были реализованы некоторые методы, которые, кажется, улучшают производительность на практике.

Пробел

Покровное дерево использует неявное представление для отслеживания повторяющихся точек. Таким образом, для этого требуется всего O (n) пространства.

См. Также

Ссылки

Примечания

Библиография

Алина Бейгельзимер, Шам Какаде и Джон Лэнгфорд. Прикрывайте деревья для ближайшего соседа. В Proc. Международная конференция по машинному обучению (ICML), 2006.
Титульное дерево JL. Страница Джона Лэнгфорда содержит ссылки на статьи и код.
Реализация дерева обложек C ++ на GitHub.
Реализация дерева обложек на Java.