Doctor en Ciencias, Mención Computación / Document Retrieval (DR) aims at efficiently retrieving the documents from a collection that are relevant to user queries. A challenging variant arises when the documents are arbitrary strings and the collection is large. This scenario arises in DNA or protein sequence collections, software repositories, multimedia sequences, East Asian languages, and others. Several DR compressed data structures have been developed to face this challenge, offering different space/time complexities. However, in practice the proposals with the best time performance require too much extra space. This thesis innovates in three aspects: (1) we build on Lempel-Ziv 1978 (LZ78) compres- sion, instead of suffix arrays, to build DR indices; (2) we build on Lempel-Ziv 1977 (LZ77) compression to handle highly repetitive collections; (3) we start the study of approximate answers in this DR scenario, which is common in DR on natural language texts. In this aspect, our main contribution is a new approach to DR based on LZ78 data compression, offering structures to solve the two most fundamental problems in the DR field: Document Listing (DL) and Top-k Retrieval. Our novel indices offer a competitive space/time tradeoff for both situations. Besides, our proposals are also capable of retrieving approximate answers, saving a lot of space and/or time compared with any structure that returns the full answer for any of these problems. Our second main contribution is the design of a structure for indexing highly repetitive text collections that solves the DL problem, which is built on the LZ77 parsing. This is the first attempt to solve DR problems using LZ77 data compression, which is the best compression scheme for such collections. On the other hand, we improve on basic data structures used, among others, in DR. We present an alternative design to the best theoretical Range Minimum Queries solution, maintaining its good complexities in space usage and query time. We obtain a simpler formula that leads to the fastest and most compact practical implementation to date. We also implemented various promising theoretical proposals for compressed suffix ar- rays, for which no previous implementations existed. Finally, we design and implement a compressed text index for highly repetitive collections that solves pattern matching, which is based on the LZ77 compression, and which is the basis for our LZ77-based DR index. / Document Retrieval (DR) apunta a la recuperación eficiente de documentos relevantes de una colección, para las consultas del usuario. Una variante que surge como desafío es cuando los documentos provienen de una gran colección de textos arbitrarios. Este escenario ocurre con colecciones de secuencias de ADN o proteínas, repositorios de software, secuencias multimedia e idiomas del Lejano Oriente, entre otros entornos. Varias estructuras de datos comprimidas para DR han sido desarrolladas a fin de hacer frente a este desafío, ofreciendo diferentes complejidades en tiempo/espacio. Sin embargo, en la práctica las propuestas con el mejor rendimiento en tiempo, requieren a su vez de demasiado espacio extra. Esta tesis innova tres aspectos: (1) construímos índices para DR en base a la compresión Lempel-Ziv 1978 (LZ78) en lugar de arreglos de sufíjos; (2) manipulamos colecciones altamente repetitivas en base a la compresión Lempel-Ziv 1977 (LZ77); (3) comenzamos a estudiar cómo entregar respuestas aproximadas en dicho escenario de DR, lo cual es una práctica común en textos de lenguaje natural. Nuestra principal contribución es un nuevo enfoque para DR basado en la compresión de datos LZ78, ofreciendo estructuras que resuelven los dos problemas fundamentales del campo de DR: Document Listing (DL) y Top-k Retrieval. Nuestros nuevos índices ofrecen desempeño competitivo en tiempo/espacio en ambos casos. Además nuestras propuestas también entregan respuestas aproximadas, ahorrando considerable espacio y/o tiempo comparado con cualquier otra estructura que entregue una respuesta completa a alguno de estos problemas. También diseñamos una estructura que indexa colecciones de texto altamente repetitivo y resuelve el problema de DL, basada en la compresión LZ77. Este el primer intento dirigido a resolver un problema de DR utilizando compresión de datos LZ77, que además es el mejor esquema de compresión para dichas colecciones. Por otro lado, realizamos mejoras sobre estructuras de datos básicas utilizadas en DR. Presentamos un diseño alternativo a la mejor solución teórica para Range Minimum Queries, manteniendo sus buenas complejidades en términos de espacio utilizado y tiempo de consulta. Logramos una fórmula más sencilla obteniendo como resultado la implementación más rápida y compacta conocida hasta hoy. Además implementamos varias propuestas teóricas promisorias para el arreglo de sufijos, de las cuales no existen implementaciones previas. Finalmente, diseñamos e implementamos un índice de texto comprimido para colecciones altamente repetitivas que resuelve el pattern matching, el cual se basa en la compresión LZ77, y que además es la base para nuestro índice sobre el LZ77 para DR. / This work has been partially funded by Conicyt Ph.D Scholarship Chile; Fondecyt Grant 1-140976; Millennium Nucleus for Information and Coordination in Networks, and Basal Center for Biotechnology and Bioengineering

Magíster en Ciencias, Mención Computación / Web search has become an important part of day-to-day life. Web search engines are important tools that give access to the information stored in the web. The success of a web search engine mostly depends on its efficiency and the quality of its ranking function. But also, web search engines give extra aids to their users, which make them more usable. An instance of this is the ability of generating result snippets and being able to retrieve the in-cache version of a web page, among others. Inverted indexes are a fundamental data structure used by web search engines to efficiently answer user queries. In a basic setup, inverted indexes only allow for simple (though fairly effective) ranking functions (e.g., BM25). It is well known that the high quality of nowadays search-engine results is due to sophisticated ranking functions. A particular example that has been widely studied in the literature is that of positional ranking functions, where the positions of the query terms within the resulting documents are used in order to rank them. To support this kind of ranking, the classical solution are positional inverted indexes. However, these usually demand large amounts of extra space, typically about three times the space of an inverted index. Moreover, if the web search engine needs to produce text snippets or display a cached copy of a web page, the textual data must be also stored. In this thesis we study time/space trade-offs for web search engines with positional ranking functions and text snippet generation. We aim to answer the question of whether positional inverted indexes are the most efficient way to store and retrieve positional data. In particular, we propose to get rid of positional data in inverted indexes, and instead obtain that information from the text collection itself. The challenge is to compress the text collection such that one can support the extraction of arbitrary documents, in order to find the positions of the query terms within them. We study and compare several alternatives for compressing the textual data. The first one uses a succinct data structure (in particular, a Wavelet Tree). We show how the space of the data structure can be reduced significantly, but also slowed down, by using high-order compressors within the nodes of the data structure. We then show how several text compression alternatives behave when used to obtain arbitrary documents (note that decompression speed is key in this application). Our starting point are compressors that either: (1) use little space for the text, yet with a slow decompression speed; and (2) have a very efficient decompression time (achieving a total performance comparable to that of positional inverted indexes), yet with a poor compression ratio. We then show how to obtain the best from both worlds: an efficient compression ratio, with a high decompression speed. We conclude that there exist a wide range of practical time/space trade-offs, other than just positional inverted indexes. The main result is that using only about 50% of the space of current solutions (i.e., positional inverted indexes plus the compressed text), one can support positional ranking and snippet generation almost with no time penalties. This seems to indicate that not to index positional data is the best solution in many practical scenarios. This can change the way in which positional data is stored and retrieved in web search engines.

Tesis para optar al grado de Doctor en Ciencias, Mención Computación / Los refinamientos actuales del análisis del peor caso sobre instancias con tamaño de entrada fijo consideran el orden de la entrada (por ejemplo, las subsecuencias ordenadas en una secuencia de números y las cadenas poligonales simples en las que puede dividirse una secuencia de puntos) o la estructura de la entrada (por ejemplo, la multiplicidad de los elementos en un multiconjunto y las posiciones relativas entre un conjunto de puntos en el plano), pero nunca, hasta donde sabemos, ambos al mismo tiempo. En esta tesis se proponen nuevas técnicas que combinan soluciones que se aprovechan del orden y la estructura de la entrada en una sola solución sinérgica para ordenar multiconjuntos, y para calcular la eficiencia de Pareto y la envoltura convexa de un conjunto de puntos en el plano. Estas soluciones sinérgicas se aprovechan del orden y la estructura de la entrada de tal forma que asintóticamente superan cualquier solución comparable que se aproveche solo de una de estas características. Como resultados intermedios, se describen y analizan varios algoritmos de mezcla: un algoritmo para mezclar secuencias ordenadas que es óptimo para cada instancia del problema; el primer algoritmo adaptativo para mezclar eficiencias de Pareto; y un algoritmo adaptativo para mezclar envolturas convexas en el plano. Estos tres algoritmos se basan en un paradigma donde las estructuras se dividen antes de ser mezcladas. Este paradigma es conveniente para extenderlo al contexto donde se responden consultas. Karp et al. (1998) describieron estructuras de datos diferidas como estructuras "perezosas" que procesan la entrada gradualmente a medida que responden consultas sobre los datos, trabajando la menor cantidad posible en el peor caso sobre instancias de tamaño fijo y número de consultas fijo. En esta tesis se desarrollan nuevas técnicas para refinar aún más estos resultados y aprovechar al mismo tiempo el orden y la estructura de la entrada y el orden y la estructura de la secuencia de consultas en tres problemas distintos: calcular el rango y la posici\'on de un elemento en un multiconjunto, determinar si un punto está dominado por la eficiencia de Pareto de un conjunto de puntos en el plano y determinar si un punto pertenece a la envoltura convexa de un conjunto de puntos en el plano. Las estructuras de datos diferidas que se obtienen superan todas las soluciones previas que solo se aprovechan de un subconjunto de estas características. Como una extensión natural a los resultados sinérgicos obtenidos en este trabajo para ordenar un multiconjunto, se describen estructuras de datos comprimidas que se aprovechan del orden y la estructura de la entrada para representar un multiconjunto, mientras se responden consultas del rango y la posición de elementos en el multiconjunto. / CONICYT-PCHA/Doctorado Nacional/2013-63130161, y los proyectos CONICYT Fondecyt/Regular nos 1120054 y 1170366

Magíster en Ciencias, Mención Computación / La estructura de la Web se puede modelar como un grafo, donde las páginas son los nodos y los hipervínculos las aristas. Estos grafos Web son ampliamente utilizados para diversas tareas de análisis de la Web, tales como el cálculo de Page-Rank o la detección de spam en la Web, entre otras. Una de las limitantes que se presentan al trabajar con estos grafos es su tamaño, por ejemplo, el 2005 se calculó que la Web pública y estática tenía 11.5 mil millones de nodos, y unas 15 aristas por nodo, lo que requiere más de 600 GB para su representación plana. De aquí surge la motivación de este trabajo, que consiste en la creación de estructuras de datos comprimidas para representar grafos de la Web. Una estructura comprimida busca almacenar la mayor cantidad de datos en el menor espacio posible, ya sea en memoria principal o en disco, soportando las consultas de interés sin la necesidad de descomprimir la estructura en su totalidad. La principal ventaja de estas estructuras es que se puede evitar mantener la información en disco o se disminuye la cantidad de transferencias necesarias. Esto es de vital importancia dado que el disco puede llegar a ser un millón de veces más lento que la memoria principal. Entre los resultados más importantes de este trabajo se presenta una estructura comprimida para grafos de la Web que mejora el estado del arte, ofreciendo el mejor compromiso espacio-tiempo conocido para recuperar listas de adyacencia. Además se muestra cómo extender esta estructura para soportar consultas más complejas, como vecinos reversos, manteniendo los requerimientos de espacio. Como productos agregados se incluyen resultados experimentales y propuestas para el problema de Rank y Select sobre secuencias generales, incluyendo estructuras no implementadas antes. Los resultados derivan en mejoras inmediatas para índices comprimidos para texto, en los cuales se reduce el espacio utilizado por los mejores índices existentes, a veces incluso sin penalización en el tiempo de búsqueda. Además se presenta un algoritmo aproximado para comprimir utilizando el método Re-Pair cuando la memoria principal es limitada. También se obtienen resultados en estructuras comprimidas para relaciones binarias, presentándose una nueva propuesta que, además de utilizar espacio proporcional a la entropía de la relación binaria, permite dinamizar la estructura, vale decir, aceptar inserciones y borrados de pares en la relación.

En el marco del análisis de redes sociales, estudiamos la red chilena de accionistas, una red dinámica cuyos actores son empresas y accionistas, y cuya relación es de propiedad. En particular, damos especial énfasis a una subred de ésta, la red de inversiones entre empresas, cuyos actores son empresas solamente. Para modelar la red de accionistas, recuperamos y procesamos la información disponible en el sitio Web de la Superintendencia de Valores y Seguros. Usando la proporción de propiedad de cada accionista en cada empresa, y los estados financieros de las últimas, modelamos esta red dirigida, dinámica y multivariable, desde Diciembre de 2003 hasta Junio de 2007. Para estudiar redes dirigidas multivariadas, diseñamos métodos empíricos y analíticos. Los métodos empíricos consisten en dos visualizaciones: perfiles de correlación de arcos y scatter-plots de redes. El método analítico consiste en reducir la topología del grafo a distribuciones de probabilidad (una para las relaciones y otra para los actores). Incluimos estas técnicas de análisis en una aplicación de software. Finalmente, estudiamos la red con las metodologías desarrolladas. Primero, buscamos propiedades generales de la red (encontrando, por ejemplo, que las empresas más grandes tienden a poseer o participar en las empresas más pequeñas). Luego, nos enfocamos en simular la red de inversión entre empresas, usando las distribuciones de probabilidad obtenidas de la red original. Concluimos que, aunque el modelamiento a nivel relacional, como la reducción de la topología a distribuciones de probabilidad, funciona relativamente bien al reproducir la red, no lo hace completamente ya que la red muestra propiedades emergentes, más allá del ámbito relacional.

No autorizado por el autor para ser publicada a texto completo / La cantidad de datos disponibles crece de forma dramática cada día. Esto trae consigo la necesidad de poder manejar éstos datos de forma adecuada, de manera de poder acceder a estos de forma eficiente y al mismo tiempo ahorrar espacio de almacenamiento. En particular, para manejar grandes cantidades de texto una herramienta clave son los índices de texto, y en el contexto de este trabajo los índices comprimidos, los cuales no sólo responden consultas de forma rápida sino que también almacenan sus datos y el texto en forma eficiente. El objetivo general del presente trabajo fue desarrollar un índice comprimido basado en listas de ocurrencias de los q-gramas del texto y comprimir este último. Se desea comparar la eficacia de este índice con los auto-índices ya desarrollados en el sitio Pizza&Chili (http://pizzachili.dcc.uchile.cl). Un índice invertido de q-gramas permite encontrar patrones en un texto. Para tal efecto las consultas se dividen en dos etapas. En la primera etapa se seleccionan las regiones del texto (llamadas bloques) donde ocurren todos los q-gramas del patrón y por lo tanto éste podría encontrarse. En la segunda etapa se verifica si efectivamente el patrón se encuentra en los bloques que fueron seleccionados. Además es necesario almacenar el texto de forma independiente. En la implementación realizada se mantiene el texto dividido en bloques comprimidos, los cuales se almacenan en memoria secundaria. Esto permite utilizar menos espacio y acceder a los bloques individualmente. Se implementaron diversos algoritmos para comprimir el índice y realizar consultas. Además se diseñaron y ejecutaron experimentos para medir el rendimiento de las distintas variantes obtenidas al combinar los diferentes algoritmos. En base a los resultados obtenidos se seleccionaron los algoritmos que presentaron mejor rendimiento tanto en velocidad como en niveles de compresión alcanzados. De la misma forma se implementaron y midieron experimentalmente alternativas para comprimir y buscar en el texto. Finalmente se comparó el rendimiento de las variantes seleccionadas del índice frente a los índices competitivos presentes en el sitio Pizza&Chili. Los resultados indican que el índice tiene un rendimiento competitivo para búsquedas de patrones pequeños.

Ingeniero Civil en Computación / El árbol de sufijos es una de las estructuras más importantes que se han creado para el manejo de cadenas de caracteres. Esta estructura permite encontrar eficientemente las ocurrencias de un patrón, en tiempo proporcional al largo del patrón. Adicionalmente soporta operaciones para resolver problemas complejos sobre una secuencia. Esta estructura tiene muchas aplicaciones en variadas áreas de la investigación , destacándose en la bioinformática, donde los recientes avances tecnológicos han permitido recolectar grandes colecciones de secuencias de ADN. La implementación clásica se vuelve impracticable para grandes volúmenes de información dado que ocupan demasiado espacio, que siempre muchas veces mayor que el texto mismo. Luego, no pueden ser almacenados en memoria principal, lo que en la práctica significa un aumento importante del tiempo de respuesta. Este problema es la principal motivación por la cual se buscan nuevas representaciones comprimidas de esta estructura, dando lugar a los árboles de sufijos comprimidos. Estos contienen la misma información que los árboles de sufijos pero ocupan un espacio considerablemente menor. Existen variadas propuestas teóricas para representar un árbol de sufijos comprimido, que ofrecen espacios y tiempos diferentes. En la práctica, dos estructuras destacan por sobre las demás. La primera fue propuesta por Sadakane e implementada por Välimäki et al. Esta estructura soporta la mayoría de las operaciones de navegación en tiempo constante, pero en la práctica requiere entre 25 y 35 bits por símbolo. La segunda fue propuesta por Fischer et al. e implementada por Cánovas, incorporando variantes y nuevas ideas para todas las estructuras que componen el árbol de sufijos comprimido propuesto por ellos. Una de estas variantes resulta ser superior a la implementación de Sadakane tanto en espacio como en tiempo, utilizando alrededor de 8 a 12 bits por símbolo. Dado que secuencias de ADN relacionadas son altamente similares, por ejemplo dos genomas humanos son muy parecidos, las colecciones pueden ser tratadas como un gran texto que contiene cadenas altamente similares. En este trabajo se propone e implementa una nueva variante del árbol de sufijos comprimido de Fischer et al, optimizada para textos altamente repetitivos. Se reemplazan y/o modifican cada una de las estructuras que componen el árbol por nuevas que presentan mayor compresión en textos repetitivos. El resultado más importante consiste en crear una nueva estructura inspirada en una técnica de compresión basada en gramáticas, aplicable al árbol de sufijos comprimido, que con poco espacio extra acelera considerablemente las operaciones sobre el árbol. Finalmente, la variante se compara experimentalmente sobre textos altamente repetitivos y resulta ser superior a la implementación de Cánovas, tanto en tiempo como en espacio, ocupando entre 3 a 6 bits por símbolo. / Este trabajo ha sido parcialmente financiado por el Instituto Milenio de Dinámica Celular y Biotecnología (ICDB) y el proyecto Fondecyt 1-080019

No description available.

No description available.

Magíster en Ciencias, Mención Computación / La recuperación de documentos consiste en, dada una colección de documentos y un patrón de consulta, obtener los documentos más relevantes para la consulta. Cuando los documentos están disponibles con anterioridad a las consultas, es posible construir un índice que permita, al momento de realizar las consultas, obtener documentos relevantes en tiempo razonable. Contar con índices que resuelvan un problema como éste es fundamental en áreas como recuperación de la información, minería de datos y bioinformática, entre otros. Cuando el texto que se indexa es lenguaje natural, la solución paradigmática corresponde al índice invertido. Sin embargo, los problemas de recuperación de documentos emergen también en escenarios en que el texto y los patrones de consulta pueden ser secuencias generales de caracteres, como lenguajes orientales, bases de datos multimedia, secuencias genómicas, etc. En estos escenarios los índices invertidos clásicos no se aplican con el mismo éxito. Si bien existen soluciones que requieren espacio lineal en este escenario de texto general, el espacio que utilizan es un problema importante: estas soluciones pueden utilizar más de 20 veces el espacio de la colección. Esta tesis presenta nuevos algoritmos y estructuras de datos para resolver algunos pro- blemas fundamentales para recuperación de documentos en colecciones de texto general, en espacio reducido. Más específicamente, se ofrecen nuevas soluciones al problema de document listing con frecuencias, y recuperación de los top-k documentos. Como subproducto, se de- sarrolló un nuevo esquema de compresión para bitmaps repetitivos que puede ser de interés por sí mismo. También se presentan implementaciones de las nuevas propuestas, y de trabajos relaciona- dos. Estudiamos nuestros algoritmos desde un punto de vista práctico y los comparamos con el estado del arte. Nuestros experimentos muestran que nuestras soluciones para document listing reducen el espacio de la mejor solución existente en un 40%, con un impacto mínimo en los tiempos de consulta. Para recuperación de los top-k documentos, también se redujo el espacio de la mejor solución existente en un 40% en la práctica, manteniendo los tiempos de consulta. Así mismo, mejoramos el tiempo de esta solución hasta en un factor de 100, a expensas de usar un bit extra por carácter. Nuestras soluciones son capaces de retornar los top-10 a top-100 documentos en el orden de milisegundos. Nuestras nuevas soluciones dominan la mayor parte del mapa espacio-tiempo, apuntando a ser el estándar contra el cual comparar la investigación futura.