Rudra and team win third Test of Time Award in five years

By Peter Murphy

Atri Rudra, the inaugural chair and professor in the Department of AI and Society, is co-author of this study and two others that have received the Association for Computing Machinery Special Interest Group on Management of Data (ACM SIGMOD) Symposium on Principles of Database Systems (PODS) Alberto O. Mendelzon Test-of-Time Award. The award recognizes a small number of papers in the PODS proceeding 10 years prior that had the most impact in terms of research, methodology or transfer to practice over the intervening decade.

Rudra and his collaborators have won this award in three of the last five years. According to him, the entire arc of this research centers around databases, and the first paper — recognized in 2022 — and this latest paper are similar.

“The first Test-of-Time Award was for our work with this join operator. In terms of tables and spreadsheets, there is this underlying master table, but you only get partial views of it. You see a few columns here or there, but you want to combine all of these partial views into one consistent view across all the columns. This is the join operator,” Rudra said.

Examining the overlapping attributes in multiple databases allows researchers to get the best view of the full set of data. Rudra and the co-authors of “Worst-case optimal join algorithms,” published in PODS 2012, developed an algorithm for the join operation, which guaranteed more efficient performance even in the most difficult scenarios.

In 2015, Rudra and his co-authors, Hung Ngo, past professor in the Department of Computer Science and Engineering and now vice president of research for RelationalAI; Mahmoud Abo Khamis, a UB computer science and engineering PhD alum and computer scientist at RelationalAI; and Christopher Ré, professor in Stanford University’s Department of Computer Science, expanded on this problem in their paper “Joins via Geometric Resolutions: Worst-case and Beyond.” The team of researchers used structures and geometry in tables to introduce new functions and capabilities, allowing researchers to optimize the process and timing behind finding the data in the underlying master table. The researchers gained more control over when and how data is retrieved instead of treating every table of the same size equivalently.  

The latest paper to be recognized, “FAQ: Questions Asked Frequently,” is related to the first paper. According to Rudra, the algorithm they developed initially to solve the join problem was powerful enough to solve many of the frequently asked questions across databases, data analysis and machine learning, reasoning, and several other contexts.

Rudra and the other co-authors realized that the algorithm they developed to solve the join problem works over many definitions of addition and multiplication.

“FAQ, or Functional Aggregate Queries, is a unified query language that can be used to express a wide variety of problems in different domains, including databases, linear algebra, and probabilistic graphical models, among others,” says Abo Khamis, who is also a UB Department of Computer Science and Engineering alum. “Prior to FAQ, researchers in different areas used to develop a different specialized algorithm for each of these problems. FAQ enables us to unify these problems in one ‘meta-problem,’ and subsequently develop one ‘meta-algorithm.’ Unifying problems enable us to develop a unified solution.”

Rudra has brought some of these concepts into his later work with structured matrices and algebraic structures with applications in deep learning. He joined UB in 2007 and was named Katherine Johnson Chair in Artificial Intelligence in 2023. His research interests include structure linear algebra with applications in deep learning, society and computing, coding theory, and database algorithms.