Técnicas de caching de intersecciones en motores de búsqueda

Los motores de búsqueda procesan enormes cantidades de datos (páginas web) para construir estructuras sofisticadas que soportan la búsqueda. La cantidad cada vez mayor de usuarios e información disponible en la web impone retos de rendimiento y el procesamiento de las consultas (queries) consume una cantidad significativa de recursos computacionales. En este contexto, se requieren muchas técnicas de optimización para manejar una alta carga de consultas. Uno de los mecanismos más importantes para abordar este tipo de problemas es el uso de cachés (caching), que básicamente consiste en mantener en memoria items utilizados previamente, en base a sus patrones de frecuencia, tiempo de aparición o costo. La arquitectura típica de un motor de búsqueda está compuesta por un nodo front- end (broker) que proporciona la interfaz de usuario y un conjunto (grande) de nodos de búsqueda que almacenan los datos y soportan las búsquedas. En este contexto, el almacenamiento en caché se puede implementar en varios niveles. A nivel del broker se mantiene generalmente un caché de resultados (results caché). Éste almacena la lista final de los resultados correspondientes a las consultas más frecuentes o recientes. Además, un caché de listas de posteo (posting list caché) se implementa en cada nodo de búsqueda. Este caché almacena en memoria las listas de posteo de términos populares o valiosos, para evitar el acceso al disco. Complementariamente, se puede implementar un caché de interscciones (intersection caché) para obtener mejoras de rendimiento adicionales. En este caso, se intenta explotar aquellos pares de términos que ocurren con mayor frecuencia guardando en la memoria del nodo de búsqueda el resultado de la intersección de las correspondientes listas invertidas de los términos (ahorrando no sólo tiempo de acceso a disco, sino también tiempo de CPU). Todos los tipos de caché se gestionan mediante una "política de reemplazo", la cual decide si va a desalojar algunas entradas del caché en el caso de que un elemento requiera ser insertado o no. Esta política desaloja idealmente entradas que son poco probables de que vayan a ser utilizadas nuevamente o aquellas que se espera que proporcionen un beneficio menor. Esta tesis se enfoca en el nivel del Intersection caché utilizando políticas de reemplazo que consideran el costo de los items para desalojar un elemento (cost-aware policies). Se diseñan, analizan y evalúan políticas de reemplazo estáticas, dinámicas e híbridas, adaptando algunos algoritmos utilizados en otros dominios a éste. Estas políticas se combinan con diferentes estrategias de resolución de las consultas y se diseñan algunas que aprovechan la existencia del caché de intersecciones, reordenando los términos de la consulta de una manera particular. También se explora la posibilidad de reservar todo el espacio de memoria asignada al almacenamiento en caché en los nodos de búsqueda para un nuevo caché integrado (Integrated caché) y se propone una versión estática que sustituye tanto al caché de listas de posting como al de intersecciones. Se diseña una estrategia de gestión específica para este caché que evita la duplicación de términos almacenados y, además, se tienen en cuenta diferentes estrategias para inicializar este nuevo Integrated caché. Por último, se propone, diseña y evalúa una política de admisión para el caché de intersecciones basada en principios del Aprendizaje Automático (Machine Learning) que reduce al mínimo el almacenamiento de pares de términos que no proporcionan suficiente beneficio. Se lo modela como un problema de clasificación con el objetivo de identificar los pares de términos que aparecen con poca frecuencia en el flujo de consultas. Los resultados experimentales de la aplicación de todos los métodos propuestos utilizando conjuntos de datos reales y un entorno de simulación muestran que se obtienen mejoras interesantes, incluso en este hiper-optimizado campo