Un árbol de puntos de vista (o árbol VP ) es un árbol métrico que segrega datos en un espacio métrico eligiendo una posición en el espacio (el "punto de vista") y dividiendo los puntos de datos en dos partes: aquellos puntos que están más cerca del punto de vista que un umbral y aquellos puntos que no lo están. Al aplicar recursivamente este procedimiento para particionar los datos en conjuntos cada vez más pequeños, se crea una estructura de datos en forma de árbol donde es probable que los vecinos en el árbol sean vecinos en el espacio. [1]
Una generalización se denomina árbol de múltiples puntos de vista (o árbol MVP ): una estructura de datos para indexar objetos de grandes espacios métricos para consultas de búsqueda de similitud . Utiliza más de un punto para dividir cada nivel. [2] [3]
Peter Yianilos afirmó que el árbol de puntos de vista fue descubierto independientemente por él (Peter Yianilos) y por Jeffrey Uhlmann . [1] Sin embargo, Uhlmann publicó este método antes que Yianilos en 1991. [4] Uhlmann llamó a la estructura de datos un árbol métrico , el nombre VP-tree fue propuesto por Yianilos. Los árboles de puntos de vista han sido generalizados a espacios no métricos utilizando divergencias de Bregman por Nielsen et al. [5]
Este proceso de partición iterativo es similar al de un árbol k -d , pero utiliza particiones circulares (o esféricas, hiperesféricas, etc.) en lugar de rectilíneas. En el espacio euclidiano bidimensional, esto se puede visualizar como una serie de círculos que segregan los datos.
El árbol de puntos de vista es particularmente útil para dividir datos en un espacio métrico no estándar en un árbol métrico.
La forma en que un árbol de puntos de vista almacena datos se puede representar mediante un círculo. [6] En primer lugar, comprenda que cada nodo de este árbol contiene un punto de entrada y un radio. Todos los hijos izquierdos de un nodo dado son los puntos dentro del círculo y todos los hijos derechos de un nodo dado están fuera del círculo. El árbol en sí no necesita saber ninguna otra información sobre lo que se está almacenando. Todo lo que necesita es la función de distancia que satisface las propiedades del espacio métrico . [6]
Un árbol de puntos de vista se puede utilizar para encontrar el vecino más cercano de un punto x . El algoritmo de búsqueda es recursivo. En cualquier paso dado estamos trabajando con un nodo del árbol que tiene un punto de vista v y una distancia umbral t . El punto de interés x estará a cierta distancia del punto de vista v . Si esa distancia d es menor que t entonces use el algoritmo recursivamente para buscar el subárbol del nodo que contiene los puntos más cercanos al punto de vista que el umbral t ; de lo contrario recurra al subárbol del nodo que contiene los puntos que están más lejos del punto de vista que el umbral t . Si el uso recursivo del algoritmo encuentra un punto vecino n con una distancia a x que es menor que | t − d | entonces no puede ayudar a buscar el otro subárbol de este nodo; se devuelve el nodo descubierto n . De lo contrario, el otro subárbol también necesita ser buscado recursivamente.
Un enfoque similar funciona para encontrar los k vecinos más cercanos de un punto x . En la recursión, se busca en el otro subárbol k − k′ vecinos más cercanos del punto x siempre que solo k′ (< k ) de los vecinos más cercanos encontrados hasta ahora tengan una distancia que sea menor que | t − d | .
El costo de tiempo para construir un árbol de puntos de observación es aproximadamente O ( n log n ) . Para cada elemento, el árbol desciende por log n niveles para encontrar su ubicación. Sin embargo, existe un factor constante k donde k es el número de puntos de observación por nodo del árbol. [3]
El costo de tiempo para buscar un vecino más cercano en un árbol de puntos estratégicos es O (log n ) . Hay niveles de log n , cada uno de los cuales implica k cálculos de distancia, donde k es el número de puntos estratégicos (elementos) en esa posición en el árbol.
El costo de tiempo para buscar un rango en un árbol de puntos de observación, que puede ser el atributo más importante, puede variar en gran medida según las particularidades del algoritmo utilizado y los parámetros. El artículo de Brin [3] presenta el resultado de experimentos con varios algoritmos de puntos de observación con varios parámetros para investigar el costo, medido en número de cálculos de distancia.
El costo de espacio para un árbol de puntos de vista es de aproximadamente n . Cada elemento se almacena y cada elemento del árbol en cada nodo que no sea una hoja requiere un puntero a sus nodos descendientes. (Consulte Brin para obtener detalles sobre una opción de implementación. El parámetro para la cantidad de elementos en cada nodo es un factor importante).
Con n puntos hay O ( n 2 ) distancias por pares entre puntos. Sin embargo, la creación de un árbol de puntos de observación requiere que solo se calculen explícitamente O ( n log n ) distancias, y una búsqueda requiere solo cálculos de distancia O (log n ) . Por ejemplo, si x e y son puntos y se sabe que la distancia d ( x , y ) es pequeña, entonces cualquier punto z que esté lejos de x también estará necesariamente casi tan lejos de y porque la desigualdad triangular del espacio métrico da d ( y , z ) ≥ d ( x , z ) − d ( x , y ) .