| |
|
| [Who doesn't understand a glance, won't understand a long explanation either.] | |
| - Arab proverb |
Similarity Searching consists in finding the elements from a set which are similar to a given query object under some criterion. If the similarity is expressed by means of a metric, the problem is called Metric Space Searching. In this thesis we present new methodologies to solve this problem using graphs G(V,E) to represent the metric database. In G, the set V corresponds to the objects from the metric space and E to a small subset of edges from V x V, whose weights are computed according to the metric of the space under consideration.
In particular, we study k-nearest neighbor graphs (kNNGs). The kNNG is a weighted graph connecting each node from V ---or equivalently, each object from the metric space--- to its k nearest neighbors. kNNGs have many other applications beyond metric space searching.
We develop algorithms both to construct kNNGs in general metric spaces, and to use them for proximity searching. These results allow us to use a graph to index a metric space, requiring a moderate amount of memory, with better search performance than that of classical pivot-based algorithms.
Finally, we show that the graph-based approach offers a great potential for improvements, ranging from fully dynamic graph-based indices to optimizations tuned for metric space searching.
The high amount of computational resources required to build and traverse these graphs also motivated us to research on fundamental algorithmic problems, such as incremental sorting and priority queues. We propose new algorithms for these problems which, in practice, improve upon the state-of-the-art solutions in several cases, and are useful in many other scenarios. In particular, they allow one to obtain a simple, competitive with the state of the art minimum spanning tree construction algorithm for random graphs.
These basic algorithms not only open new research lines, for instance minimum spanning tree construction algorithms for arbitrary graphs, but also they turn out to be appealing to be applied directly in production environments.
La Búsqueda por Similaridad consiste en encontrar los elementos de un conjunto que son semejantes a un objeto de consulta dado de acuerdo a algún criterio. Cuando la semejanza se expresa mediante una métrica, el problema es llamado Búsqueda en Espacios Métricos. En esta tesis se presentan nuevas metodologías para resolver este problema que utilizan grafos G(V,E) para representar la base de datos métrica. En G, el conjunto V corresponde a los objetos del espacio métrico, y E a un pequeño subconjunto de arcos de V x V, cuyos pesos se calculan de acuerdo a la métrica del espacio en cuestión.
En particular, se estudian los grafos de k vecinos más cercanos (kNNGs). El kNNG es un grafo con pesos que conecta cada nodo de V ---o equivalentemente, cada objeto del espacio métrico--- con sus k vecinos más cercanos. Los kNNGs tienen muchas otras aplicaciones más allá de su utilidad para búsqueda en espacios métricos.
Se desarrollan algoritmos tanto para construir kNNGs en espacios métricos generales como para utilizarlos en búsqueda por similitud. Estos resultados permiten usar un grafo para indexar un espacio métrico requiriendo una cantidad moderada de memoria, con un desempeño de búsqueda por similaridad superior al obtenido utilizando las técnicas clásicas basadas en pivotes.
Finalmente, se muestra que la técnica basada en grafos ofrece un gran potencial para mejoras, que van desde índices completamente dinámicos basados en grafos hasta optimizaciones específicas para búsqueda en espacios métricos.
La gran cantidad de recursos computacionales requeridos para construir y recorrer estos grafos ha motivado también la investigación de problemas algorítmicos fundamentales, tales como ordenamiento incremental y colas de prioridad. Se proponen nuevos algoritmos para estos problemas, que en la práctica son superiores al estado del arte en varios casos. Estos algoritmos son útiles en muchos otros escenarios. En particular, permiten obtener un algoritmo simple y competitivo con el estado del arte para construir el árbol cobertor mínimo de un grafo aleatorio.
Los algoritmos propuestos no sólo abren nuevas líneas de investigación, por ejemplo algoritmos de construcción de árbol cobertor mínimo para grafos arbitrarios, sino que también resultan atractivos para aplicarse directamente en ambientes de desarrollo.