El almacenamiento digital de la información debe abordar tanto el problema de la incorporación de datos al sistema como su recuperación, y debe hacer un catálogo acorde con las consultas que sobre ellos quiera hacerse. El espacio ocupado para el almacenamiento y el tiempo necesario para ingresar la información, y para recuperala, depende directamente de la estructura utilizada en el repositorio. De este modo, cuando nos referimos a información que ya cuenta cion un grado de estructuración, la indexación debe ser coherente con la estructuta formal de la misma, para favorecer así la consulta. En el presente estudio se aborda el problema de la compresión estática de información semi-estructurada combinada con una indezación tendiente a soportar uin conjunto de consultas sobre los datos, con un fuerte énfasis en el almacenamiento en memoria secundaria. El ámbito de desarrollo de la aplicación propuesta se enmarca dentro de la documentación XML y su lenguaje de consulta XQuery. El modelo utilizado en la implementación está basado en la propuestas desarrolladas por Baeza-Yates y Navarro en Proximal Nodes. La implementación corresponde a un desarrollo posterior de un procesador destinado a soportar consultas en el lenguaje XPath desarrollado por Manuel Ortega como memoria de Ingeniería. El desarrollo de la capa de almacenamiento del prototipo actual se enfoca en la resolución de problemas en tres áreas: recuperación del archivo fuente, consulta eficiente sobre la estructura del documento, y búsqueda de texto en lenguaje natural. Las estructuras diseñadas adhieren a técnicas recientes en el área de la compresión y de recuperación de la información en XML. El resultado de esta memoria es un autoíndice XML con gran desempeño en colecciones de tamaño pequeño y mediano, con capacidad de abordar colecciones de gran tamaño con resucesos limitados de memoria principal, y con un gran potencial de adaptación para colecciones en un nuevo contexto dinámico. El prototipo presenta un desempeño altamente competitivo con las alternativas existentes en el estado del arte.

Doctor en Ciencias, Mención Computación / El principal objetivo de los sistemas de recuperación de información (SRI) es encontrar, lo más rápido posible, la mejor respuesta para una consulta de un usuario. Esta no es una tarea simple: la cantidad de información que los SRI manejan es típicamente demasiado grande como para permitir búsquedas secuenciales, por lo que es necesario la construcción de índices. Sin embargo, la memoria es un recurso limitado, por lo que estos deben ser eficientes en espacio y al mismo tiempo rápidos para lidiar con las demandas de eficiencia y calidad. La tarea de diseñar e implementar un índice que otorgue un buen compromiso en velocidad y espacio es desafiante tanto del punto de vista teórico como práctico. En esta tesis nos enfocamos en el uso, diseño e implementación de estructuras de datos compactas para crear nuevos índices que sean más rápidos y consuman menos espacio, pensando en ser utilizados en SRI sobre lenguaje natural. Nuestra primera contribución es una nueva estructura de datos que compite con el índice invertido, que es la estructura clásica usada en SRIs por más de 40 años. Nuestra nueva estructura, llamada {\em Treaps Invertidos}, requiere espacio similar a las mejores alternativas en el estado del arte, pero es un orden de magnitud más rápido en varias consultas de interés, especialmente cuando se recuperan unos pocos cientos de documentos. Además presentamos una versión incremental que permite actualizar el índice a medida que se van agregando nuevos documentos a la colección. También presentamos la implementación de una idea teórica introducida por Navarro y Puglisi, llamada Dual-Sorted, implementando operaciones complejas en estructuras de datos compactas. En un caso más general, los SRI permiten indexar y buscar en colecciones formadas por secuencias de símbolos, no solamente palabras. En este escenario, Navarro y Nekrich presentaron una solución que es óptima en tiempo, que requiere de espacio lineal y es capaz de recuperar los mejores $k$ documentos de una colección. Sin embargo, esta solución teórica requiere más de 80 veces el tamaño de la colección, haciéndola poco atractiva en la práctica. En esta tesis implementamos un índice que sigue las ideas de la solución óptima. Diseñamos e implementamos nuevas estructuras de datos compactas y las ensamblamos para construir un índice que es órdenes de magnitud más rápido que las alternativas existentes y es competitivo en términos de espacio. Además, mostramos que nuestra implementación puede ser adaptada fácilmente para soportar colecciones de texto que contengan lenguaje natural, en cuyo caso el índice es más poderoso que los índices invertidos para contestar consultas de frases. Finalmente, mostramos cómo las estructuras de datos, algoritmos y técnicas desarrolladas en esta tesis pueden ser extendidas a otros escenarios que son importantes para los SRI. En este sentido, presentamos una técnica que realiza agregación de información de forma eficiente en grillas bidimensionales, una representación eficiente de registros de accesos a sitios web que permite realizar operaciones necesarias para minería de datos, y un nuevo índice que mejora las herramientas existentes para representar colecciones de trazas de paquetes de red. / Este trabajo ha sido parcialmente financiado por Millennium Nucleus Information and Coordination in Networks ICM/FIC P10-024F, Fondecyt Grant 1-140796, Basal Center for Biotechnology and Bioengineering (CeBiB) y Beca de Doctorado Nacional Conicyt

Ingeniero Civil en Computación / En la actualidad, la cantidad de información que se genera en el mundo es inmensa. En el campo científico tenemos, por ejemplo, datos astronómicos con imágenes de las estrellas, los datos de pronósticos meteorológicos, los datos de infomación biológica y genética, etc. No sólo en el mundo científico se produce este fenómeno, por ejemplo, un usuario navegando por Internet produce grandes cantidades de información: Comentarios en foros, participación en redes sociales o simplemente la comunicación a través de la web. Manejar y analizar esta cantidad de información trae grandes problemas y costos. Por ello, antes de realizar un análisis, es conveniente determinar si el conjunto de datos que se posee es adecuado para lo que se desea o si trata sobre los temas que son de nuestro interés. Estas preguntas podrían responderse si se contara con un resumen del conjunto de datos. De aquí surge el problema que esta memoria abarca: Crear resúmenes semi-automáticos de conocimiento formalizado. En esta memoria se diseñó e implementó un método para la obtención de resúmenes semiautomáticos de conjuntos RDF. Dado un grafo RDF se puede obtener un conjunto de nodos, cuyo tamaño es determinado por el usuario, el cual representa y da a entender cuáles son los temas más importantes dentro del conjunto completo. Este método fue diseñado en base a los conjuntos de datos provistos por DBpedia. La selección de recursos dentro del conjunto de datos se hizo utilizando dos métricas usadas ampliamente en otros escenarios: Centralidad de intermediación y grados. Con ellas se detectaron los recursos más importantes en forma global y local. Las pruebas realizadas, las cuales contaron con evaluación de usuarios y evaluación automática, indicaron que el trabajo realizado cumple con el objetivo de realizar resúmenes que den a entender y representen al conjunto de datos. Las pruebas también mostraron que los resúmenes logran un buen balance de los temas generales, temas populares y la distribución respecto al conjunto de datos completo.

Magíster en Ciencias, Mención Computación / Las estructuras de datos compactas ofrecen funcionalidad y acceso a los datos usando poco espacio. En una estructura de datos plana se conservan los datos en su forma original y se busca minimizar el espacio extra usado para proveer la funcionalidad, mientras que en una estructura comprimida además se recodifican los datos para comprimirlos. En esta tesis se estudian estructuras de datos compactas para secuencias de bits (bitmaps) que proveen las operaciones rank y select: rankb(B,i) cuenta el número de bits b ∈ {0,1} en B[1..i] y selectb(B,i) retorna la posición de la i-ésima ocurrencia de b en B. En teoría ambas consultas se pueden responder en tiempo constante, pero la implementación práctica de estas soluciones no siempre es directa o con buenos resultados empíricos. Las estructuras de datos con un enfoque más práctico, usualmente no óptimas en teoría, pueden tener mejor desempeño que implementaciones directas de soluciones teóricamente óptimas. Esto es particularmente notorio para la operación select. Además, las implementaciones más eficientes para rank son deficientes para select, y viceversa. En esta tesis se definen nuevas estructuras de datos prácticas para mejorar el desempeño de las operaciones de rank y select, basadas en dos ideas principales. La primera consiste en, a diferencia de las técnicas actuales, que usan estructuras separadas para rank y select, reutilizar cada estructura también para acelerar la otra operación. La segunda idea es simular en tiempo de consulta una tabla de resultados precomputados en vez de almacenarla, lo que permite utilizar tablas universales mucho mayores que las que sería posible almacenar. Los resultados experimentales muestran que la primera idea, aplicada a estructuras planas, utiliza sólo 3% de espacio sobre el bitmap y ofrece tiempos similares a estructuras que usan mucho más espacio, para ambas operaciones. En estructuras de datos comprimidas se pueden combinar ambas ideas, obteniendo un espacio extra de menos de 7 % sobre el bitmap comprimido y manteniendo, para ambas operaciones, tiempos similares o mejores que las estructuras actuales (que usan 27 % de espacio extra).

Doctor en Ciencias, Mención Computación / El actual diluvio de datos está inundando la Web con grandes volúmenes de datos representados en RDF, dando lugar a la denominada Web de Datos. En la actualidad, se publican datos abiertos e interrelacionados sobre bioinformática, geografía o sobre redes sociales, entre otros, que forman parte de proyectos tan activos como Linked Open Data. Varias áreas de investigación han emergido de este diluvio; indexación y consulta de RDF (típicamente mediante el lenguaje SPARQL), razonamiento, esquemas de publicación, alineamiento de ontologías, visualización de RDF, etc. Los tópicos de la Web Semántica relacionados con RDF son, de hecho, trending topics en casi cualquier conferencia informática. Sin embargo, podemos discernir tres importantes hechos del actual estado del arte: i) se han realizado aplicaciones e investigaciones apoyándose en datos RDF, pero aún no se ha realizado un trabajo que permita entender la esencia de este modelo de datos, ii) las representaciones clásicas de RDF continúan influenciadas por la visión tradicional de la Web basada en documentos, lo que resulta en sintaxis verbosas, redundantes y, aún, centradas en humanos. Ello conlleva iii) publicaciones pobres y difusas, procesamientos complejos e ineficientes y una falta de escalabilidad para poder desarrollar la Web de Datos en toda su extensión. En esta tesis proponemos, en primer lugar, un estudio profundo de aquellos retos que nos permitan abordar un conocimiento global de la estructura real de los conjuntos de datos RDF. Dicho estudio puede avanzar en la consecución de mejores diseños de conjuntos de datos y mejores y más eficientes estructuras de datos, índices y compresores de RDF. Posteriormente, presentamos nuestra representación binaria de RDF, HDT, que afronta la representación eficiente de grandes volúmenes de datos RDF a través de estructuras optimizadas para su almacenamiento y transmisión en red. HDT representa eficazmente un conjunto de datos RDF a través de su división en tres componentes: La cabecera (Header), el diccionario (Dictionary) y la estructura de sentencias RDF (Triples). A continuación, nos centramos en proveer estructuras eficientes tanto para el diccionario como para dicha estructura de sentencias, ya que forman parte de HDT pero también de la mayoría de aplicaciones sobre grandes volúmenes de datos RDF. Para ello, estudiamos y proponemos nuevas técnicas que permiten disponer de diccionarios e índices de sentencias RDF comprimidos, a la par que altamente funcionales. Por último, planteamos una configuración compacta para explorar y consultar conjuntos de datos codificados en HDT. Esta estructura mantiene la naturaleza compacta de la representación permitiendo el acceso directo a cualquier dato.

En este artículo se presenta la propuesta de una arquitectura escalable para la mejora de la disponibilidad y escalabilidad de la información basada en google cloud platform para la empresa SmartBrands S.A.C., con la cual se obtuvo un incremento en su disponibilidad con respecto a su ERP de 1.5% y una mejora de 2.19% con respecto a su servidor on-premise, analizando los primeros meses del año 2020. También se demostró en este proyecto que el duplicar la capacidad del servidor central para mejorar el procesamiento de información era insuficiente ya que solo mejoró el proceso de respuesta en 6 segundos, por lo que se concluyó que para mejorar su escalabilidad este debería ser horizontal, en un segregamiento de procesos independientes, los cuales en funcionamiento y trabajando en conjunto crean una arquitectura para una mejorar adaptabilidad del sistema. Al tener esta arquitectura operando, nos permite tener un soporte para los diferentes eventos que puede acontecer en el sector retail, tales como el escalamiento de negocio por compra de marcas para su distribución, integración con api externas por contrato o por necesidad, reportes con segmentación de negocio, etc.

En la actualidad, el crecimiento vertiginoso de la cantidad de información genera volúmenes de datos cada vez más grandes y difíciles de comprender y analizar. El aporte de la visualización a la exploración y entendimiento de estos grandes conjuntos de datos resulta altamente significativo. Es frecuente que distintos dominios de aplicación requieran representaciones visuales diferentes; sin embargo, varios de ellos comparten estados intermedios de los datos, transformaciones, y/o requieren manipulaciones similares a nivel de vistas. Al analizar estos denominadores comunes se plantea la necesidad de contar con un modelo de visualización consistente para todas las áreas de visualización que sea válido para distintos dominios de aplicación. En este contexto se define el Modelo Unificado de Visualización (MUV), un modelo de estados representado como un flujo entre los distintos estados que asumen los datos a lo largo del proceso. Las características del proceso de visualización determinan que el usuario deba poder interactuar con los datos y sus representaciones intermedias, controlar las transformaciones y manipular las visualizaciones. En este contexto, la definición de una taxonomía de las interacciones en el área de visualización es sumamente necesaria para lograr un mejor entendimiento del espacio de diseño de las interacciones. El objetivo general de esta tesis consiste en establecer tanto las interacciones como una clasificación de las mismas en el área de visualización que sea válida en los distintos dominios de aplicación. Las interacciones definidas deberían poder aplicarse sobre las distintas transformaciones y estados del proceso de visualización. En este contexto, surge la necesidad de definir una representación para los conjuntos de datos lo suficientemente flexible y orientada al área de visualización, que permita soportar las distintas clasificaciones de datos, atributos, conjuntos de datos y mapeos visuales presentes en la literatura de visualización. Finalmente, con el objetivo de estudiar y validar los conceptos introducidos en esta tesis, se diseñó e implementó el SpinelViz y el Spinel Explorer, dos prototipos de visualización de datos geológicos. Para cada prototipo se diseñó un conjunto de interacciones dedicadas que contribuyeron directamente a un avance significativo en el flujo de trabajo de los geólogos expertos. Además, se mostró cómo la clasificación de las interacciones y las operaciones definidas permiten ordenar y facilitar el desarrollo de un sistema de visualización en un determinado campo de aplicación. / Nowadays, the vertiginous growth of information generates volumes of data that are increasingly larger and dificult to understand and analyze. The contribution of visualization to the exploration and understanding of these large data sets is highly significant. Usually, different application domains requiere different visual representations, however, several of them share intermediate states of data, transformations, and/or require similar manipulations. These common denominators suggest the need for a visualization model that is consistent for all visualization areas and valid for different application domains. In this context, the Unified Visualization Model (MUV) is defined. The MUV is a model of states represented as a ow among the different states assumed by the data throughout the process. The properties of the visualization process determine that the user should be able to interact with the data and its intermediate representations, control the transformations and manipulate the visualizations. In this context, the definition of a taxonomy of the interactions in the visualization area is extremely necessary to achieve a better understanding of the design space of the interactions. The overall goal of this thesis is to define the interactions and a classification of interactions in visualization, that is valid in different application domains. The defined interactions will be applied to the states and transformations of the visualization process. In this context, it is necesary to define a representation for the data sets involved in this process. This representation must be suficiently exible to support the different classifications of data, attributes, datasets and visual mappings present in the visualization literature. Finally, with the aim of studying and validating the concepts introduced in this thesis, we designed and implemented the SpinelViz and the Spinel Explorer, two prototypes for geological data visualization. For each prototype, a set of dedicated interactions that significantly improved the traditional work ow was designed. In addition, it was exposed how the presented classification and the defined operations allow to order and facilitate the development of a visualization system in a specific application field.