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.

En esta tesis se estudian dos sistemas fuera del equilibrio: una capa de agua vibrada vertical- mente que exhibe solitones hidrodinámicos no propagativos y un cristal líquido nemático al que se le aplica un campo eléctrico que exhibe vórtices. El objetivo principal de este estudio es caracterizar la interacción entre las estructuras localizadas de estos dos sistemas. En el primer capítulo se detalla la motivación de este trabajo y sus objetivos, además de una descripción de las estructuras a estudiar. En el segundo capítulo se detalla el montaje experimental en el que se estudian solitones hidrodinámicos no propagativos, las distintas técnicas de medición utilizadas para ello y el procesamiento de los datos obtenidos utilizando dichas técnicas. En el tercer capítulo se caracteriza teóricamente el sistema; primero se muestra un análisis lineal para una capa de agua, lo que permite calcular los modos propios de este sistema, luego se presenta un análisis no lineal a partir de la ecuación de Schrödinger no lineal con forzamiento paramétrico, que permite describir los solitones observados. En el cuarto capítulo se muestran los resultados experimentales que caracterizan el sistema que exhibe solitones, se miden los modos propios experimentalmente y se caracteriza la bifurcación en este sistema, también se compran estos resultados con los resultados teóricos presentados en el tercer capítulo En el quinto capítulo se estudia la interacción entre dos solitones; se revisa el cálculo teórico derivado de la ecuación de Schrödinger no lineal y se muestran resultados experimentales para la interacción, tanto para dos solitones en fase como para dos solitones en oposición de fase. En el sexto capítulo se describe el montaje experimental y la metodología de medición para el estudio de vórtices en un cristal líquido nemático sometido a un campo eléctrico, para este experi- mento se utiliza una celda fotosensible, que impone un campo eléctrico en las zonas iluminadas por un láser. En el séptimo capítulo se presentan los resultados experimentales del estudio de vórtices en este sistema, se estudia la interacción de dos vórtices de distinto signo y la localización de un vórtice al cambiar las condiciones de borde del sistema. Finalmente se presentan las conclusiones de este trabajo para ambos sistemas y se plantean algunas preguntas que podrían guiar el trabajo futuro, así, esta es una investigación que sigue en desarrollo.

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

Memoria para optar al título de Arquitecto / En los últimos 40, Dalcahue ha experimentado una serie de transformaciones y cambios, viéndose reflejado en la modificación de los patrones de asentamiento, la expansión de la trama urbana y la alteración de dinámicas sociales. Este fenómeno de crecimiento explosivo, se debe en gran parte a la instalación de grandes fábricas de extracción de productos marinos, la migración de habitantes de otras islas hacia la ciudad de Dalcahue se hizo inminente, generándose una creciente demanda de viviendas que requirió una solución urgente y eficiente; formando asentamientos de poblaciones, caracterizada por viviendas rígidas y estandarizadas, las cuales no responden de ninguna manera a las necesidades propias del habitante local. La prefabricación en madera en Chiloé es una variable poco explorada, pero es algo conocido y propio de la cultura local -practicado de manera artesanal en las iglesias chilotas-,por lo que la oportunidad de plantear el proyecto de título prefabricado en madera, es una alternativa conciente y necesaria para replantear el ‘cómo hacemos vivienda local hoy en día’ en los diferentes lugares del país. Particularmente en el caso de Dalcahue, es posible ver una ciudad fragmentada, una ciudad que a pesar de sus 7.000 habitantes, segrega y expulsa los nuevos grupos sociales de menor ingreso económico, generando una ciudad desarticulada, barrios sin ningún arraigo, conjuntos sin expresión y comunidades desconectadas delritmo Chilote. Es por esta razón, que el presente proyecto de título busca desarrollar una propuesta alternativa que surja de la comprensión del hábitat residencial, de las características culturales, geográficas y sociales propias del lugar, entregando una propuesta coherente con la identidad Chilota y enmarcada dentro de los mismos programas de subsidios estatales utilizados en la actualidad.

Los requerimientos actuales para el diseño sísmico de elementos de hormigón armado exigen un adecuado detallamiento de las zonas donde se espera que ocurran deformaciones inelásticas. En dichas zonas, se espera que los valores alcanzados por la amplitud de las deformaciones unitarias sean significativos, ya que durante sismos moderados dicha amplitud puede sobrepasar el 2%. A partir de ensayos cíclicos en elementos estructurales de hormigón armado, se observan tres modos de falla que pueden asociarse a la pérdida de ductilidad. Estos modos de falla son los siguientes: falla por compresión en el núcleo de hormigón debido a falta de confinamiento, pandeo por compresión en las barras de refuerzo longitudinal y fatiga de bajo número de ciclos en las barras de refuerzo longitudinal. El presente trabajo de título tiene como objetivo estudiar alternativas que permitan modelar la fatiga de bajo número de ciclos en las barras de refuerzo longitudinal en elementos estructurales de hormigón armado. El trabajo, de carácter teórico, pretende proveer información referente a la degradación de la capacidad resistente en el refuerzo longitudinal considerando la degradación cíclica producto de la fatiga de bajo número de ciclos, considerando además el efecto conjunto del pandeo al cual éstas barras son susceptibles de experimentar. En la actualidad, existe un modelo numérico de plasticidad concentrada desarrollado por Massone y Moroder (2009), validado por Lacaze (2009), capaz de representar la degradación en la capacidad resistente del refuerzo longitudinal producto del pandeo. Utilizando este modelo como base se incorporan diferentes alternativas que permiten modelar la degradación cíclica en el refuerzo. En este caso la metodología aplicada consiste en utilizar modelos de fatiga de materiales existentes en la literatura. Con esto es posible implementar el modelo de degradación cíclica para así determinar el efecto conjunto del pandeo y de la fatiga de bajo número de ciclos. La validación y calibración del modelo se realiza en base a los resultados experimentales disponibles en la literatura. Al comparar los resultados analíticos con los resultados experimentales, fue posible cuantificar la disminución en la capacidad resistente del material, llegando a disminuciones cercanas al 25%, dependiendo de la amplitud de deformación a la cual está sometido el espécimen. El modelo es capaz de representar el efecto que considera que a mayor amplitud de deformación, menor es la cantidad de ciclos para la falla del elemento. Por otra parte, el modelo permite representar la degradación cíclica del material pero no fue posible representar la última etapa de la degradación cíclica, correspondiente a la fractura del refuerzo producto del daño progresivo que experimenta el elemento.

Ingeniero Civil / El presente trabajo estudia el comportamiento estructural de un prototipo de vivienda modular, que tiene como objetivo ser una solución habitacional de emergencia ante desastres naturales como la ocurrencia de terremotos y tsunami. Los prototipos de vivienda de emergencia se componen de paneles SIP prefabricados, los que son paneles térmicos, construidos con un núcleo de poliestireno expandido de 45mm y dos placas de madera OSB de 9,5mm, ofreciendo resistencia estructural, aislación térmica y acústica. Se estudió el comportamiento estructural de los prototipos generados para 5 zonas del país: Las Cardas en la IV Región, Santiago en la Región Metropolitana, las Balsas en la VI, Pantanillos en la VII y Frutillar en la X Región. Finalmente por tratarse de una vivienda de emergencia, el prototipo no necesariamente debe cumplir con toda la normativa aplicable a una vivienda definitiva. Los estudios realizados indicaron que algunas estructuras como techos, pisos, y paneles que forman parte de los prototipos de emergencia no cumplen con algunos requerimientos dependiendo de la zona térmica donde se encuentren: Techo: Las localidades de Las Cardas, Santiago y Las Balas presentaron problemas de resistencia para la estructura de techo, los cuales pueden ser omitidos, debido a que constituyen exigencias que indica la normativa que no se presentan en el uso diario de los prototipos. Piso: Los pisos cumplen con lo que exige la normativa nacional, salvo en el caso de la localidad de Frutillar que cumple con el 97.5% de la carga de uso que exige la normativa (200kgf/m2). Por el carácter de vivienda de emergencia el valor obtenido se considera suficiente. Paneles: A partir de resultados de ensayos de laboratorio realizados en carga lateral y fuera del plano en los paneles que componen el prototipo de vivienda de emergencia, se logró concluir que el prototipo tolera el sismo de diseño y las máximas cargas de viento establecidas en la normativa nacional.

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.

Magíster en Ciencias de la Ingeniería, Mención Ingeniería Sísmica / La norma chilena que regula el diseño sísmico de estructuras e instalaciones industriales es la norma NCh2369.Of2003. Esta norma referencia a modo complementario el estándar AISC Seismic Provisions for Structural Steel Buildings , el cual presenta diferencias conceptuales respecto a la norma chilena, siendo la más importante la definición del mecanismo de disipación de energía sísmica. En la práctica norteamericana se espera que la disipación de energía ocurra sólo en elementos puntuales del sistema sismorresistente (fusibles), lo que requiere que la incursión inelástica de estos elementos esté ampliamente distribuida en altura, de modo de maximizar la disipación de energía y evitar mecanismos frágiles. En un contexto industrial, donde las estructuras se diseñan en gran parte para servir a la operación de equipos y maquinaria, lograr un detallamiento que permita una distribución amplia de plastificación de elementos fusibles no es simple, dada las irregularidades usuales de masa, rigidez y geometría que presentan las estructuras. Considerando lo anterior, la práctica chilena, además de los elementos fusibles tradicionales define el anclaje estructura-fundación como un punto de disipación adicional. La ventaja de este enfoque es que permite limitar en la base la cantidad de energía que ingresa a la estructura, reduciendo el daño de esta durante terremotos severos. Esta práctica ha mostrado un comportamiento exitoso en los últimos once terremotos de magnitud Richter-Kanamori mayor a 7.5. De manera de estudiar el impacto en el comportamiento sísmico de la aplicación de una u otra práctica, en este trabajo se diseñan paralelamente dos estructuras arriostradas típicas del rubro de la minería chilena utilizando los requisitos de NCh2369 y AISC. El comportamiento estructural se caracteriza por medio de los parámetros de desempeño y la metodología indicados en el estándar FEMA P695. Se estudia adicionalmente para cada práctica la distribución de energía sísmica entre los diferentes mecanismos de disipación y el efecto de incorporación de disipación adicional en el anclaje. Se observa que la utilización de un anclaje dúctil mejora el comportamiento estructural, reduciendo la demanda sobre los elementos resistentes y aumentando la ductilidad general. Se aprecia también que la incorporación de disipación adicional en el anclaje aparece como un medio eficiente de reducción de la demanda sísmica.

Realiza el análisis y diseño de 3 edificaciones de características similares; la primera, con la versión anterior de la norma sismorresistente E030 (2003); la segunda, teniendo la edificación en la zona 4 con la norma vigente E030 (2016); la tercera también con la norma vigente pero con la diferencia de que la edificación se encontrará en la zona 3. Luego se procederá a realizar los diseños de los elementos principales de las 3 edificaciones para luego realizar el cálculo de las dimensiones de placas, columnas, vigas, y el acero que estas tendrán en cada edificación. El propósito es saber qué influencia tienen los cambios que presenta la versión de la norma E030 actual (2016) en volumen y cantidad de acero y concreto para las edificaciones analizadas. Para la evaluación de los 3 casos, se realizará un análisis comparativo de los aspectos más importantes como fuerza basal, momentos, derivas, dimensiones y cuantías. Es decir se analizará si los cambios en la norma sismorresistente implican grandes variaciones en estos factores. Al final, se realizará un análisis de materiales de concreto y acero de cada estructura diseñada anteriormente para tener una idea del porcentaje en que pueden variar los costos del casco de una edificación al diseñarse con la versión de la norma 2016, con diferente zonificación del proyecto, respecto a la versión de la norma 2003.