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

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

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

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

Сложность

Найти

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

Вставить

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

Космос

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

См. также

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

Ссылки

Примечания

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

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