"New complexity bounds for evaluation and containment of graph query languages", se titula la tesis de doctorado de Miguel Romero, presentada el 10 de agosto, que se enmarcó en el área de bases de datos de grafos, la cual ha ganado mucha relevancia hoy en día debido a aplicaciones como la Web Semántica o las redes sociales”, explicó Miguel Romero y agregó que “nuestro foco fue estudiar la complejidad de dos lenguajes fundamentales para grafos: las Unions of Conjunctive two-way Regular Path Queries (UC2RPQs) y las Regular Queries (RQs), las cuales han sido propuestas recientemente como una extensión natural de las UC2RPQs”.
Los aportes principales de este trabajo, guiado por el profesor Pablo Barceló, fueron “obtener nuevos algoritmos para el problema de evaluación y contención de estos lenguajes. En particular, definimos restricciones de UC2RPQs que se pueden evaluar más eficientemente que el caso general (evaluar UC2RPQs es NP-completo en general). El segundo aporte fue demostrar que la complejidad de contención (o implicancia) de RQs no es significativamente más alta que la del caso de las UC2RPQs. Esto último muestra que las RQs alcanzan un buen balance entre expresividad y complejidad”, explicó Miguel.
Miguel Romero es Ingeniero Civil en Matemáticas, Magíster en Computación (2011) y Doctor en Ciencias mención de la Computación de la Universidad de Chile (2016). Sus Líneas de Investigación son: Teoría de base de datos, Web Semántica, Lógica en Computación. Actualmente se encuentra realizando una estadía de investigación en el Simons Institute de la Universidad de Berkeley.
Resumen de tesis
En tanto, Héctor Ferrada presentó el 19 de agosto la investigación: “Compressed Indexes for Document Retrieval (DR)”, que es el área de investigación dentro de las Ciencias de la Computación que se encarga de la representación de colecciones de archivos de textos, con el fin de buscar/recuperar de forma eficiente los documentos que mejor satisfagan una información requerida en tiempo real. “Dentro de esta investigación, trabajamos en dos grandes áreas principales: en el diseño de índices comprimidos para recuperar documentos y en el diseño de estructuras sucintas usadas en DR”, comentó Héctor.
La investigación, guiada por el profesor Gonzalo Navarro, logró cumplir con sus objetivos, ya sea “ofrecemos índices para DR que mejoran en tiempo de respuesta y/o requerimientos de espacio soluciones del estado del arte y compiten a la par con las mejores soluciones existentes actualmente. Además iniciamos una línea de investigación para el diseño de índices comprimidos que entreguen soluciones aproximadas a los principales problemas de DR. Por último, damos soluciones para DR sobre índices Lempel-Ziv y ofrecemos también una solución alternativa al problema de Range Mnimun Query (RMQ)”, explicó.
Héctor es licenciado en Ciencias de la Computación y Analista Computacional Científico de la Universidad de Santiago de Chile (2005) y Doctor en Ciencias mención Computación (2016) de la Casa de Bello. Actualmente se encuentra haciendo un postdoctorado en Finlandia, en la Universidad de Helsinki en el grupo de Genome-scale Algorithmics.
Resumen de tesis
Finalmente, Roberto Konow con su trabajo de investigación presentado el 26 de septiembre “Compact Data Structures For Information Retrieval on Natural Language”, estudiaron, diseñaron e implementaron nuevas formas de poder almacenar y buscar información en lenguaje natural. “En especial, desarrollamos nuevas estructuras de datos compactas que permiten realizar búsquedas sobre colecciones gigantes, usando menos tiempo y menos espacio, lo que se traduce en una posible reducción de costos para empresas que manejan una gran cantidad de información”, explicó Roberto.
La investigación, guiada también por el profesor Gonzalo Navarro, se enfocó en el uso, diseño e implementación de estructuras de datos compactos para crear nuevos índices que sean más rápidos y consuman menos espacio. “Nuestra nueva estructura, llamada “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”, expresó Roberto.
Roberto es Ingeniero en Ciencias de la Computación y Telecomunicaciones, (2009) y Magíster en Ciencias de la Computación (2011) de la Universidad Diego portales. Doctor en Ciencias mención Computación (2016) de la Universidad de Chile, y actualmente se encuentra trabajando en eBay, en Silicon Valley USA, donde espera seguir trabajando por un tiempo y aplicando lo aprendido en el doctorado.
