Árbol de cubierta

Tipo de estructura de datos

El árbol de cobertura es un tipo de estructura de datos en informática que está específicamente diseñada para facilitar la aceleración de una búsqueda del vecino más cercano . Es un refinamiento de la estructura de datos de Navigating Net y está relacionada con una variedad de otras estructuras de datos desarrolladas para indexar datos intrínsecamente de baja dimensión. ^[1]

El árbol puede considerarse como una jerarquía de niveles, en la que el nivel superior contiene el punto raíz y el nivel inferior contiene todos los puntos del espacio métrico. Cada nivel C está asociado a un valor entero i que disminuye en uno a medida que se desciende por el árbol. Cada nivel C del árbol de cobertura tiene tres propiedades importantes:

• Anidamiento: ${\displaystyle C_{i}\subseteq C_{i-1}}$
• Cobertura: Para cada punto , existe un punto tal que la distancia desde a es menor o igual a y exactamente uno de ellos es padre de . ${\displaystyle p\in C_{i-1}}$ ${\displaystyle q\in C_{i}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle 2^{i}}$ ${\displaystyle q}$ ${\displaystyle p}$
• Separación: Para todos los puntos , la distancia de a es mayor que . ${\displaystyle p,q\in C_{i}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle 2^{i}}$

Complejidad

Encontrar

Al igual que otros árboles métricos, el árbol de cobertura permite búsquedas de vecinos más cercanos en donde es una constante asociada con la dimensionalidad del conjunto de datos y n es la cardinalidad. Para comparar, una búsqueda lineal básica requiere , que es una dependencia mucho peor de . Sin embargo, en espacios métricos de alta dimensión , la constante no es trivial, lo que significa que no se puede ignorar en el análisis de complejidad. A diferencia de otros árboles métricos, el árbol de cobertura tiene un límite teórico en su constante que se basa en la constante de expansión del conjunto de datos o la constante de duplicación (en el caso de la recuperación de NN aproximada). El límite en el tiempo de búsqueda es donde es la constante de expansión del conjunto de datos. ${\displaystyle O(\eta *\log {n})}$ ${\displaystyle \eta }$ ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle \eta }$ ${\displaystyle O(c^{12}\log {n})}$ ${\displaystyle c}$

Insertar

Aunque los árboles de cobertura proporcionan búsquedas más rápidas que el enfoque ingenuo, esta ventaja debe sopesarse con el costo adicional de mantener la estructura de datos. En un enfoque ingenuo, agregar un nuevo punto al conjunto de datos es trivial porque no es necesario preservar el orden, pero en un árbol de cobertura puede llevar tiempo. Sin embargo, este es un límite superior y se han implementado algunas técnicas que parecen mejorar el rendimiento en la práctica. ^[2] ${\displaystyle O(c^{6}\log {n})}$

Espacio

El árbol de cobertura utiliza una representación implícita para realizar un seguimiento de los puntos repetidos, por lo que solo requiere espacio O(n).

Véase también

• Búsqueda de vecino más cercano
• árbol kd
• Árbol M

Referencias

Notas

1. Kenneth Clarkson. Búsqueda de vecinos más próximos y dimensiones del espacio métrico. En G. Shakhnarovich, T. Darrell y P. Indyk , editores, Métodos de vecinos más próximos para el aprendizaje y la visión: teoría y práctica, páginas 15--59. MIT Press, 2006.
2. "Árbol de portada".

Bibliografía

• Alina Beygelzimer, Sham Kakade y John Langford. Árboles de cobertura para el vecino más cercano. En Proc. Conferencia internacional sobre aprendizaje automático (ICML), 2006.
• Página de portada de JL. La página de John Langford contiene enlaces a artículos y códigos.
• Una implementación de C++ Cover Tree en GitHub.
• Una implementación de árbol de cobertura en Java.