Дерево покрытий

Дерево покрытий (англ. Cover tree) — древовидная структура данных (дерево), специально разработанная для ускорения поиска ближайшего соседа.

Дерево можно рассматривать как иерархию, верхний уровень которой содержит корневую точку, а нижний - все точки в метрическом пространстве. Каждому уровню $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}$.

Вычислительная сложность

См. также

• Задача поиска ближайшего соседа
• K-мерное дерево

Ссылки

• Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006.
• John Langford's Cover Tree page.
• Реализация Cover tree на C++.