Introducción al problema

El concepto de ``búsqueda de similaridad'' ó ``búsqueda de proximidad'', consiste en buscar a los elementos de la base de datos que sean similares o cercanos a un elemento de consulta dado. La similaridad es modelada con una función de distancia [NBY00] que satisface la desigualdad del triángulo, y el conjunto de objetos es llamado espacio métrico.

En muchas aplicaciones, el problema en espacios métricos generales es trasladado a un espacio vectorial (por ejemplo, los objetos están representados como puntos en $m$-dimensiones con alguna interpretación geométrica de similaridad). Desafortunadamente los algoritmos existentes son muy sensibles a la dimensión del espacio vectorial, es decir, tienen una dependencia exponencial en la dimensión del espacio (esto es llamado ``la maldición de la dimensión''). En términos prácticos, es considerado que el problema es intratable en más de 20 dimensiones. Por esta razón, varios autores han propuesto el uso de técnicas de indexamiento basadas en $distancias$, las cuales usan solo la distancia entre puntos y evitan cualquier referencia a coordenadas, en un intento por evitar la maldición de la dimensión.

El problema de los $K$ vecinos más cercanos aparece en diversas áreas en las cuales las técnicas computacionales son aplicadas, por ejemplo para encontrar agrupamientos en nubes de datos (clustering) [Chá97], precondicionamiento de algoritmos de indexamiento, matrices de confusión para probar el algoritmo $K$NN (K-Nearest Neighbors), algoritmos de Ranking, pruebas de hipótesis y estimación de densidades.

En este trabajo se presenta una solución al problema de todos los $K$ vecinos más cercanos. Este problema consiste en que dada una base de datos de n puntos o elementos en un espacio métrico, se necesita encontrar para cada elemento sus $K$ vecinos más cercanos (la figura , muestra el resultado de encontrar todos los $K$ vecinos de una base de datos). La complejidad del problema es medida en cálculos de distancia, de antemano se sabe que usando la fuerza bruta el problema es solucionado con $n^2$ cálculos de distancia (debido a que cada elemento calcularía la distancia hacia toda la base de datos).

La solución planteada para encontrar los $K$ vecinos mas cercanos consiste en hacer uso de un algoritmo de indexamiento para reducir los cálculos de distancia; el algoritmo de indexamiento usado es el FQTrie (Fixed Query Trie), el cual una combinación de lo mejor de los algoritmos FQT (Fixed Query Tree) y FQA (Fixed Query Array).

Figura: Ejemplo de una base de datos, donde cada elemento ya conoce a sus $K$ vecinos más cercanos