Workshop GRADES-NDA: Premian a equipo IMFD por estrategia que acelera consultas en bases de datos de grafos
Los investigadores Diego Arroyuelo (DCC UC) y Gonzalo Navarro (DCC UChile), junto al estudiante de doctorado UTFSM, codirigido por Arroyuelo, José M. Cazorla, obtuvieron el Best Paper Award en GRADES-NDA 2026 —workshop asociado a SIGMOD/PODS— por una técnica que vuelve mucho más rápidos a los Qdags, una estructura de datos para grafos publicada por investigadores del IMFD en 2022.
Un equipo de investigadores del Instituto Milenio Fundamentos de los Datos (IMFD) obtuvo el Best Paper Award en GRADES-NDA 2026, workshop internacional que forma parte de SIGMOD/PODS, una de las conferencias más importantes del mundo en bases de datos. El reconocimiento fue para el artículo «Boosting Graph Joins and Matrix Multiplications in Little Space» (2026), escrito por Diego Arroyuelo, académico del Departamento de Ciencia de la Computación de la Universidad Católica de la Chile; José M. Cazorla, estudiante de doctorado del Departamento de Informática de la Universidad Técnica Federico Santa María; y Gonzalo Navarro, académico del Departamento de Ciencia de la Computación de la Universidad de Chile.
El trabajo fue uno de los 9 aceptados de un total de 22 enviados al workshop, y resultó elegido entre todos ellos como ganador del Best Paper Award.
Una línea que el IMFD viene construyendo hace años
Para Diego Arroyuelo el premio reconoce años de investigación dentro del IMFD: “Recibir este premio es muy importante para nuestro grupo, ya que es un respaldo a una línea que venimos desarrollando desde hace más de 5 años. Nos da visibilidad en uno de los principales foros mundiales de bases de datos de grafos y confirma que los problemas que estamos estudiando, y las soluciones que estamos proponiendo, son relevantes para la comunidad internacional”.
José M. Cazorla también lo describe como un logro colectivo: «Lo siento como el resultado de un trabajo conjunto entre tres instituciones del IMFD: la UTFSM, la UC y la Universidad de Chile, nacido de una pasantía que hice durante mi doctorado. Como estudiante, recibir un reconocimiento de este nivel en un workshop asociado a SIGMOD/PODS es una validación muy importante y una motivación enorme para seguir profundizando esta línea de investigación«.
El paper premiado retoma la publicación anterior “Optimal Joins Using Compressed Quadtrees» (2022), desarrollada por Arroyuelo, Navarro y otros dos investigadores del IMFD, Juan L. Reutter y Javiel Rojas-Ledesma. Allí los autores presentaron Qdags (o compressed quadtrees), una estructura que representa grafos de manera extremadamente compacta (alrededor de 5 bytes por conexión, frente a los más de 100 bytes que usan los sistemas clásicos) para resolver consultas en bases de datos de grafos usando muy poco espacio.
“El problema es que, pese a esa eficiencia en espacio, el tiempo de respuesta seguía dependiendo exponencialmente del número de variables de la consulta: con 3 variables o menos andaban muy bien, pero a partir de 4 los tiempos se disparaban y dejaban de ser una opción competitiva”, explica Cazorla.
Pre-joining, la solución al problema de los Qdags
La solución que propusieron Arroyuelo, Cazorla y Navarro en el paper postulado a GRADES-NDA 2026 se llama pre-joining, y consiste en dividir una consulta grande en subconsultas más pequeñas —con menos variables —que los Qdags sí pueden resolver con rapidez.
El resultado de esas subconsultas se usa después como un filtro para acotar la búsqueda en la consulta completa, reduciendo drásticamente el tiempo de respuesta sin perder las garantías de espacio de los Qdags. “En los mejores casos, las consultas con pre-joining se resuelven hasta 2.000 veces más rápido que con los Qdags originales, usando apenas un poco más de espacio (de 5 a poco más de 6 bytes por conexión)”, explica Cazorla.
Gonzalo Navarro, académico del DCC de la Universidad de Chile y coautor tanto de los Qdags originales como de esta nueva estrategia, explica que el truco está en anticiparse: “Mostramos que este filtro adicional puede reducir mucho los tiempos de la consulta final porque ayuda a evitar caminos innecesarios. La clave es que el pre-join precalcula qué combinaciones tienen chance de producir resultados y cuáles no es necesario revisar”.
Sobre los próximos pasos, Arroyuelo adelanta que el equipo ya trabaja en una versión extendida del paper: «El siguiente paso es preparar una versión final para enviarla a una revista especializada del área. Allí buscaremos extender estos resultados a otros tipos de consultas en bases de datos de grafos, como las RPQs (consultas de caminos en grafos), complementando una línea que parte de nuestro grupo ya ha venido desarrollando en trabajos anteriores».
Fuentes: Entrevistas propias a Diego Arroyuelo y José M. Cazorla, GRADES-NDA 2026 y Comunicaciones DDC.