Magíster en Ciencias de la Ingeniería Informática (MII)

En esta tesis, se presentan algoritmos y estructuras de datos eficientes en espacio y tiempo para el problema offline set intersection. Mostramos que un conjunto de enteros ordenados s c [0..u) de n elementos se puede representar usando espacio comprimido, mientras se soportan intersecciones de k conjuntos en tiempo adaptativo O(k&log(u/&)), siendo & la medida de alternancia introducida por Barbay y Kenyon. De esta manera, se mostrará que el desempeño adaptativo de algoritmos como el de Demaine, López-Ortiz y Munro [SODA, 2000], y el de Barbay y Kenyon [TALG, 2008] se puede lograr usando espacio comprimido, introduciendo nuevos conocimientos sobre este problema algorítmico fundamental. Los resultados experimentales sugieren que nuestros enfoques son competitivos en la práctica, superando las alternativas más eficientes (Partioned Elias-Fano, Roaring Bitmaps, y Recursive Universe Partitioning (RUP)) en varios escenarios, ofreciendo en general trade-offs espacio-tiempo relevantes.

Los inminentes problemas asociados al cambio climático han acelerado los esfuerzos para lograr una pronta transición energética hacia fuentes renovables. Por ende, la estimación precisa y a gran escala del potencial de generación de distintas energías renovables tomar una nueva importancia en el proceso de toma de decisiones y políticas públicas. La estimación fotovoltaica sobre las zonas urbanas es particularmente complicada dada la influencia de las oclusiones del sol por edificaciones adyacentes, la disponibilidad incierta de áreas favorables para las instalaciones y la ausencia de datos apropiados públicamente disponibles y confiables. El Ministerio de Energía ha generado una base de datos del potencial fotovoltaico urbano de Santiago, que puede utilizarse para efectos de aprendizaje. Más aún, una segunda base de datos, obtenida desde el Servicio de Impuestos Internos, presenta descriptores de las edificaciones presentes en el territorio nacional, entre otras, el número de pisos o la superficie total construida. Esto permite consolidar una base de datos a nivel de manzana, la cual presenta una lista de edificios con sus respectivos descriptores y el potencial fotovoltaico, en términos del área favorable, de esta. Con estos datos se puede realizar aprendizaje automático para modelar la relación entre las características de las manzanas y su potencial. Esta prometedora aproximación tiene, sin embargo, una dificultad adicional: distintos registros (i.e. manzanas) tienen distinto número de edificaciones, y por ende distinta dimensionalidad. Esto requiere por lo tanto un manejo particular de los datos, los cuales tienen largo variable. En el presente proyecto se propone aprovechar la capacidad de las redes convolucionales uno dimensionales de aprender patrones sobre secuencias de datos para realizar el aprendizaje sobre representaciones secuenciales de los datos disponibles. Más aún, se propone utilizar los datos tanto en la representación habitual “homogénea” (distintas posiciones de la secuencia corresponden a distintas instancias del mismo tipo de dato), como “heterogéneas” (distintas posiciones corresponden a distintos tipos de datos, en nuestro caso, distintos atributos de las edificaciones), como una tercera representación “mixta”, inicialmente homogénea seguida de heterogénea. Además, esto permitirá igualmente a la red aprender representaciones convolucionales significativas de los datos. Si bien estas innovadoras representaciones heterogénea y mixta no permiten mejorar significativamente los resultados del estado del arte homogéneo, si se aprecian diferencias en los costos computacionales asociados, siendo la representación heterogénea significativamente menos costosa en tiempos de entrenamiento y predicción que la representación estándar homogénea. Esto se evidencia igualmente en el aprendizaje realizado sobre las representaciones intermedias, donde la representación heterogénea aprendida logra desempeños similares utilizando órdenes de magnitud menos dimensiones que las otras representaciones.

Los sistemas de transporte son componentes críticos para las ciudades, impactando inmensamente la calidad de vida de sus ciudadanos, proveyendo alternativas de transporte, reduciendo drásticamente el tráfico vehicular y la contaminación atmosférica. Se requiere de una cuidadosa planificación para evitar usuarios descontentos y un sistema insostenible, siendo fundamental el correcto diseño de la red de rutas de buses. En consecuencia, el Urban Transit Routing Problem (UTRP) se enfoca en encontrar un conjunto de rutas de buses que minimiza el tiempo de viaje de los pasajeros y los costos al operador del sistema. Varios algoritmos han sido desarrollados para resolver el UTRP, pero la mayoría de las instancias del problema carecen de datos de demanda de la vida real, con las instancias más conocidas siendo muy pequeñas para los estándares actuales y/o generadas aleatoriamente. Las técnicas de relajación del estado del arte se basan en características inherentes de los sistemas de transporte urbano y no pueden reducir de manera significativa el orden de magnitud de instancias complejas. En este trabajo, se propone un framework para generar instancias de UTRP usando datos de demanda zonal de la vida real, que incluyen miles de ubicaciones de paraderos. Los algoritmos de clustering permiten al framework reducir la complejidad del problema generando una aproximación que mantiene el comportamiento de la demanda y la estructura de caminos manteniendo conectadas y representadas tanto ubicaciones centrales como periféricas. El framework se aplica al complejo sistema de transporte público de la ciudad de Santiago de Chile. Se generan instancias con un comportamiento similar de demanda al usar una cantidad suficiente de clústeres. Además, los diversos algoritmos de clustering probados muestran una alta similitud en su salida y rendimiento. Este framework es fácilmente aplicable a diferentes realidades y debería ayudar a futuros investigadores en el diseño de algoritmos de resolución, así como mejorar los modelos de aproximación de otras ciudades.

Construir software seguro requiere tomar decisiones de diseño que permitan cumlir los requerimientos de seguirdad deseados; estas decisiones deben realizarse detenidamente antes de ser establecidas, lo anterior debido a que un mal diseño podría impactar gravemente el resultado final de un sistema, afectando los objetivos esperados. Respecto al punto anterior, son los arquitectos quienes suelen tomar estas resoluciones, basándose tanto en sus experiencias como en el uso de diferentes técnicas de arquitectura, como por ejemplo el uso de tácticas de arquitectura de software; por otro lado, los desarrolladores también ejecutan acciones claves al desarrollar el software, sin embargo es posible que estos no consideren de forma sistemática y primordial la importancia de un diseño seguro desde el punto de vista de las decisiones de diseño. El trabajo realizado en esta tesis presenta la Técnica TaSPER (Security Tactics Selection Poker), técnica consensuada basada en Planning Poker, la cual permite que todas las peronas involucradas en un desarrollo de software puedan identificar, argumentar, discutir y seleccionar las tácticas de seguridad para el desarrollo de arquitectura de acuerdo a los objetivos, requerimientos y prioridades establecidas. Para lograr esto, primero se realizó un estudio de caso a un grupo de nueve profesionales de la Armada de Chile, para luego desarrollar un estudio experimental el cual consideró cinco etapas: definición, planificación, evaluación, ejecución y análisis. Para ello, se realizaron dos pre-experimentos con estudiantes de pregrado y postgrado en diferentes universidades y finalmente, se ejecutó un experimento con veinte profesionales del Programa del Magíster en TI con el objeto de evualuar la efectividad de la técnica en varios escenarios. Los resultados muestran que la técnica TaSPeR apoya la toma de decisiones arquitectónicas colaborativas, formenta la participación de los diferentes involucrados y genera una dinámica grupal sobre cómo actuar contra las amenazas. Al mismo tiempo, se pudo determinar que la técnica propuesta permite decisiones más cercanas a Ground Truth (establecido por expertos) en comparación con decisiones individuales tomadas por los participantes. Por tanto, el uso de una técnica consensuada para la evualuación de arquitecturas parece ser un enfoque prometedor para establecer de forma grupal la seguridad en el desarrollo de software.

Las tecnologías de las Web Semántica están cambiando las formas en la que se comparte la información, sustituyendo los grandes volúmenes de información en formato HTML por datasets en los que el dato en bruto es tratado como un “ciudadano de primera clase”. Este nuevo enfoque busca persuadir a las organizaciones, empresas e individuos a que publiquen sus datos libremente siguiendo los estándares propuestos por la W3C y enlazando diferentes áreas del conocimiento generando la llamada Web de los Datos Enlazados. El público objetivo para consumir estos datos incluye tanto personas como aplicaciones de software. En los últimos años, la aplicaciones de software han incrementado las capacidades de extraer información útil de estos grandes volúmenes de datos estructurados utilizando lenguajes como SPARQL que es el estándar para consultar datos RDF y se ha implementado en una amplia variedad de motores. Estos motores brindan el acceso a los datos a través de endpoints públicos en la Web, los cuales reciben miles de consultas diariamente. En muchos casos, estos endpoints enfrentan dificultades al evaluar consultas complejas o cuando reciben demasiadas al mismo tiempo. Esto provoca que los tiempos de respuesta percibidos por los clientes que ejecutan las consultas se vean afectados, sobre todo porque algunas de estas consultas necesitan grandes cantidades de recursos para ser procesadas. Todos estos motores tienen un optimizador de consultas interno que propone un plan de ejecución de consultas supuestamente óptimo, sin embargo, esta es una tarea difícil ya que puede haber miles de posibles planes de consulta a considerar y el optimizador puede no elegir el mejor. En dependencia de los recursos computacionales disponibles es posible implementar también arquitecturas más complejas como réplicas y balances de carga, o incluso nuevos conceptos “Self-Driving Database Management Systems”. Sin embargo, todos estos mecanismos dependen de buenos estimadores de la latencia de ejecución de las consultas. Hasta donde sabemos, en general, los estimadores de latencia para consultas SPARQL se basan en heurísticas sobre información estadística de las bases de datos. Otros técnicas como el uso de Support Vector Machine han mejorado las predicciones. En esta propuesta se utilizan redes neuronales profundas para la creación de un estimador de latencias de consultas SPARQL que supera los resultados obtenidos en técnicas anteriores y que puede servir como base de apoyo para la construcción de técnicas de optimización más avanzadas. El estimador fue evaluado en bases de datos sintéticas y reales. Los resultados muestran que el desempeño de redes neuronales profundas supera las propuestas anteriores en el contexto de la predicción de latencia en consultas SPARQL.