Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | computacion |
| Título: | Técnicas de caching de intersecciones en motores de búsqueda |
| Título alternativo: | Intersection caching techniques in search engines |
| Autor: | Tolosa, Gabriel Hernán |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Departamento de Computación
|
| Publicación en la Web: | 2017-06-09 |
| Fecha de defensa: | 2016-09-19 |
| Fecha en portada: | 2016 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Director: | Feuerstein, Esteban |
| Jurado: | Lin, Min Chih; Navarro, Gabriel; Silvestri, Fabrizio |
| Idioma: | Inglés |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n6131_Tolosa |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n6131_Tolosa.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n6131_Tolosa |
| Ubicación: | Dep.COM 006131 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Tolosa, Gabriel Hernán. (2016). Técnicas de caching de intersecciones en motores de búsqueda. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n6131_Tolosa |
Resumen:
Los motores de búsqueda procesan enormes cantidades de datos (páginas web) paraconstruir estructuras sofisticadas que soportan la búsqueda. La cantidad cada vez mayorde usuarios e información disponible en la web impone retos de rendimiento y el procesamientode las consultas (queries) consume una cantidad significativa de recursos computacionales. En este contexto, se requieren muchas técnicas de optimización para manejaruna alta carga de consultas. Uno de los mecanismos más importantes para abordareste tipo de problemas es el uso de cachés (caching), que básicamente consiste en manteneren memoria items utilizados previamente, en base a sus patrones de frecuencia, tiempode 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 nodosde búsqueda que almacenan los datos y soportan las búsquedas. En este contexto, elalmacenamiento en caché se puede implementar en varios niveles. A nivel del broker semantiene generalmente un caché de resultados (results caché). Éste almacena la lista finalde los resultados correspondientes a las consultas más frecuentes o recientes. Además, uncaché 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é deinterscciones (intersection caché) para obtener mejoras de rendimiento adicionales. Eneste caso, se intenta explotar aquellos pares de términos que ocurren con mayor frecuenciaguardando en la memoria del nodo de búsqueda el resultado de la intersección de lascorrespondientes listas invertidas de los términos (ahorrando no sólo tiempo de acceso adisco, sino también tiempo de CPU). Todos los tipos de caché se gestionan mediante una "política de reemplazo", la cualdecide si va a desalojar algunas entradas del caché en el caso de que un elemento requieraser insertado o no. Esta política desaloja idealmente entradas que son poco probablesde que vayan a ser utilizadas nuevamente o aquellas que se espera que proporcionen unbeneficio menor. Esta tesis se enfoca en el nivel del Intersection caché utilizando políticas de reemplazoque 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 secombinan con diferentes estrategias de resolución de las consultas y se diseñan algunasque aprovechan la existencia del caché de intersecciones, reordenando los términos de laconsulta de una manera particular. También se explora la posibilidad de reservar todo el espacio de memoria asignadaal 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 listasde posting como al de intersecciones. Se diseña una estrategia de gestión específica paraeste caché que evita la duplicación de términos almacenados y, además, se tienen en cuentadiferentes 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é deintersecciones basada en principios del Aprendizaje Automático (Machine Learning) quereduce al mínimo el almacenamiento de pares de términos que no proporcionan suficientebeneficio. Se lo modela como un problema de clasificación con el objetivo de identificarlos 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 utilizandoconjuntos de datos reales y un entorno de simulación muestran que se obtienenmejoras interesantes, incluso en este hiper-optimizado campo.
Abstract:
Search Engines process huge amounts of data (i.e. web pages) to build sophisticated structuresthat support search. The ever growing amount of users and information availableon the web impose performance challenges and query processing consumes a significantamount of computational resources. In this context, many optimization techniques arerequired to cope with heavy query trafic. One of the most important mechanisms toaddress this kind of problems is caching, that basically consists of keeping in memorypreviously used items, based on its frequency, recency or cost patterns. A typical architecture of a search engine is composed of a front-end node (broker)that provides the user interface and a cluster of a large number of search nodes that storethe data and support search. In this context, caching can be implemented at severallevels. At broker level, a results cache is generally maintained. This stores the finallist of results corresponding to the most frequent or recent queries. A posting list cacheis implemented at each node that simply stores in a memory buffer the posting lists ofpopular or valuable terms, to avoid accessing disk. Complementarily, an intersectioncache may be implemented to obtain additional performance gains. This cache attemptsto exploit frequently occurring pairs of terms by keeping the results of intersecting thecorresponding inverted lists in the memory of the search node (saving not only disk accesstime but CPU time as well). All cache types are managed using a so-called "replacement policy" that decideswhether to evict some entry from the cache in the case of a cache miss or not. This policyideally evicts entries that are unlikely to be a hit or those that are expected to provideless benefit. In this thesis we focus on the Intersection Cache level using cost-aware caching policies,that is, those policies that take into account the cost of the queries to evict an itemfrom cache. We carefully design, analyze and evaluate static, dynamic and hybrid costawareeviction policies adapting some cost-aware policies from other domains to ours. These policies are combined with different query-evaluation strategies, some of them originallydesigned to take benefit of the existence of an intersection cache by reordering thequery terms in a particular way. We also explore the possibility of reserving the whole memory space allocated tocaching at search nodes to a new integrated cache and propose a static cache (namely Integrated Cache) that replaces both list and intersection caches. We design a specificcache management strategy that avoids the duplication of cached terms and we alsoconsider different strategies to populate the integrated cache. Finally, we design and evaluate an admission policy for the Intersection Cache basedin Machine Learning principles that minimize caching pair of terms that do not provideenough advantage. We model this as a classification problem with the aim of identifyingthose pairs of terms that appear infrequently in the query stream. The experimental results from applying all the proposed approaches using real datasetson a simulation framework show that we obtain useful improvements over the baselineeven in this already hyper-optimized field.
Citación:
---------- APA ----------
Tolosa, Gabriel Hernán. (2016). Técnicas de caching de intersecciones en motores de búsqueda. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n6131_Tolosa
---------- CHICAGO ----------
Tolosa, Gabriel Hernán. "Técnicas de caching de intersecciones en motores de búsqueda". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2016.https://hdl.handle.net/20.500.12110/tesis_n6131_Tolosa
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n6131_Tolosa.pdf
