Professor Xiao Hu has received a Best Paper Award at the 2025 ACM SIGMOD/PODS International Conference on Management of Data for her research on optimizing join-aggregate queries. Her paper, Output-Optimal Algorithms for Join-Aggregate Queries, addresses a long-standing open problem in database theory, establishing output-optimal bounds on the efficiency with which such queries can be processed.
The ACM SIGMOD/PODS conference is the premier international forum for database researchers, practitioners and developers. Organized jointly by the ACM Special Interest Group on Management of Data (SIGMOD) and the ACM Symposium on Principles of Database Systems (PODS), the conference brings together leading experts to share research, discuss innovative tools and techniques, and exchange insights on data management.
“Congratulations to Xiao on winning a Best Paper Award at SIGMOD/PODS,” said Raouf Boutaba, University Professor and Director of the Cheriton School of Computer Science. “Her paper solves a long-standing open question in database theory by proving tight upper and lower bounds for join-aggregate queries, a result that advances theoretical understanding and allows for more efficient query processing in modern data systems.”
Professor Xiao Hu’s research aims to equip modern data systems with efficient query processing algorithms that offer scalability, low latency, and privacy guarantees across emerging data applications and computing architectures.
Before joining the Cheriton School of Computer Science, Professor Hu was a Research Fellow at the Simons Institute for the Theory of Computing, a Visiting Faculty Scholar in Google Research, and a Postdoctoral Researcher at Duke University. She received her PhD from HKUST in 2019 and BE from Tsinghua University in 2014.
About this award-winning research
Join-aggregate queries defined over commutative semirings capture a broad class of algorithmic problems, including graph pattern matching, graph colourability, matrix multiplication, and constraint satisfaction problems. A foundational result in evaluating join-aggregate queries over commutative semirings is the Yannakakis algorithm, introduced in 1981.
For a special class of queries known as free-connex acyclic queries, the Yannakakis algorithm runs in time proportional to the size of the input data plus the size of the final query result. This runtime was thought to be optimal in terms of output size, and in the past 40 years no improvement in its complexity has been discovered.
In her award-winning paper, Professor Hu presents a new result; namely, she establishes both a matching upper and lower bound for computing general acyclic join-aggregate queries using semiring algorithms. Importantly, this is the first improvement of this algorithm and has proved that it is output-optimal among all combinatorial algorithms.
These results have significant practical implications. With the advent of advanced computing architectures, output-optimal algorithms developed by Professor Hu can substantially enhance the performance and scalability of modern database systems.
To learn more about the research on which this article is based, please see Output-Optimal Algorithms for Join-Aggregate Queries. Xiao Hu. 2025. Proceedings of the ACM SIGMOD International Conference on Management of Data.