University of Wisconsin–Madison

Paris Koutris’ award-winning research addresses the “fundamental problem” of database theory

By Rachel Robey At the 2023 and 2024 Symposiums on Principles of Database Systems, Koutris received a string of awards for his groundbreaking research on join processing.

Professor Paris Koutris

At any given moment, the average smartphone is running dozens of invisible and remote databases, each one storing and fetching data to ensure seamless functionality across the device. Now scale this up to the organizational level—a bank, government, corporation, or university, for example—and the number, complexity, and stakes of those databases are increased exponentially. Across the world, they’re essential to just about everything our society takes for granted: tracking financial transactions, accessing library materials, storing social security information, managing voter registration, and so on—endlessly. “In short, they’re everywhere,” says Professor Paris Koutris, an expert in data management. “Databases are how we organize all our important information. My work introduces algorithmic frameworks for making them actionable, so that we can retrieve and use the information stored within a database meaningfully and easily.” Recently, Koutris received a series of awards on papers addressing what he describes as the “fundamental problem” in databases and database theory: computing joins. In addition to the accolades presented at the “the premier international conference on the theoretical aspects of database systems,” the results from Koutris’ research are also starting to draw interest from industry. Groundbreaking work receives string of awards Over the last two years, Koutris has achieved a series of Distinguished Paper Awards for his work on join processing. These operations allow for information retrieval across tables within a database, effectively establishing relationships between the various kinds of stored data.   “Receiving these awards is incredibly gratifying,” he says. “I’m grateful to my research group, the Database Systems Group, and my collaborators and students who have made this work possible.” Three of these awards were conferred at the 2024 Symposium on Principles of Database Systems (PODS):
And a fourth was conferred at the 2023 PODS conference: “Some of these introduce improved algorithms that we prove are doing joins more efficiently,” explains Koutris. “Some of the other work is on lower bounds, meaning we prove that our method is the best possible algorithm.”  To prove your method to be the best, you must first define “best” and then restrict the computation or method in some way. “In general, this is very hard to do,” continues Koutris. “Yet under some restrictions, we proved our algorithms are optimal. Otherwise, we showed what steps one must take in order to get to the optimal.” From theory to practice While most of the algorithms are theoretical, Koutris currently has a collaboration with CS Professor Xiangyao Yu, an expert in database systems and 2024 Sloan Fellow, that applies some of those ideas in service of a more practical algorithm. “Our new approach, called predicate transfer, proposes a novel way to implement a classic join algorithm that so far has been mostly theoretical. It is a great example of how one can bring theory to practice,” says Koutris. “There’s also a lot of enthusiasm from industry, where some people are trying to implement it in their systems.” As of now, it’s been about one year since Koutris and Yu’s algorithm was introduced—not very long in the world of databases.  “Databases don’t move as fast as machine learning, for example. There are systems that have been developed for 30 years, so it’s hard to suddenly introduce this new feature,” says Koutris. “But, you know, there’s been interest. So we’ll see what impact it will have.”