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 eligiendo una posición en el espacio (el "punto de vista") y dividiendo 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 similitud . Utiliza más de un punto para dividir cada nivel. [2] [3]
Historia
Peter Yianilos afirmó que el árbol del mirador fue descubierto de forma independiente 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.
Entendiendo un árbol de mirador
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]
Buscando a través de un árbol mirador
Se puede usar un árbol de puntos de vista 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 vy una distancia de umbral t . El punto de interés x estará a cierta distancia del mirador v . Si esa distancia d es menor que t , utilice el algoritmo de forma recursiva para buscar en el subárbol del nodo que contiene los puntos más cercanos al punto de observación que el umbral t ; de lo contrario, recurre al subárbol del nodo que contiene los puntos que están más lejos que el punto de observación que el umbral t . Si el uso recursivo del algoritmo encuentra un punto vecino n con una distancia ax menor que | t - d | entonces no puede ayudar buscar el otro subárbol de este nodo; se devuelve el nodo n descubierto . De lo contrario, el otro subárbol también debe buscarse de forma recursiva.
Un enfoque similar funciona para encontrar los k vecinos más cercanos de un punto x . En la recursividad, 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 menor que | t - d | .
Ventajas de un árbol mirador
- En lugar de inferir puntos multidimensionales para el dominio antes de que se construya el índice, construimos el índice directamente en función de la distancia. [6] Al hacer esto, se evitan los pasos previos al procesamiento.
- Actualizar un árbol de puntos de vista es relativamente fácil en comparación con el enfoque de mapa rápido. Para mapas rápidos, después de insertar o eliminar datos, llegará un momento en que el mapa rápido tendrá que volver a escanearse. Eso lleva demasiado tiempo y no está claro cuándo comenzará la nueva exploración.
- Los métodos basados en la distancia son flexibles. Es "capaz de indexar objetos que se representan como vectores de características de un número fijo de dimensiones". [6]
Complejidad
El costo de tiempo para construir un árbol Vantage-Point 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 de árbol. [3]
El costo de tiempo para buscar en un árbol de Vantage-Point para encontrar un solo vecino más cercano es O (log n ) . Hay log n niveles, cada uno de los cuales incluye 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 vista, que puede ser el atributo más importante, puede variar mucho según las especificaciones del algoritmo utilizado y los parámetros. El artículo de Brin [3] da el resultado de experimentos con varios algoritmos de puntos de vista con varios parámetros para investigar el costo, medido en número de cálculos de distancia.
El costo de espacio para un árbol Vantage-Point es aproximadamente n . Cada elemento se almacena y cada elemento de árbol en cada nodo no hoja requiere un puntero a sus nodos descendientes. (Consulte Brin para obtener detalles sobre una opción de implementación. El parámetro para el número de elementos en cada nodo juega un factor).
Tenga en cuenta que algunas herramientas de espacio métrico requieren una matriz de valores de distancia por pares, con un costo de O ( n 2 ) , pero eso no es necesario con los árboles de puntos de vista.
Referencias
- ↑ a b Yianilos (1993). Estructuras de datos y algoritmos para la búsqueda de vecinos más cercanos en espacios métricos generales (PDF) . Cuarto simposio anual ACM-SIAM sobre algoritmos discretos. Sociedad de Matemáticas Industriales y Aplicadas Filadelfia, PA, EE. UU. págs. 311–321. pny93 . Consultado el 22 de agosto de 2008 .
- ^ Bozkaya, Tolga; Ozsoyoglu, Meral (septiembre de 1999). "Indexación de grandes espacios métricos para consultas de búsqueda de similitud". ACM Trans. Syst base de datos . 24 (3): 361–404. doi : 10.1145 / 328939.328959 . ISSN 0362-5915 .
- ^ a b c Brin, Sergey (septiembre de 1995). "Búsqueda de vecinos cercanos en grandes espacios métricos" . VLDB '95 Actas de la 21ª Conferencia Internacional sobre Bases de Datos Muy Grandes . Zúrich, Suiza: Morgan Kaufmann Publishers Inc .: 574–584.
- ^ Uhlmann, Jeffrey (1991). "Satisfacer consultas generales de proximidad / similitud con árboles métricos". Cartas de procesamiento de información . 40 (4): 175-179. doi : 10.1016 / 0020-0190 (91) 90074-r .
- ^ Nielsen, Frank (2009). "Árboles de punto de vista de Bregman para consultas vecinas más cercanas eficientes". Actas de Multimedia y Exp (ICME) . IEEE. págs. 878–881.
- ^ a b c d Fu, Ada Wai-chee; Polly Mei-shuen Chan; Yin-Ling Cheung; Yiu Sang Moon (2000). "Indexación dinámica de vp-tree para n -búsqueda de vecinos más cercanos dadas distancias por pares" . The VLDB Journal: la revista internacional sobre bases de datos muy grandes . Springer-Verlag Nueva York, Inc. Secaucus, Nueva Jersey, EE. UU. págs. 154-173. vp . Consultado el 2 de octubre de 2012 .