Professor Xiao Hu, and her collaborators Mahmoud Abo Khamis, Senior Computer Scientist at RelationalAI, and Dan Suciu, Professor of Computer Science and Engineering at the University of Washington, have received a at the 2025 ACM SIGMOD/PODS International Conference on Management of Data.
Their paper, , introduces a new and unified framework for determining how efficiently any Boolean conjunctive query can be answered using fast matrix multiplication techniques.
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.
鈥淐ongratulations to Xiao and her colleagues on winning a Distinguished Paper Award,鈥 said Raouf Boutaba, University Professor and Director of the Cheriton School of Computer Science. 鈥淭hat this is Xiao鈥檚 second paper to receive such a recognition at PODS 2025 is a remarkable achievement and speaks volumes about her significant theoretical contributions to the database research community.鈥澛
Professor 鈥檚 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.
About this award-winning research
A fundamental question in database theory is the computational complexity of answering Boolean conjunctive queries, returning true or false based on whether specific conditions are met within a database. This class of queries form the backbone of many database SQL queries. The classic graph pattern detection problem, which detects whether a given sub-graph pattern exists in a graph, is a special class of Boolean conjunctive queries. As the time complexity of any algorithm depends on the size of the database, researchers strive to answer such queries as quickly as possible.
When limited to combinatorial algorithms, the best-known running times are determined by a structural property of the query, known as the submodular width. Yet for certain queries 鈥 most notably triangles, cycles, and cliques 鈥 researchers have derived faster, non-combinatorial algorithms that leverage fast matrix multiplication together with non-trivial data partitioning. To date, however, there has been no systematic method for deriving such algorithms for general Boolean conjunctive queries.
In their paper, Professor Hu and her co-authors introduce a unified, information-theoretic framework that fills the gap. They propose a stronger version called the 蠅-submodular width that captures both the query structure and the power of fast matrix multiplication. Moreover, they have given an algorithm whose time complexity exactly matches this new measure. Their framework not only recovers the best-known bounds for all classic graph queries but also yields novel, faster algorithms for the large remaining class of Boolean conjunctive queries.聽
To learn more about the research on which this article is based, please see . Mahmoud Abo Khamis, Xiao Hu, Dan Suciu. 2025. Proceedings of the ACM SIGMOD International Conference on Management of Data.