Conclusiones

Como fruto de este trabajo, se presentó un algoritmo de indexamiento llamado FQTrie, el cual es una combinación de los algoritmos FQA y FQT, obteniendo como resultado una estructura mitad árbol y mitad arreglo, con esta estructura se mejora la memoria necesaria en el FQT y se mejora el tiempo la búsqueda del FQA, conserva las ventajas de los algoritmos basados en pivotes y el tiempo empleado en el indexamiento es lineal en $n$ (tamaño de la base de datos). Cabe mencionar que este algoritmo es necesario en el desarrollo del algoritmo que soluciona el problema de los $K$ vecinos más cercanos. La decisión de usar este algoritmo para solucionar el problema principal radica en sus ventajas: su tiempo de indexamiento, la eficiencia de la búsqueda que se puede realizar en él, y la cantidad de memoria utilizada.

Antes de abordar las ventajas del algoritmo presentado, se mencionará la importancia de la dimensión intrínseca en un algoritmo de indexamiento, para entender este problema se propone utilizar un histograma de distancias para caracterizar la dificultad de la búsqueda en un espacio métrico arbitrario, en la sección , se dio una explicación intuitiva del porque el problema es más difícil a medida que la dimensión crece. Cuando se habla de la dimensión se refiere a la dimensión representativa de los datos y cuando se habla de la dimensión intrínseca esta última trata de capturar la dimensión real del espacio en la que están los datos.En [CN99] se propone una medida para cuantificar la dimensión intrínseca de un algoritmo basado en pivotes.

Según la definición dada en [CN99], la dimensión intrínseca de un espacio métrico esta definido como $\rho = \frac{\mu^2}{2\sigma^2}$, donde y son la media y la varianza del histograma de distancias correspondiente.

En los algoritmos basados en pivotes, cada vez que se realiza una consulta, se hacen un número de cálculos de distancia y es posible saber cuantos cálculos de distancia se realizarán, en [CN99] se demuestra que el límite inferior para conocer el costo promedio de búsqueda usando un algoritmo basado en pivotes es:

donde es el número de pivotes utilizado, es la varianza de los elementos de la base de datos y $r$ es radio promedio de las búsquedas aplicadas a un algoritmo basado en pivotes, una descripción más detallada, se puede observar en el apéndice .

En este trabajo se presentó un algoritmo que encuentra los $K$ vecinos más cercanos de todos los elementos en una base de datos, las ventajas de este algoritmo son las enlistadas a continuación.

• Parámetros de ajuste.- Entre las cosas que deben tomarse en cuenta en una aplicación se encuentran la memoria y el tiempo de ejecución. En algunas ocasiones el usuario está dispuesto a gastar memoria, por tiempo de ejecución, y viceversa. Un parámetro de ajuste, es precisamente la libertad que se le concede al usuario de decidir entre tiempo de ejecución y memoria. El algoritmo de todos los $K$ vecinos más cercanos presentado, tiene algunos parámetros de ajuste, los cuales modifican el desempeño del algoritmo, a continuación se presentan dichos parámetros.
  • Número de pivotes.- Permite seleccionar la cantidad de pivotes utilizados, tanto en la construcción del FQTrie, como en la búsqueda de los $K$ vecinos más cercanos. Las conclusiones acerca de este parámetro son: a medida que incrementa el número de pivotes aumenta el tiempo de construcción del FQTrie linealmente y disminuye el tiempo de respuesta en la búsqueda de todos los $K$ vecinos más cercanos.

    Siendo un parámetro tan importante el número de pivotes, cabe mencionar que la mejor manera, para encontrar los puntos que serán pivotes es de manera aleatoria, debido a que con los puntos seleccionados de esta manera (observe en las gráficas mostradas en el capítulo anterior) se obtiene un buen rendimiento del algoritmo y no es necesario hacer ningún cálculo de distancia extra, si se implementara alguna heurística para conocer los mejores puntos como pivotes, el costo del algoritmo sería, el costo de la construcción del índice más el costo de la selección de pivotes más el costo del algoritmo para encontrar los $K$ vecinos y además el tiempo que tarda cada uno de estos procesos, por lo tanto se recomienda que esta selección sea aleatoria.

    En [CN99] se sugiere el número óptimo de pivotes es:

    
    

    
    
    donde $n$ es el tamaño de la base de datos, y es , donde es la varianza de la base de datos y es el radio promedio de consulta, la demostración de puede verse en el apéndice .

    Un valor muy importante es el número de vecinos para cada punto, este valor varía de acuerdo tipo de problema a resolver, es decir, el número de los vecinos más cercanos depende directamente del problema que se pretende resolver. Como sugerencia, el número de vecinos más cercanos debe ser menor que el número de pivotes, debido a las características del algoritmo.

  • Número de Bits.- El manejo de memoria siempre es importante en cualquier algoritmo, con este parámetro es posible seleccionar la cantidad de memoria empleada en el indexamiento, es claro, que a medida que aumenta el número de bits, mayor es la memoria necesaria para realizar el indexamiento, sin embargo, si aumenta el número de bits, disminuye el número de cálculos de distancia al momento de la consulta. Como sugerencia, se recomienda que sean 8 bits.

• En algunas aplicaciones solo se requiere una buena aproximación de los vecinos más cercanos, para esto, es importante mencionar, que este algoritmo, puede detenerse en el momento que se desee, y cada elemento tendría una aproximación buena de sus vecinos más cercanos. Si se requiere saber con exactitud los vecinos más cercanos de todos los puntos, entonces si es necesario esperar a que el algoritmo termine. Debido a las características del algoritmo al momento de consultar un elemento para conocer sus vecinos más cercanos, se modifican los vecinos más cercanos de otros puntos, esta es la razón por la que es posible detener el algoritmo en cualquier momento.

Una vez que se obtuvo el algoritmo, se hicieron algunas pruebas, acerca de como empezar la búsqueda de los vecinos mas cercanos, esto con la finalidad de probar, si importa el orden de los puntos en que se empieza la búsqueda de los vecinos más cercanos, se observó que no existen diferencias significativas en el desempeño del algoritmo; las dos heurísticas planteadas para realizar esta pruebas fueron:

• Radios máximos primeros.- Empezar la búsqueda de los vecinos mas cercanos primero con los elementos cuyo radio inicial fuera el mayor de todos, esto con el fin de que muchos más puntos fueran beneficiados con la búsqueda de un elemento. La desventaja de esta heurística, es que se necesita una cola de prioridad para mantener ordenados los puntos de acuerdo al radio máximo, con esto, es obvio que se necesita más memoria, y más tiempo de procesamiento. Los resultados de esta prueba, no incrementan significativamente el desempeño del algoritmo.

• Radios mínimos primeros.- Se planteó empezar la búsqueda con los elementos que tuvieran el radio inicial mínimo, pretendiendo con esto que los puntos con un radio más grande, se redujera y al momento de consultar estos otros puntos su radio ya no fuera tan grande. Si un radio inicial esta muy próximo al correspondiente radio que encierra los $K$ vecinos, se realizaran menos cálculos de distancia. La desventaja de esta heurística es que se necesita una cola de prioridad para mantener los elementos ordenados por su distancia menor, lo que implica, incrementar la memoria usada y un incremento al tiempo de procesamiento. Esta otra heurística, tampoco muestra un incremento considerable en el desempeño del algoritmo.

Es importante para todo algoritmo, que se realicen comparaciones con respecto a los algoritmos existentes, en misma circunstancias, así que, las pruebas finales aplicadas a este algoritmo, fueron tratar de compararlo con respecto a los algoritmos existentes, por desgracia, no fue posible conseguir el algoritmo realizado por Vaidya, así que esta comparación no se llevo a cabo, el otro algoritmo desarrollado por Clarkson, además de que tampoco fue posible conseguirlo, no tiene parámetros de ajuste, por lo tanto, el algoritmo presentado en este trabajo podría superarlo modificando sus parámetros de ajuste.