Desempeño del algoritmo

Todos lo algoritmos de búsqueda tratan de capturar las propiedades geométricas del espacio, las cuales son complejas y costosas de evaluar y algunas son difíciles de extender a espacios métricos [CNBYM99]. Muchos autores han propuesto usar los histogramas de distancias para caracterizar la dificultad de la búsqueda en un espacio métrico arbitrario. Si se considera el histograma de distancias entre puntos en un espacio métrico $X$, usando un diccionario $U$, se puede dar una explicación intuitiva del porque el problema de búsqueda es más difícil cuando el histograma esta concentrado (véase la figura ). Si consideramos una consulta aleatoria $q$ y un esquema de indexamiento basado en pivotes, entonces las posibles distancias entre $q$ y un pivote son distribuidas de acuerdo al histograma de esta figura. La regla de eliminación dice que podemos descartar cualquier punto $u$ tal que , . El área gris en la figura muestra los puntos que no pueden ser descartados. Conforme el histograma esta más y más concentrado al punto $q$, menos y menos puntos pueden ser descartados usando la información dada por $d(p,q)$.

Figura 6.14: Un histograma de distancias con dimensión baja (izquierda) y dimensión alta (derecha), mostramos que en dimensión alta virtualmente todos los elementos son candidatos para una evaluación exhaustiva

Para observar el desempeño del algoritmo se probó este algoritmo en un espacio dimensional completo, variando el número de pivotes, variando el número de vecinos más cercanos ($K$), y por supuesto variando también el número de elementos en el conjunto de puntos, en las siguientes secciones se presentan los resultados experimentales.

En las gráficas mostradas se nota que hay un cambio de tener un algoritmo subcuadrático a uno sublineal si medimos solo los cálculos de distancia externas (no contando el costo de construcción del índice). Esto es posible por que en algunos casos (muy común para los últimos elementos de la base de datos) podemos resolver las consultas de proximidad casi sin ningún cálculo de distancia, cuando el máximo radio en la cola de prioridad coincide con la lista actual de vecinos más cercanos ($K$).

En las siguientes secciones se mostrarán los resultados experimentales de este algoritmo, es importante enfatizar que en cada una de las gráficas mostradas a continuación es mucho mejor que usar la fuerza bruta y las gráficas presentadas son comparadas con esta heurística.