Estado del arte de la construcción del índice

Probablemente la primera solución general para buscar en espacios métricos fue presentada en [BK73], donde se propone un árbol llamado ``Burkhard-Keller Tree'' o BKT, el cual es recomendable para cuando se usan funciones de distancia discretas. Un desarrollo más sobresaliente sobre los BKTs es FQT ``Fixed Query Tree'' [BYCMW94]. Este árbol es básicamente un BKT donde todas las ramas del mismo nivel, tienen el mismo pivote (por supuesto que no necesariamente pertenecen al conjunto guardado en el subárbol). Los elementos restantes están guardados en las hojas. La ventaja de tal construcción es que las comparaciones entre la consulta y los nodos (pivotes) solo se necesitan una vez y estas ayudan en el recorrido del árbol. Si visitamos muchos nodos del mismo nivel, no se necesita calcular más que una comparación porque todos los pivotes en este nivel son el mismo. En [BYCMW94] los autores proponen una variante llamada FQHT ``Fixed-Height FQT'', donde todas las hojas están a la misma profundidad $h$, independientemente del tamaño del bucket. Esto hace que algunas hojas estén más profundas de lo necesario, lo cual tiene sentido porque podemos haber desarrollado las comparaciones entre la consulta y el pivote de un nivel intermedio, y por lo tanto eliminamos libremente una hoja, sin haber calculado su distancia. En [CMN99] se presenta el FQA arreglo de consultas fijas (Fixed Query Array), aunque no propiamente un árbol, no es más que una representación compacta de los FQHT. Imagine que un FQHT de altura fija $h$ es construida en un conjunto. Si recorremos las hojas del árbol de izquierda a derecha y ponemos los elementos en un arreglo, el resultado es el FQA. Los elementos del arreglo (renglones) son concatenados en un número que después es ordenado lexicográficamente, cada subárbol del FQHT corresponde a un intervalo en el FQA, y cada movimiento en el FQHT es simulado con dos búsquedas binarias en el FQA. Usando la misma memoria, la simulación del FQA es capaz de usar muchos más pivotes que el original FQHT, con lo cual prueba su eficiencia.

La primera técnica diseñada para funciones de distancia continuas fue llamada ``árboles métricos'' en [Uhl91]. Un trabajo más completo con la misma idea [Yia93] son VPTs ``Vantage Point Tree'', en el cual se construye un árbol binario recursivamente, tomando algún elemento como la raíz y tomando la mediana del conjunto de todas las distancia, $M=mediana\{d(p,u) \mid u \in U\}$. Los elementos $u$ tales que $d(p,u) < M$ son insertados en el subárbol izquierdo, mientras que aquellos tales que son insertados en el subárbol derecho. Los VPT pueden ser extendidos a árboles $m-arios$ usando los $m-1$ percentiles uniformes en lugar de solo la mediana, esto es sugerido en [Bri95,BO97]. En [BO97] se presentó el ``Multi-Vantage Point Tree MVPT el cual proponen el uso de muchos elementos en un nodo. Otra generalización de los VPT está dada por el VPF (Vantage Point Forest) [Yia93]. Este algoritmo está diseñado para búsqueda del vecino más cercano con un radio limitado (una consulta de tipo (b) con radio máximo $r^{\ast}$). El método consiste en excluir, a cada nivel los elementos a distancia intermedia a sus pivotes. Si $r_o$ y $r_n$ corresponden a los puntos más cercanos y más lejanos al pivote , los elementos $u \in U$ tales que $d(p,r_o) + \delta \leq d(p,u) \leq d(p,r_n) - \delta$ son excluidos del árbol. Un segundo árbol es construido con la parte excluida del primer árbol, y así se continúa para obtener un bosque.

Otro algoritmo presentado en [Uhl91] es GHT árbol de generalización hiperplana (Generalize Hiperplane-Tree) el cual es un árbol binario construido recursivamente como sigue. Para cada nodo, dos puntos $p_1$ y $p_2$ son seleccionados. Los puntos más cercanos a $p_1$ que a $p_2$ van dentro del subárbol izquierdo y aquellos más cercanos a $p_2$ van en el subárbol derecho. El GHT es extendido en [Bri95] a un árbol $m-ario$, llamado GNAT ''Geometric Near-Neighbor Access Tree''. Se selecciona, para el primer nivel pivotes $p_1, ..., p_P$, y se define $U_i = \{ u \in U, d(p_i,u) < d(p_j, u), \forall j \neq i \}$. Esto es, $U_i$ son los puntos más cercanos a $p_i$ que a algún otro $p_j$. Finalmente dan algún criterio para seleccionar los $p_i$ elementos los suficientemente lejanos.

Un algoritmo el cual encierra muchas de las ideas presentadas pero se desarrolla sorpresivamente mucho mejor por un orden de magnitud es AESA [Vid86] (``Aproximating Eliminating Search Algorithm''). La estructura no es un árbol, pero la idea es muy similar, se selecciona un punto $p \in U$ aleatorio y miden $r_p = d(p,q)$, eliminando todos los elementos $u \in U$ los cuales no satisfacen $r_p - r \leq d(u,p) \leq r_p + r$. Esto se repite hasta que hay pocos elementos resultantes en el conjunto y son comparados contra $q$ directamente.