Búsqueda práctica por proximidad en bases de datos de gran tamaño

Abstract

This work discusses a serie of proximity searching methods reaching excellent tradeoffs between time and memory. We present exact indexes, i.e., those retrieving the exact set of meeting the query’s constraints. Also, we create approximate indexes, i.e., algorithms and structures trading time and memory performances with the quality of the result. In both fields, our indexes are fast and small. Remarkably, some of them achieve storage sizes really close to the minimum of its representation. Our exact indexes perform half the distance computations of the state of the art methods (using practical amounts of memory). Furthermore, we experimentally demonstrate that the construction cost is reduced from O(n2) to O(λn1+α), where n is the size of the database, λ is a small value dependent of the data’s complexity (commonly between 1 and 12), and α < 1. Also, we introduce a metric compression technique saving half the storage requirements of the uncompressed index. In the part of approximate methods, we propose several indexes. All of these new indexes achieve excellent tradeoffs between time and memory costs. Also, the quality of the results is quite high, in both recall and proximity ratio. For instance, we created a new representation of the Locality Sensitive Hashing (LSH), based on sequences of symbols. This index needs a storage space close to the minimum (this lower bound is part of our contribution). The new representation is important because LSH requires several instances to improve the quality of its results.

En este trabajo presentamos una serie de índices alcanzando excelentes compromisos entre eficiencia en tiempo y memoria. Presentamos índices exactos, es decir, aquellos que recuperan el conjunto que satisface completamente la consulta data. Adicionalmente, creamos índices aproximados, es decir, algoritmos y estructuras que a costa de la exactitud de la consulta, alcanzan mayores velocidades de búsqueda. En ambas áreas, nuestros índices son rápidos y pequeños, y notablemente, algunos de ellos alcanzan un tamaño cercano al mínimo posible para cada representación. Nuestros índices exactos realizan cerca de la mitad de cálculos de distancia que el estado del arte (usando memoria dentro de los límites prácticos). Así mismo, el tiempo de construcción se reduce de manera sustancial de O(n2) a O(λn1+α), donde n es el tamaño de la base de datos, λ es valor pequeño que depende de la complejidad de los datos (comúnmente entre 1 y 12), y α < 1. También introducimos una técnica para compresión de índices métricos que para reduce los requerimientos de almacenamiento hasta la mitad de la versión descomprimida. En la parte de algoritmos métricos aproximados creamos varios índices, todos ellos alcanzando excelentes tiempos y costo en memoria. La calidad de los resultados es muy alta en términos de recall y proximity ratio (definidos en el siguiente capítulo). En particular, creamos una nueva representación para el índice Locality Sensitive Hashing (LSH), basada en una secuencia de símbolos. El índice necesita un espacio cercano al mínimo requerido (este límite inferior también es parte de nuestra contribución), esta representación es de vital importancia ya que LSH requiere múltiples instancias para mejorar la calidad de los resultados.