GRADES-NDA Workshop: IMFD Team Honored for Strategy That Speeds Up Queries in Graph Databases

Researchers Diego Arroyuelo (DCC UC) and Gonzalo Navarro (DCC UChile), along with the UTFSM doctoral student, co-advised by Arroyuelo, José M. Cazorla,won the Best Paper Award at GRADES-NDA 2026—a workshop associated with SIGMOD/PODS—for a technique that significantly speeds up Qdags, a graph data structure published by IMFD researchers in 2022.

A team of researchers from Millennium Institute Foundational Research on Data IMFD) won the Best Paper Award at GRADES-NDA 2026, an international workshop that is part of SIGMOD/PODS, one of the world’s leading conferences on databases. The award was given for the paper “Boosting Graph Joins and Matrix Multiplications in Little Space” (2026), written by Diego Arroyuelo, a faculty member in the Department of Computer Science at the Catholic University of Chile; José M. Cazorla, a Ph.D. student in the Department of Computer Science at the Federico Santa María Technical University; and Gonzalo Navarro, a faculty member in the Department of Computer Science at the University of Chile.

The paper was one of nine accepted out of a total of 22 submitted to the workshop, and was selected from among them all as the winner of the Best Paper Award.

An approach that the IMFD has been developing for years

For Diego Arroyuelo, the award recognizes years of research within the IMFD: “Receiving this award is very important for our group, as it validates a line of research we have been pursuing for more than five years. It gives us visibility in one of the world’s leading 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 a collaborative effort among three IMFD institutions— UTFSM, UC, and the University of Chile— that originated from an internship I completed during my doctoral studies. As a student, receiving this level of recognition at a workshop associated with SIGMOD/PODS is a very important validation and a tremendous motivation to continue exploring this line of research.”

The award-winning paper builds on the previous publication “Optimal Joins Using Compressed Quadtrees” (2022), developed by Arroyuelo, Navarro, and two other IMFD researchers, Juan . Reutter and Javiel Rojas-Ledesma. In that paper, the authors introduced Qdags (or compressed quadtrees), a structure that represents graphs in an extremely compact manner (about 5 bytes per edge, compared to the more than 100 bytes used by classical systems) to resolve queries in graph databases using very little space.

“The problem is that, despite that efficiency in terms of space, response time continued to depend exponentially on the number of variables in the query: with three variables or fewer, they performed very well, but with four or more, response times skyrocketed and they were no longer a competitive option,” explains Cazorla.

Pre-joining: The Solution to the Qdag Problem

The solution proposed by Arroyuelo, Cazorla, and Navarro in their paper submitted to GRADES-NDA 2026 is called pre-joining, and it consists of dividing a large query into smaller subqueries—with fewer variables—that Qdags can indeed solve quickly.

The result of these subqueries is then used as a filter to narrow the search in the full query, drastically reducing response time without compromising the space guarantees of Qdags. “In the best-case scenarios, queries with pre-joining are resolved up to 2,000 times faster than with the original QDAGs, using only slightly more space (from 5 to just over 6 bytes per connection),” explains Cazorla.

Gonzalo Navarro, a researcher at the DCC at the University of Chile and co-author of both the original Qdags and this new strategy, explains that the trick lies in planning ahead: “We’ve shown that this additional filter can significantly reduce the time required for the final query because it helps avoid unnecessary paths. The key is that the pre-join precalculates which combinations are likely to yield results and which ones don’t need to be checked.”

Regarding the next steps, Arroyuelo notes that the team is already working on an expanded 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 in graph databases, suchas RPQs (path queries in graphs), building on a line of research that part of our group has already been developing in previous work.”

Sources: Original interviews with Diego Arroyuelo and José M. Cazorla, GRADES-NDA 2026, and DDC Communications.