Estructuras de datos de diccionario y técnica de memoization.

Doctor en Ciencias, Mención Computación / Los autoíndices comprimidos para texto ofrecen una funcionalidad similar a la de los índices clásicos, ocupan espacio proporcional al tamaño del texto comprimido, y además lo reemplazan, pues son capaces de reproducir cualquier subcadena del texto. Aunque un índice comprimido es más lento que su versión clásica, puede funcionar en memoria principal en casos en que un índice tradicional tendría que recurrir a la memoria secundaria, que es órdenes de magnitud más lenta. Por otra parte, los autoíndices comprimidos para texto actuales sufren de varias deficiencias, como la falta de practicidad, la lentitud para localizar un patrón y para extraer un texto, y la falta de mecanismos de construcción eficientes en espacio, de versiones en memoria secundaria o de capacidades para actualizar el índice. Esta tesis aporta soluciones para todos estos problemas. Nuestra primera contribución es una estructura de datos para arreglos de bits, sencilla y eficiente, que permite consultas de rank y select, y que se ha hecho muy popular por su practicidad. También se creó el sitio Pizza&Chili, que contiene una colección de textos y de índices comprimidos, y se realizó un estudio práctico que compara los índices más prometedores. Cabe destacar que este sitio se ha convertido en una referencia habitual en la comunidad. Se desarrolló un nuevo índice comprimido para texto, basado en regularidades del arreglo de sufijos, el cual permite localizar ocurrencias rápidamente, y aún es más pequeño que los índices clásicos. Esta estructura se basa en Re-Pair, un compresor que posee propiedades de localidad que no tienen los índices comprimidos clásicos. Se desarrolló un codificador estadístico de secuencias, que permite el acceso directo a cualquier parte de la secuencia y logra una compresión de alto orden. Esta es una herramienta clave para lograr velocidad y localidad en la extracción de texto en un índice comprimido. Aprovechando esta localidad en la localización y en la extracción, se presentó un nuevo índice para memoria secundaria cuyo tiempo de acceso mejora gracias a la compresión, en lugar de empeorar como es lo normal en otros autoíndices. Este índice ofrece un compromiso muy competitivo entre espacio y tiempo. / Esta tesis ha recibido el apoyo de Mecesup, Proyecto UCH 0109, Chile; del Núcleo Milenio Centro de Investigación de la Web, Proyecto P04-067F, Mideplan, Chile; de Yahoo! Research Latin America, y del Instituto Milenio de Dinámica Celular y Biotecnología, Proyecto P05-001-F, Mideplan, Chile

Ingeniero Civil en Computación / En la actualidad existe una clara tendencia por buscar nuevos modelos de bases de datos que se adecuen de mejor manera a las necesidades modernas. Dentro de las alternativas que cuentan con popularidad se encuentran las denominadas bases de datos de grafos, que han adquirido fuerza en conjunto a la reciente revolución de la Web y sus tecnologías asociadas. La adopción de este modelo aún requiere de un amplio estudio, pues los grafos suponen una complejidad intrínseca que debe ser considerada al momento de diseñar una implementación. Dos desafíos fundamentales que se presentan son los volúmenes de información que deben ser manejados, junto con la elección de un buen lenguaje de consultas que equilibre el nivel de expresividad con su complejidad de evaluación. En este trabajo se considera un lenguaje de consultas ampliamente estudiado que permite realizar consultas de navegación a partir de expresiones regulares. Así mismo, se presenta un algoritmo de evaluación práctico para resolver estas consultas de manera eficiente. Adicionalmente se utiliza una representación para bases de datos de grafos que explota las características de las estructuras de datos sucintas para mantener grandes volúmenes de información en memoria principal. El trabajo presenta además una implementación de la propuesta considerando la extensibilidad y orden del código, con el fin de proveer una herramienta de utilidad para nuevas investigaciones. El desarrollo está dividido en dos componentes. Por un lado se proporciona una biblioteca con la implementación de las estructuras sucintas involucradas y por otro un sistema simple de gestión de base de datos que permite la evaluación de consultas del lenguaje escogido. Adicionalmente, y con el objetivo de comprobar el desempeño de la propuesta, se presenta una evaluación experimental de la implementación, realizando una comparación con algunas alternativas actuales para bases de datos de grafos y obteniendo resultados favorables. Finalmente se termina el trabajo señalando las conclusiones obtenidas del análisis experimental realizado.

Ingeniero Civil en Computación / Las estructuras de datos son la piedra angular en el desarrollo de cualquier algoritmo o programa. El código fuente de un programa suele describir, en esencia, una serie de operaciones y transformaciones sobre distintas estructuras de datos. El código no sólo debe expresar correctamente estas operaciones para que la máquina pueda ejecutarlas, sino que debe ser legible y entendible por aquellos que trabajan con él, tanto añadiendo nuevas funcionalidades como corrigiendo errores. La motivación principal de esta memoria es mejorar el proceso de documentación de código fuente al incorporar descripciones de las estructuras de datos en juego. Estas descripciones se pueden utilizar posteriormente para la generación de visualizaciones que ayuden a entender de mejor forma el código. Esta memoria describe el desarrollo de un lenguaje para la visualización de estructuras de datos. Se exploran aspectos teóricos y técnicos detrás de la construcción tanto del intérprete del lenguaje como del motor encargado de generar las visualizaciones. Complementario al intéprete y motor del lenguaje, se desarrolló una aplicación web que permite utilizar el lenguaje para generar visualizaciones de forma interactiva, así como explorar las distintas estructuras soportadas por el lenguaje. Se concluye publicando la herramienta en Internet y realizando una evaluación con múltiples usuarios, en la que se validó exitosamente la utilidad y facilidad de uso del lenguaje.

A continuación se presenta la Tesis doctoral que lleva por título Técnicas para la mejora del join paralelo y del procesamiento de secuencias temporales de datos, llevada a cabo por Josep Aguilar Saborit y dirigida por el profesor Josep.L Larriba-Pey.Los Sistemas Gestores de Bases de Datos (SGBDs) son las herramientas con las que se gestiona la información almacenada en una Base de Datos, ya sea para realizar consultas, actualizaciones o modificaciones. Los SGBDs se han convertido en una importante fuente de investigación y desarrollo encaminada a encontrar nuevas técnicas que hagan de los mismos unas herramientas lo más eficientes posible.Dentro del álgebra relacional, la operación más compleja y costosa de llevar a cabo por un SGBD, es la operación de join. Los métodos más conocidos y extendidos en la literatura para una ejecución rápida y eficaz de esta operación, son: Merge Sort Join, Nested Loop Join, Hash Join. Las dos primeras, para una ejecución eficiente, requieren de un cierto orden en los datos de sus relaciones fuente. Esto implica una ordenación previa o bien el soporte de una estructura auxiliar que de por si mantenga el orden de dichos datos. Por el contrario, la operación Hash Join no precisa de ningún orden sobre las relaciones fuente y utiliza hashing sobre los datos para resolver el join. Hash Join es una de las operaciones más utilizadas por los SGBDs y ha sido un importante foco de investigación con el fin de explotar al máximo sus posibilidades.Esta Tesis presenta cinco ténicas. Cuatro de ellas están destinadas a mejorar el rendimiento de la operación de join en SGBDs paralelos, tanto en configuraciones paralelas con recursos compartidos, como en configuraciones paralelas sin recursos compartidos. La última técnica, y que abarca un denso capítulo de la Tesis, presenta nuevas estructuras para representar de forma eficiente en espacio y tiempo secuencias temporales de datos.Todas las técnicas presentadas han sido publicadas. Los respectivos artículos también se adjuntan al final de esta documentación. Las referencias a dichos artículos se pueden consultar en el último apéndice de la Tesis.

No description available.

Las máquinas de búsqueda para la Web utilizan el índice invertido como estructura de datos que permite acelerar las búsquedas en grandes colecciones de texto. Para lograr tiempos de respuesta por consulta menores al medio segundo, tanto el índice como la colección de texto se particionan en dos grupos de máquinas distintos. Cada consulta se envía al primer grupo, las cuales responden con los documentos más relevantes para esa consulta. Desde estos resultados se seleccionan los documentos más relevantes en forma global. Dichos documentos se envían al segundo grupo de máquinas las cuales extraen de la colección de texto el resumen (o snippet) asociado a cada documento en el resultado y construyen la página Web final a ser presentada al usuario como respuesta a su consulta. En este trabajo de memoria se propone un método alternativo de procesamiento de consultas, el cual ocupa un solo grupo de máquinas para realizar ambas operaciones, es decir, en un solo grupo de máquinas se realiza la determinación de los mejores documentos y la construcción de la página Web de respuesta. Para esto se recurre al uso de estrategias de texto comprimido auto-indexado y memoria cache diseñada para mantener las listas invertidas de los términos más frecuentes en las consultas. El texto comprimido auto-indexado se utiliza para generar de manera on-line las listas invertidas y para generar el resumen asociado a cada documento en la respuesta a una consulta. Los resultados experimentales muestran que en el mismo espacio ocupado por el índice invertido estándar es posible ubicar la memoria cache de listas invertidas y el texto comprimido, y alcanzar la misma tasa de respuestas por unidad de tiempo que se logra con el índice invertido. La ventaja está en que en el nuevo esquema no es necesario el uso del segundo grupo de máquinas, y por lo tanto se logra un mejor uso de los recursos de hardware, lo cual es relevante para la operación económica de los grandes centros de datos para máquinas de búsqueda.

No autorizada por el autor para ser publicada a texto completo / El continuo aumento de los volúmenes de información almacenada digitalmente ha fomentado el desarrollo de técnicas para brindar acceso y búsqueda de manera eficiente a los datos. En particular, el manejo de grandes colecciones de imágenes es un problema de gran interés. Un enfoque es tratar las imágenes como secuencias de texto bidimensional. En este contexto, han sido planteadas recientemente dos estructuras de autoindexación para colecciones de imágenes, basadas en extender autoíndices de texto unidimensional. Estas estructuras almacenan la colección en espacio proporcional al requerido para almacenar la colección comprimida, permitiendo a la vez el acceso directo a cualquier parte de la colección y la búsqueda eficiente de patrones en ella. Dos tipos de autoíndices para secuencias de texto son el Arreglo de Sufijos Comprimido y el Índice FM, y en ellos se basan las soluciones para imágenes. Este trabajo se centra en la implementación de esos dos autoíndices para imágenes. Se implementaron distintas variantes para ambas estructuras buscando la mejor manera de adaptarlas a secuencias bidimensionales, y mejorando significativamente varios de los algoritmos originales. Finalmente se diseñaron y ejecutaron experimentos para comparar las distintas variantes de ambos índices, tanto en términos de espacio requerido por las estructuras, como de tiempo en responder las consultas de acceso y búsqueda de patrones. Las estructuras basadas en el Arreglo de Sufijos Comprimido resultaron mejores en cuanto a tiempo, mientras que aquellas basadas en el Índice FM resultaron mejores en términos de espacio requerido, cuando el rango de colores es pequeño. Por ejemplo, con el Arreglo de Sufijos Comprimido somos capaces de almacenar una colección utilizando un 80% del espacio que requeriría la representación plana, pudiendo dar acceso a cualquier subimagen a una velocidad aproximada de 1 megapixel por segundo. Con esta estructura somos capaces de contar las ocurrencias de un patrón a una velocidad aproximada de 0,5 megapixeles por segundo, y podemos localizar la posición de cada ocurrencia en menos de 0,1 milisegundo. Sobre colecciones con un rango de color más pequeño, utilizando el Índice FM podemos alcanzar niveles de compresión del 50 %, pudiendo llegar al 25% si aceptamos pérdida de información. Con esta estructura podemos acceder a cualquier subimagen y realizar la búsqueda de patrones a una velocidad de 0,1 megapixel por segundo.

Ingeniero Civil en Computación / En este trabajo se propone un nuevo método para la recuperación de documentos eficiente en espacio reducido. En términos generales, en recuperación de documentos se busca responder eficientemente a consultas sobre una colección de documentos con aquellos documentos cuyo contenido satisface algún criterio especificado en las consultas. Para acelerar las consultas los documentos son indexados con alguna estructura de datos. Las soluciones tradicionales para estos problemas basadas en índices invertidos no son adecuadas para dominios en los cuales los patrones de consulta son arbitrarios. Por ello, para colecciones cuyo contenido son, por ejemplo, secuencias de ADN, secuencias de proteínas, datos multimedia o algunos lenguajes naturales estas soluciones no son aplicables. Los índices de texto completo ofrecen una alternativa. Estos permiten indexar patrones generales pero incurren en un excesivo costo en espacio. Muthukrishnan diseñó una solución que utiliza este tipo de índices junto con otras estructuras para resolver listado de documentos. Su algoritmo es óptimo en tiempo pero consume más de veinte veces el espacio que ocupa la colección de documentos de entrada. Sadakane desarrolló una variante del algoritmo de Muthukrishnan. Para reducir el espacio introduce algunas modificaciones y diseña estructuras compactas que reemplazan las utilizadas por Muthukrishnan. Además extiende el algoritmo para resolver consultas de listado de documentos jerarquizadas. El espacio ocupado por el algoritmo de Sadakane para consultas jerarquizadas resulta excesivo para muchas aplicaciones prácticas. Aquí se proponen nuevas estructuras compactas para abordar este problema. Los resultados experimentales muestran que la nueva estrategia resuelve el problema de listado de documentos con sus frecuencias en un espacio menor y con la misma eficiencia que la solución original de Sadakane.

Doctor en Ciencias, Mención Ciencias de la Computación / Existe una necesidad creciente por contar con aplicaciones espacio-temporales que necesitan modelar la naturaleza dinámica de los objetos espaciales. Las bases de datos espacio-temporales intentan proporcionar facilidades que permitan apoyar la implementación de este tipo de aplicaciones. Una de estas facilidades corresponde a los métodos de acceso, que tienen por objetivo construir índices para permitir el procesamiento eciente de las consultas espacio-temporales. En esta tesis se describen nuevos métodos de acceso basados en un enfoque que combina dos visiones para modelar información espacio-temporal: snapshots y eventos. Los snapshots se implementan por medio de un índice espacial y los eventos que ocurren entre snapshots consecutivos, se registran en una bitácora. Se estudió el comportamiento de nuestro enfoque considerando diferentes granularidades del espacio. Nuestro primer método de acceso espacio-temporal (SEST-Index) se obtuvo teniendo en cuenta el espacio completo y el segundo (SESTL) considerando las divisiones más finas del espacio producidas por el índice espacial. En esta tesis se realizaron varios estudios comparativos entre nuestros métodos de acceso y otros métodos propuestos en la literatura (HR-tree y MVR-tree) para evaluar las consultas espacio-temporales tradicionales (time-slice y time-interval). Los estudios muestran la superioridad de nuestras estructuras de datos en términos de almacenamiento y eficiencia para procesar tales consultas en un amplio rango de situaciones. Para nuestros dos métodos de acceso se definieron modelos de costos que permiten estimar tanto el almacenamiento como el tiempo de las consultas. Estos modelos se validaron experimentalmente presentando una buena capacidad de estimación. Basándonos en nuestros métodos propusimos algoritmos para procesar otros tipos de consultas espacio-temporales, más allá de time-slice y time-interval. Específicamente diseñamos algoritmos para evaluar la operación de reunión espacio-temporal, consultas sobre eventos y sobre patrones espacio-temporales. Se realizaron varios experimentos con el propósito de comparar el desempeño de nuestros métodos frente a otros propuestos en la literatura (3D R-tree, MVR-tree, HR-tree y CellList) para procesar estos tipos de consultas. Los resultados muestran un rendimiento, en general, favorable a nuestros métodos. En resumen, nuestros métodos son los primeros que resuelven de manera eficiente no sólo las consultas de tipo time-slice y time-interval, sino también varias otras de interés en aplicaciones espacio-temporales.