热点大瓜

By Elizabeth Egan 

The award recognizes a paper that was published in the PODS proceedings 10 years prior that has had the most impact in terms of research, methodology or transfer to practice over the previous decade.  

Rudra and his co-authors, Hung Ngo, past professor in the Department of Computer Science and Engineering and vice president of research for RelationalAI, Mahmoud Abo Khamis, a computer scientist at RelationalAI, and Christopher Ré, professor in Stanford University’s Department of Computer Science, are recognized for the lasting impacts of their paper, “Joins via Geometric Resolutions: Worst-case and Beyond.”

“My collaborations with Hung, Mahmoud and Chris on our series of join work has been some of the most intellectually satisfying research I have done in my career,” said Rudra, who will also serve as inaugural department chair in the . “It feels special (and humbling!) that this series of work has been recognized with two PODS test of time awards.”

Rudra said that the 2015 paper came as a “middle” step in a series of collaborations with Ngo, Abo Khamis and Ré that was focused on designing new algorithms to compute the relational join operator, the most basic operation that a database system performs over and over.

The team introduced a novel worst-case optimal relational join algorithm that generalized several worst-case optimal algorithms within a unifying geometric framework that connects to logical resolution. These algorithms are crucial for ensuring strong performance in modern relational and graph database systems, which are needed to process complex queries with numerous joins.

Over the past decade, the paper has influenced multiple subsequent research directions, including functional aggregate queries, tensor computations, triangle listing, clustering, and high-dimensional data analysis, according to the award citation.

“In my mind the main contribution of the paper is the geometric view of looking at the join problem,” said Rudra. “I was under the impression that people in the community did not really appreciate this work (there was not a lot of follow up work e.g.), So it was a very pleasant surprise that people actually thought this work was good enough to be given this award!”

Ngo noted that the team was interested in studying one of the most important problems in database query processing, how to answer join queries faster. Ngo added that this problem was not widely understood despite over 40 years of research.

“This paper was in the middle of a series of papers that we wrote together at that time, delving deeper into these two questions: what is the right model for an "optimal" join algorithm, and how to come up with such an optimal join algorithm,” said Ngo. “We are very happy that the community recognized the importance of the problem and the issues we were and still are passionate about.”

Abo Khamis earned his PhD in computer science and engineering from the University at Buffalo in 2016. “I was very lucky to be part of the team stumbling upon this line of work back when I was doing my PhD at UB,” said Abo Khamis. “We continued in the following years to investigate connections between database join queries and other areas of computer science, most notably information theory. These efforts culminated later in the “” algorithm, which remains the asymptotically fastest join algorithm known to date.”

Rudra, Ngo and Ré also received the Test of Time Award in 2022 for their 2012 PODS paper titled, “Worst-case optimal join algorithms.”

The research team will be officially presented with the award at the Special Interest Group on Management of Data/PODS 2025 award ceremony during the International Conference on Management of Data in Berlin that will take place in late June.