Un árbol de punto de vista (o árbol de VP ) es un árbol de métricas que segrega datos en un espacio de métricas al elegir una posición en el espacio (el "punto de vista") y dividir los puntos de datos en dos partes: los puntos que están más cerca de el mirador que un umbral, y los puntos que no lo son. Al aplicar de forma recursiva este procedimiento para dividir los datos en conjuntos cada vez más pequeños, se crea una estructura de datos de árbol donde es probable que los vecinos del árbol sean vecinos del espacio. [1]
Una generalización se llama á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 similitudes . Utiliza más de un punto para dividir cada nivel. [2] [3]
Peter Yianilos afirmó que el árbol del mirador 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 mirador se han generalizado a espacios no métricos utilizando las 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 particiones 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 punto de vista almacena datos se puede representar mediante un círculo. [6] Primero, comprenda que cada nodo de este árbol contiene un punto de entrada y un radio. Todos los hijos de la izquierda de un nodo dado son los puntos dentro del círculo y todos los hijos de la derecha de un nodo dado están fuera del círculo. El árbol en sí no necesita conocer ninguna otra información sobre lo que se está almacenando. Todo lo que necesita es la función de distancia que satisfaga las propiedades del espacio métrico . [6]