Índices comprimidos para búsqueda por proximidad en series de tiempo

Abstract

Information Retrieval Systems have driven search engines with new technology that has improve queries in such way that most users are satisfied. IRS are concerned with representing, searching, and manipulating large collections of objects like databases of images, audio, electronic text and other multimedia representations. This project propose de compressed index Locality Sensitive Hashing (LSH) for information retrieval. The space in the LSH is reduced by using succint structures that occupy space close to the zero order empirical entropy H0. As second approach, the structure of the index is modified and the index LSH is implemented using a sequence index in order to reduce space even more. The LSH index is a representation for similarity search based on hash functions. The main idea is to apply a hash function to all objects in the database in such way that it makes sure that the probability of collision is higher for similar objects than for those that are different. The use of succinct structures is described to represent a compressed index. Because the increase of information is growing constantly, search index occupy each time more memory space, therefore, it is important to save indexes that occupy less space. The space occupied for the compressed index LSH is reduced close to the zero order empirical entropy H0, it has a percentage of recall between 80 and 92% and the time of recall is in the order of de milliseconds. The second proposal of compression, using the sequence index, called Locality Sensitive Classification (LSC) reduces the space in menor proportion than the compressed index LSH, the percentage of recall is preserve between 80 and 92% and the time of recall is in the order of the milliseconds.

Los Sistemas de Recuperación de Información (SRI) han aportado a los motores de búsqueda una nueva tecnología que ha mejorado las consultas de tal forma que gran parte de los usuarios se encuentran satisfechos. Los SRI se concentran en la representación, la búsqueda, y la manipulación de grandes colecciones de objetos como bases de datos de imágenes, audio, texto electrónico y otras representaciones multimedia. Este proyecto propone la compresión del índice Locality Sensitive Hashing (LSH) para recuperación de información. Se reduce el espacio requerido por el índice LSH utilizando estructuras sucintas que ocupan espacio cercano a la entropía de orden cero H0. Como segunda propuesta se modifica la estructura del índice y se implementa el índice LSH con un índice de secuencias para reducir el espacio aún más. El índice LSH es un esquema para búsqueda aproximada basado en funciones hash. La idea principal es aplicar una función hash a todos los objetos de la base de datos de forma tal que asegure que la probabilidad de colisión sea mayor para objetos que son cercanos que para aquellos que son diferentes. Se describe el uso de estructuras sucintas para hacer una representación comprimida del índice. Debido a que la información crece constantemente, los índices de búsqueda ocupan cada vez más espacio en memoria, por lo tanto, es importante poder almacenar ´índices que ocupen menor espacio. El espacio utilizado por el índice LSH comprimido se reduce cercano a la entropía de orden cero H0, tiene un porcentaje de respuesta entre el 80 y 92% y el tiempo de respuesta se encuentra en el orden de los milisegundos. La segunda propuesta de compresión, utilizando el índice de secuencias, llamada Locality Sensitive Classification (LSC) reduce el espacio en menor razón que el índice LSH comprimido, el porcentaje de respuesta se mantiene entre el 80% y 92% y el tiempo de respuesta se encuentra en el orden de los milisegundos.