Workshop GRADES-NDA: IMFD Team Awarded for Strategy that Speeds Up Queries in Graph Databases
Researchers Diego Arroyuelo (DCC UC) and Gonzalo Navarro (DCC UChile), together with the UTFSM PhD student, co-advised by Arroyuelo, José M. Cazorla, received the Best Paper Award at GRADES-NDA 2026 —a workshop associated with SIGMOD/PODS— for a technique that makes Qdags, a graph data structure published by IMFD researchers in 2022, much faster.
A team of researchers from the Millennium Institute for Foundational Research on Data (IMFD) received the Best Paper Award at GRADES-NDA 2026, an international workshop that is part of SIGMOD/PODS, one of the world’s most important database conferences. The award went to the paper “Boosting Graph Joins and Matrix Multiplications in Little Space” (2026), written by Diego Arroyuelo, faculty member of the Computer Science Department at Universidad Católica de Chile; José M. Cazorla, PhD student in the Informatics Department at Universidad Técnica Federico Santa María; and Gonzalo Navarro, faculty member of the Computer Science Department at Universidad de Chile.
The paper was one of 9 accepted out of a total of 22 submitted to the workshop, and was chosen among all of them as the winner of the Best Paper Award.
A line of research the IMFD has been building for years
For Diego Arroyuelo the award recognizes years of research within IMFD: “Receiving this award is very important for our group, since it validates a line of research we have been developing for more than 5 years. It gives us visibility in one of the main international forums on graph databases and confirms that the problems we are studying, and the solutions we are proposing, are relevant to the international community”.
José M. Cazorla also describes it as a collective achievement: “I see it as the result of joint work between three IMFD institutions: UTFSM, UC, and Universidad de Chile, born out of an internship I did during my PhD. As a student, receiving recognition of this level at a workshop associated with SIGMOD/PODS is a very important validation and a huge motivation to keep deepening this line of research“.
The award-winning paper builds on the earlier publication “Optimal Joins Using Compressed Quadtrees” (2022), developed by Arroyuelo, Navarro, and two other IMFD researchers, Juan L. Reutter and Javiel Rojas-Ledesma. There, the authors presented Qdags (or compressed quadtrees), a structure that represents graphs in an extremely compact way (around 5 bytes per connection, compared to the more than 100 bytes used by classic systems) to resolve queries on graph databases using very little space.
“The problem is that, despite that space efficiency, response time still depended exponentially on the number of variables in the query: with 3 variables or fewer they performed very well, but from 4 onward the times shot up and stopped being a competitive option,” explains Cazorla.
Pre-joining, the solution to the Qdags problem
The solution that Arroyuelo, Cazorla, and Navarro proposed in the paper submitted to GRADES-NDA 2026 is called pre-joining, and consists of splitting a large query into smaller subqueries —with fewer variables— that Qdags can indeed resolve quickly.
The result of those subqueries is then used as a filter to narrow the search in the full query, drastically reducing response time without losing the space guarantees of Qdags. “In the best cases, queries with pre-joining are resolved up to 2,000 times faster than with the original Qdags, using just a bit more space (from 5 to just over 6 bytes per connection),” explains Cazorla.
Gonzalo Navarro, faculty member of the DCC at Universidad de Chile and co-author of both the original Qdags and this new strategy, explains that the trick lies in anticipating: “We showed that this additional filter can greatly reduce the times of the final query because it helps avoid unnecessary paths. The key is that pre-joining precomputes which combinations have a chance of producing results and which ones do not need to be checked”.
Regarding next steps, Arroyuelo reveals that the team is already working on an extended version of the paper: “The next step is to prepare a final version to submit to a specialized journal in the field. There, we will seek to extend these results to other types of queries on graph databases, such as RPQs (regular path queries), complementing a line of research our group has already been developing in previous work”.
Sources: Original interviews with Diego Arroyuelo and José M. Cazorla, GRADES-NDA 2026 and Comunicaciones DDC.
