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 Mecánico / La necesidad por desarrollar métodos cuantitativos para la detección de daño que puedan ser utilizados en estructuras complejas ha llevado a una continua investigación de métodos basados en los cambios en las características vibracionales de una estructura. Estos métodos son capaces de detectar daños pequeños en cualquier sector de una estructura. Tienen la ventaja que la ubicación del daño no debe ser conocida a priori y tampoco es necesario tener acceso a ella. Un área con potencial y que aún está en investigación, es el uso de las anti-resonancias en la detección de daño. Las anti-resonancias se pueden determinar de manera más precisa que los modos normales (usualmente utilizados), lo que puede resultar en una evaluación más precisa del daño. Este trabajo busca desarrollar un algoritmo de detección de daño utilizando anti-resonancias cruzadas y redes neuronales. Las redes neuronales artificiales son eficientes técnicas computacionales, usadas ampliamente para solucionar problemas complejos en muchos campos del conocimiento. El método se valida mediante datos simulados y experimentales de una viga libre y empotrada en distintas situaciones de daño. El estudio se estructura de la siguiente manera: Se generan los modelos en elementos finitos de las vigas y se crean las bases de datos analíticas de los casos de falla. Con las bases se entrenan las RNAs, luego se validan para después hacer la toma de datos experimentales. Con estos datos se validan experimentalmente las RNAs. Más tarde se procede con la introducción de ruido a los datos analíticos y finalmente se comparan los resultados con los obtenidos anteriormente. Se tratan los casos de una sola falla y dos fallas simultaneas en algún par de los 20 elementos en los cuales se discretizó la viga. Los daños se simulan disminuyendo porcentualmente la matriz de rigidez de alguno de los elementos de la viga. Se logran detectar todos daños inducidos en las vigas, teniendo más éxito en la viga libre debido a que el empotramiento implementado no pudo simular las condiciones de borde completamente, lo que se traduce en que los datos obtenidos no condicen con los datos simulados analíticamente, los cuales obedecen a un empotramiento perfecto. Se estudia la introducción de ruido pseudo-aleatoreo que sigue una distribución uniforme y una normal. Se concluye que el ruido mejora los resultados pero no logra acercarse del todo al caso experimental, por lo que se propone analizar otro método de introducción de ruido.

Ingeniera Civil Mecánica / Toda estructura en ingeniería se encuentra expuesta al daño y deterioro durante su vida útil. La información oportuna del deterioro que presenta puede incrementar la seguridad en su uso y mejorar su confiabilidad, además de reducir significativamente los costos asociados al mantenimiento. El uso de Redes Neuronales Artificiales (ANN en inglés artificial neural network) ha sido considerado en la detección de daño porque luego que la ANN es entrenada, utilizarla implica solo un gasto menor de recursos computacionales, lo que la hace idónea para monitoreo en tiempo real. Sin embargo, en la etapa de entrenamiento es necesaria gran capacidad computacional, la cual crece con la complejidad de la estructura. Además, mientras más elementos se quieran detectar con una red, más difícil se vuelve el entrenamiento y peores son los resultados. Esto último hace que la aplicación directa de redes neuronales en estructuras complejas sea casi imposible. Una solución es dividir la estructura en sub-estructuras y entrenar una red para cada sub-estructura por separado, este método se conoce como sub-estructuración. En el presente trabajo se obtiene un algoritmo capaz de identificar daño en estructuras de barras por medio del método de subestructuras combinado con ANN. Las frecuencias de resonancia y anti-resonancia de la estructura son las variables de entrada sensibles al daño y las variables de salida son factores de reducción de rigidez para cada elemento. El trabajo se divide en dos etapas principales; primero se modela en MATLAB la estructura mediante elementos finitos y se realiza un análisis con daño simulado, y luego se valida el modelo con una estructura experimental. El método de identificación de daño utiliza dos redes neuronales. La primera debe detectar la o las sub-estructura(s) con daño y la segunda debe detectar daños en cada elemento de la sub-estructura identificada por la primera red. De esta forma se reduce el tamaño de cada ANN, y con esto los recursos computacionales necesarios para entrenarlas. El daño en un elemento tiene dos representaciones; a nivel de elementos finitos se considera un factor de reducción de rigidez y a nivel experimental se considerarán cortes en las secciones. El desarrollo de la primera red entrega buenos resultados a nivel numérico y logra detectar las subestructuras dañadas en tres de los cuatro casos de daño experimental. Para su entrenamiento se incluyeron las frecuencias de resonancia y las frecuencias de anti-resonancia de los nodos límite de cada subestructura. Las redes de la segunda etapa, una para cada subestructura, se logran entrenar a nivel numérico dependiendo principalmente del número de entradas disponibles, lo cual permite que tres de las seis presenten resultados muy buenos. La validación con datos experimentales detecta los daños 5 existentes en los casos estudiados, pero sólo logra cuantificar y localizar uno de ellos. Por lo tanto, el uso de un método de sub-estructuración y redes neuronales para la identificación de daño en estructuras de barras, resultó correcto en la etapa de localización de subestructuras dañadas. Sin embargo, para la identificación de elementos dañados en cada sub-estructura es necesario asegurar una cantidad mínima de datos de entrada a la red (frecuencias de anti-resonancia) que permita el correcto entrenamiento de la red neuronal.

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.

Esta investigación evidencia las ventajas de automatizar el funcionamiento de una red neuronal, en el contexto de aplicaciones financieras de valoración de activos y portafolios. Demostramos que el establecimiento de forma manual de las funciones de activación tiene efectos adversos sobre la efectividad de la red; en términos de los niveles de error alcanzados. Se encuentra que el hacer una elección óptima puede disminuir entre un 20% y un 95% el ECM del modelo. Además se desarrollan las bases de un modelo teórico de resolución de Redes Neuronales que no requiere de la selección de una función de activación, ya que éstas son resultado del proceso de optimización del modelo

Ingeniero Comercial, Mención Administración / En el siguiente trabajo se busca demostrar que las Redes Neuronales pueden ser usadas para predecir la variación en el precio de una acción. Los resultados obtenidos nos ayudan a creer que estos métodos de inteligencia artificial están muy prontos a ser las herramientas esenciales para trabajar y desenvolverse en los mercados financieros. Una de nuestras motivaciones para hacer este trabajo tenía que ver con la efectividad de esta herramienta, y si dicha efectividad motiva a que ya estén siendo usadas en grandes compañías financieras y mesas de “trading” en otros países. Una característica a destacar es que a diferencia de estudios anteriores, éste se realiza con datos diarios. Al probar que el modelo funciona y es efectivo, concluimos que es posible obtener rentabilidades diarias, rápidas y a corto plazo. La aplicación se efectúa en una acción del mercado estadounidense, a pesar de la inestabilidad actual de dicho mercado afectado por la crisis financiera. La razón es porque la empresa estudiada se beneficia del gran plan de energía renovable implantado por el presidente Obama. Dicho plan, creado para la reactivación económica del país, otorga beneficios y solidez financiera a empresas como First Solar, dedicada a la producción de paneles solares. Si bien la metodología de este trabajo se basa en una red neuronal, se ocupan otras herramientas que ayudan al modelo, como las Bandas de Bollinger, la teoría de ondas de Elliott y el test de Perasan & Timmermann, entre otros. Todo esto en conjunto nos ayuda a demostrar que el modelo funciona con una significancia estadística, lo cual demostraremos más adelante. Conclusiones hay varias, pero creemos que la más importante es que los modelos financieros y las formas de predecir se están actualizando. Los modelos econométricos clásicos están obsoletos y los operadores, brokers y gente desenvuelta en éste ámbito no pueden quedar ausente ante estos cambios.

Encontrar buenas cotas inferiores y condiciones necesarias para nociones de complejidad y universalidad es uno de los mayores desafíos en el área de la informática teórica. En este sentido, la teoría de la complejidad comunicacional ha resultado ser una herramienta útil para abordar tal problemática en diversos modelos de computación, tales como circuitos booleanos, máquinas de Turing y modelos no convencionales. En este trabajo se incorporan tales técnicas al estudio del conjunto de autómatas celulares unidimensionales. Dada una relación de simulación ≤ y autómatas celulares (ACs) Φ y Ψ, se denota Φ ≤ Ψ si es el caso que Φ puede ser simulado por Ψ. Un AC Ψ capaz de simular a todo otro AC Φ es denominado como intrínsecamente ≤ - universal. Aquí son considerados tres tipos de simulaciones presentes en la literatura: sobreyectiva, inyectiva y mixta, siendo las dos últimas capaces de soportar universalidad intrínseca. Por otro lado, para la primera de éstas, la existencia de un elemento universal aún sigue siendo un problema abierto. Seguidamente, son definidos cinco problemas comunicacionales inducidos por ACs: Pred, Cycl, SInv, TInv y CInv, de tal manera que PΦ(x, y) indica la parametrización de un problema genérico P por un AC Φ, donde AΦ es el conjunto de estados de éste y x, y ϵ AΦ+ son inputs. Tales problemas cumplen con ser compatibles comunicacionalmente, esto es, si Ψ simula a Φ, se tiene que la complejidad comunicacional asociada a Φ es de menor o igual orden a la de Ψ. De este modo, si la complejidad comunicacional de PΦ es de orden estrictamente menor a la de PΨ, se puede deducir que Φ no es intrínsecamente universal. Luego, como punto fuerte, se introduce una nueva problemática comunicacional que logra aunar las técnicas y condiciones necesarias previamente estudiadas. Informalmente, cuando Alice y Bob (los participantes en el modelo usual de complejidad comunicacional) reciben respectivamente inputs x e y, tienen la posibilidad de escoger qué problema P resolver. Se entregan resultados mostrando que tal libertad hace de este nuevo problema, denominado Ovrl, un potente filtro a la hora de desechar ACs como intrínsecamente universales. Más precisamente, se construye un AC con complejidad máxima en los cinco problemas anteriores y complejidad constante en Ovrl. Finalmente, se utilizan las herramientas desarrolladas para descartar en familias completas de autómatas celulares la cualidad de universalidad intrínseca. Además, se estudia la estructura de los preórdenes dados por las relaciones de simulación, caracterizando algunos conjuntos cerrados bajo simulación, tales como los ACs sobreyectivos, cerrados y reversibles, entre otros.

Geólogo / El presente estudio se realizó en el Complejo Volcánico Tres Puntas, el cual presenta una extensa zona de alteración hidrotermal ubicada en la Cordillera Claudio Gay, Región de Atacama, en el noreste de la franja de Maricunga. Dado su contexto geodinámico y metalogénico, el área de estudio presenta un gran interés para la prospección de metales preciosos. En el área de estudio se realizó una campaña de exploración básica, en la cual se recolectaron 113 muestras de superficie (rocas y suelo) y se reconocieron las características litológicas, mineralógicas y texturales de varios de los puntos de muestreo. Se analizó la composición química de roca total de las muestras, obteniéndose concentraciones para 49 elementos mayores y trazas, respectivamente mediante ICP-MS e ICP-ES. Asimismo se obtuvieron las concentraciones de Au mediante AAS, utilizando un ensayo de fusión a fuego. En términos generales, las características geoquímicas, mineralógicas y de alteración, son compatibles con un sistema epitermal de Au de alta sulfuración. Los datos geoquímicos fueron estudiados utilizando redes neuronales artificiales (RNA). La aplicación de esta técnica permitió realizar un análisis multi-elemento de este set de datos, el cual incluye un número elevado de muestras con características litológicas y mineralógicas variadas. Como resultado del análisis mediante RNA, fue posible sub-dividir el set de datos en 6 Grupos Geoquímicos, es decir, 6 conjuntos de muestras con características geoquímicas similares. La proyección de esta información sobre el área de estudio, permitió identificar marcadas zonaciones geoquímicas, donde destacan dos zonas prospectivas, distanciadas aproximadamente en 1 km, que se caracterizan por concentrar las muestras con mayores valores de Au y Ag, además de las mayores abundancias de Pb, As, Sb, Te, Bi, Se, Sn, W y S (muestras de los Grupos Geoquímicos 3, 4 y 6). Estas correlaciones geoquímicas coinciden con las esperadas para sistemas epitermales de metales preciosos. El carácter prospectivo de estas zonas se ve reforzado dado que ellas coinciden estrechamente con una zona de alteración argílica avanzada y con una zona de alteración silícea. Las muestras con mayores valores de Cu se correlacionan con las mayores abundancias de Co y Cd (Grupo Geoquímico 5) y estarían relacionadas a rasgos de mayor profundidad (asociados a metales base) por lo que se interpreta como posibles estructuras locales (fallas de colapso) y además se relacionan con un cuerpo intrusivo hipabisal de composición diorítica que aflora en una de las zonas prospectivas. Cabe destacar que las muestras asociadas al Grupo Geoquímico 2 comparten algunas características con el Grupo Geoquímico 5, pero presentan una distribución espacial más dispersa, con algunas muestras dentro de las zonas que se definen como más prospectivas. Las muestras asociadas al Grupo Geoquímico 1 marcan una zona de bajo interés prospectivo ya que presenta algunas características geoquímicas afines con los Grupos Geoquímicos 3 y 6, pero no se relacionan con las anomalías esperadas para sistemas epitermales de metales preciosos.

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.