árbol de cubierta

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

Se puede pensar en el árbol como una jerarquía de niveles con el nivel superior que contiene el punto raíz y el nivel inferior que contiene cada punto en el espacio métrico. Cada nivel C está asociado con un valor entero i que decrece en uno a medida que desciende el árbol. Cada nivel C en el árbol de cobertura tiene tres propiedades importantes:

Al igual que otros árboles de métricas, el árbol de cobertura permite búsquedas de vecinos más cercanos en las que 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 de métricas, el árbol de cobertura tiene un límite teórico en su constante que se basa en la constante de expansión o la constante de duplicación del conjunto de datos (en el caso de la recuperación aproximada de NN). El límite en el tiempo de búsqueda es donde está la constante de expansión del conjunto de datos. $O(\eta *\log{n})$ ${\ estilo de visualización \ eta}$ ${\ estilo de visualización O (n)}$ $n$ $\eta$ $O(c^{12}\log {n})$ $c$

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] $O(c^{6}\log {n})$

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