18 Junio 2026

El académico UC e investigador del Instituto Milenio Fundamentos de los datos (IMFD), Diego Arroyuelo, fue distinguido con “Best Paper Award en GRADES-NDA 2026″ por el artículo “Boosting Graph Joins and Matrix Multiplications in Little Space”, desarrollado junto a José M. Cazorla (UTFSM) y Gonzalo Navarro (UChile). GRADES-NDA es un workshop internacional sobre gestión y análisis de grafos a gran escala, y es parte de ACM SIGMOD/PODS, una de las principales conferencias internacionales en el área de bases de datos. ¿De qué trata “Boosting Graph Joins and Matrix Multiplications in Little Space“?El paper presenta una técnica llamada prejoining para acelerar consultas en bases de datos de grafos, específicamente mejorando el rendimiento de las estructuras de datos llamadas qdags, que son representaciones muy compactas de grafos. Problema que resuelvenLos qdags son extremadamente eficientes en espacio (menos de 5 bytes por arista, versus los más de 100 bytes de sistemas clásicos), pero su tiempo de consulta crece exponencialmente con el número de variables en la consulta, volviéndose poco prácticos para consultas con 4 o más variables. Idea central: PrejoiningEn vez de resolver un join de alta dimensión directamente, la técnica divide el problema: primero resuelve un join sobre un subconjunto de atributos (más barato), y luego usa ese resultado intermedio como filtro en el join final. Esto mantiene la optimalidad en el peor caso mientras reduce drásticamente el tiempo práctico. Estrategias exploradasProponen varias variantes de prejoining, las principales siendo one-shot, leapfrog, kernel y weak kernel, cada una adecuada a distintas topologías de consulta. Resultados