Efficient access methods for metric data

Abstract

This thesis presents new methods to access the information on a computer. Concretely, searches on metric spaces. This apparently simple problem could be very complicated depending on the amount of the information stored, the type of query, the complexity of the representation of the data, and many others. The basic searches are, given an object, find the more similar elements. This type of searches are known as proximity searches or nearest neighbor searches, and has many applications like searching multimedia databases by content. The indexes are structures capable of answering these type of queries. The proximity search problem can be divided in two classes, in the first, the set of results coincide with the exhaustive search. The indexes corresponding to this class are called exact metric indexes. The rest of the indexes are called approximate metric indexes . This document presents the indexes EPT and ANNI for the exact case. They have simple parameters and both adjust to the circumstances of each database. The extensive experimentation shows their excellent performance in comparison to the state of the art. For the case of approximate searches, the indexes APG*, APG*-R, and BS are presented. All of them are the result of treating the nearest neighbor problem as an optimization problem. They are improvements over the well known APG. The thesis concludes with a study of the HSP graph that has multiple applications in metric space searches, ad-hoc networks, and others. Various properties of the graph and its generalization are presented.

En esta tesis se presentan varios métodos nuevos para acceder a información almacenada en una computadora. Concretamente, búsquedas en espacios métricos. Este aparente simple problema puede volverse muy complicado dependiendo del volumen de información almacenado, el tipo de consulta realizada y la complejidad de la representación de los objetos, entre otros. Las búsquedas básicas son, dado un objeto, encontrar los elementos más parecidos a él. Este tipo de búsquedas se llaman búsquedas de proximidad o búsquedas de vecino cercano y tienen muchas aplicaciones como búsquedas en bases de datos por contenido. Los ´índices son estructuras que nos permiten responder este tipo de consultas. El problema de búsqueda por proximidad puede dividirse en dos clases, en la primera, el conjunto de resultados coincide con el de la búsqueda exhaustiva. Los índices que corresponden a esta clase se les llama índices métricos exactos. Los otros índices corresponden a la segunda clase y se les llama ´índices métricos aproximados. Para el caso exacto se presentan los índices EPT y ANNI. Estos cuentan con simples parámetros ya que se ajustan a las circunstancias de cada base de datos. En los múltiples experimentos se muestra el excelente desempeño de ambos índices en comparación con el estado del arte. Para búsquedas aproximadas se presentan los índices APG*, APG*-R y BS. Todos ellos parten de ver al problema de encontrar al vecino más cercano como un problema de optimización. Estos índices son mejoras sobre el conocido APG. Finalmente, se hace un estudio del grafo HSP que tiene múltiples aplicaciones tanto en búsquedas de espacios métricos como en redes de sensores entre otras. Se presentan varias propiedades del grafo y de su generalización.