Покровное дерево

Дерево покрытия представляет собой тип структуры данных в компьютерной науке , которая специально разработан для облегчения быстрого плана ближайшего поиска соседа . Это усовершенствованная структура данных Navigating Net, связанная с множеством других структур данных, разработанных для индексации низкоразмерных данных. ^[1]

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

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

Сложность [ править ]

Найдите [ редактировать ]

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

Вставить [ изменить ]

Хотя деревья покрытия обеспечивают более быстрый поиск, чем наивный подход, это преимущество необходимо сопоставить с дополнительными затратами на поддержку структуры данных. При наивном подходе добавление новой точки в набор данных тривиально, потому что порядок не нужно сохранять, но в дереве обложки это может занять время. Однако это верхний предел, и были реализованы некоторые методы, которые, кажется, улучшают производительность на практике. ^[2]${\ Displaystyle О (с ^ {6} \ журнал {п})}$

Пробел [ править ]

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

См. Также [ править ]

• Поиск ближайшего соседа
• kd-дерево

Ссылки [ править ]

Примечания

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

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