Árbol de vicepresidentes

VP-tree ( Árbol de puntos de vista en inglés  ) es una especie de árbol BSP .

Se puede construir un árbol VP para objetos de un espacio métrico , es decir, para cualquier conjunto en el que se define la distancia entre dos elementos cualesquiera de este conjunto.

Principio de construcción del árbol

Uno de los puntos ("punto de referencia") se toma del conjunto inicial y se selecciona el "radio" R para este punto. Los puntos restantes se dividen en dos subconjuntos: con una distancia menor que R al punto de referencia y una distancia mayor que R. En cada uno de los subconjuntos resultantes, se selecciona el siguiente punto de referencia y un nuevo radio, y así sucesivamente, hasta el número de elementos en cada uno de los subconjuntos restantes se vuelve menos de un cierto valor de umbral.

Los puntos de referencia y los "radios" de las esferas divisorias se eligen de modo que el árbol esté lo más equilibrado posible.

Beneficios

A diferencia de un árbol KD , que solo se aplica a los puntos desde , un árbol VP se puede usar para encontrar los objetos más cercanos desde cualquier espacio métrico. Por ejemplo, la distancia de Hamming se puede usar como métrica  ; luego, el árbol VP se puede usar para buscar palabras similares en un diccionario o para buscar imágenes similares.

Véase también

• árbol KD
• R-árbol
• Partición binaria del espacio

Literatura

• Ming Hua, Jian Pei. Clasificación de consultas sobre datos inciertos . - Springer Science & Business Media, 2011. - P.  60 . — ISBN 978-1-4419-9380-9 .
• Vittorio Castelli, Lawrence D. Bergman. Bases de datos de imágenes: búsqueda y recuperación de imágenes digitales. - John Wiley & Sons, 2004. - Pág. 422. - ISBN 978-0-471-46407-5 .

Enlaces

• Algoritmo paralelo para encontrar el punto más cercano en un radio