Xiao Hu

Assistant Professor
Cheriton School of Computer Science
University of Waterloo
Email: xiaohu@uwaterloo.ca
Room 3353, Davis Center

I am seeking highly motivated Ph.D. and MMath students for fully funded positions starting in 2026. If you are interested in working with me, please send me an email and mention my name as a potential advisor in your application.

Efficient query engines lie at the heart of modern data-intensive applications, such as real-time analytics, ML pipelines, privacy-preserving services, knowledge-graph exploration, and beyond. My group work on new algorithms and complexity results for database query processing, so that next-generation data systems can run faster, use fewer resources, and adapt optimally to new constraints. Some of our recent works include join-aggregate query processing [PODS25], sampling/clustering over relational data [SIGMOD18, SIGMOD24, PODS25], leveraging fast matrix multiplication to improve decades-old complexity barriers [PODS24, PODS25]. These algorithmic insights naturally extend beyond classic relational settings into high-dimensional, unstructured, and multimodal domains: algorithms for hybrid sparse/dense vector search, machine learning over representative samples from query results, and automatically inducing structures from unstructured multimodal data for efficient querying. I am looking for students who want to push both the theoretical foundations and these emerging areas forward.

Publications

• Xiao Hu. "Output-Optimal Algorithms for Join-Aggregate Queries." ACM Symposium on Principles of Database Systems (PODS), June 2025. pdf arxiv (Best Paper Award) (invited to JACM)

• Mahmoud Abo-Khamis, Xiao Hu, and Dan Suciu. "Fast Matrix Multiplication meets the Submodular Width." ACM Symposium on Principles of Database Systems (PODS), June 2025. pdf arxiv (Distinguished Paper Award) (invited to TheoretiCS)

• Xiao Hu and Qichen Wang. "Towards Update-Dependent Analysis of Query Maintenance." ACM Symposium on Principles of Database Systems (PODS), June 2025. pdf

• Aryan Esmailpour, Boris Glavic, Xiao Hu, and Stavros Sintos. "Smallest Synthetic Witnesses for Conjunctive Queries." ACM Symposium on Principles of Database Systems (PODS), June 2025. pdf

• Pankaj K. Agarwal, Aryan Esmailpour, Xiao Hu, Stavros Sintos, and Jun Yang. "Computing A Well-Representative Summary of Conjunctive Query Results." ACM Symposium on Principles of Database Systems (PODS), June 2025. pdf

• Xiao Hu and Zhiang Wu. "Oblivious Optimal Algorithms for Multi-way Joins." International Conference on Database Theory (ICDT), March 2025. pdf arxiv

• Binyang Dai, Xiao Hu, and Ke Yi. "Reservoir Sampling over Joins." SIGMOD Record, March 2025 (Vol. 54, No. 1). (invited) pdf

• Xiao Hu. "Fast Matrix Multiplication for Query Processing." ACM Symposium on Principles of Database Systems (PODS), June 2024. pdf

• Xiao Hu and Paraschos Koutris. "Topology-aware Parallel Joins." ACM Symposium on Principles of Database Systems (PODS), June 2024. pdf (Distinguished Paper Award) (invited to TODS)

• Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, and Jun Yang. "Reporting Durable Patterns in Temporal Graphs Efficiently." ACM Symposium on Principles of Database Systems (PODS), June 2024. pdf

• Binyang Dai, Xiao Hu, and Ke Yi. "Reservoir Sampling over Joins." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2024. pdf arxiv (Best Paper Award Honorable Mention) (SIGMOD Research Highlight Award) (invited to TODS)

• Zichen Zhu, Xiao Hu, and Manos Athanassoulis. "NOCAP: Near-Optimal Correlation-Aware Partitioning Joins." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2024. pdf arxiv

• Xiao Hu and Stavros Sintos. "Finding Smallest Witness for Conjunctive Query." International Conference on Database Theory (ICDT), March 2024. pdf arxiv (Best Paper Award) (invited to TODS)

• Xiao Hu and Yufei Tao. "Parallel Acyclic Joins: Optimal Algorithms and Cyclicity Separation." Journal of the ACM (JACM), Vol. 71, Issue 1, Article No. 6, Feb 2024. pdf

• Badih Ghazi, Xiao Hu, Ravi Kumar, and Pasin Manurangsi. "On Differentially Private Sampling from Gaussian and Product Distributions." Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS), Dec 2023. pdf arxiv

• Qichen Wang, Xiao Hu, Binyang Dai, and Ke Yi. "Change Propagations Without Joins." International Conference on Very Large Data Bases (VLDB), Aug 2023. pdf

• Shaleen Deep, Xiao Hu, and Paraschos Koutris. "General Space-Time Tradeoffs via Relational Queries." Algorithms and Data Structures Symposium (WADS), July 2023. arxiv

• Badih Ghazi, Xiao Hu, Ravi Kumar, and Pasin Manurangsi. "Differentially Private Data Release over Multiple Tables." ACM Symposium on Principles of Database Systems (PODS), June 2023. pdf

• Xiao Hu and Qichen Wang. "Computing the Difference of Conjunctive Queries Efficiently." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2023. pdf

• Shaleen Deep, Xiao Hu, and Paraschos Koutris. "Ranked Enumeration of Join Queries with Projections." International Conference on Very Large Data Bases (VLDB), Sept 2022. pdf

• Xiao Hu, Yuxi Liu, Haibo Xiu, Pankaj K. Agarwal, Debmalya Panigrahi, Sudeepa Roy, and Jun Yang. "Selectivity Functions of Range Queries are Learnable." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2022. pdf

• Xiao Hu, Stavros Sintos, Junyang Gao, Pankaj K. Agarwal, and Jun Yang. "Computing Complex Temporal Join Queries Efficiently." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2022. pdf

• Xiao Hu, Shouzhuo Sun, Shweta Patwa, Debmalya Panigrahi, and Sudeepa Roy. "Aggregated Deletion Propagation for Counting Conjunctive Query Answers." International Conference on Very Large Data Bases (VLDB), Aug 2021. pdf arxiv

• Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, and Jun Yang. "Dynamic Enumeration of Similarity Joins." International Colloquium on Automata, Languages and Programming (ICALP), July 2021. pdf arxiv

• Xiao Hu. "Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins." ACM Symposium on Principles of Database Systems (PODS), June 2021. pdf

• Xiao Hu, Paraschos Koutris, and Spyros Blanas. "Algorithms for a Topology-aware Massively Parallel Computation Model." ACM Symposium on Principles of Database Systems (PODS), June 2021. pdf arxiv

• Shaleen Deep, Xiao Hu, and Paraschos Koutris. "Enumeration Algorithms for Conjunctive Queries with Projection." International Conference on Database Theory (ICDT), March 2021. pdf arxiv (invited to LMCS)

• Xiao Hu and Ke Yi. "Massively Parallel Join Algorithms." SIGMOD Record, 49(3), Sept 2020. (invited) pdf

• Xiao Hu and Ke Yi. "Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries." ACM Symposium on Principles of Database Systems (PODS), June 2020. pdf

• Shaleen Deep, Xiao Hu, and Paraschos Koutris. "Fast Join Project Query Evaluation using Matrix Multiplication." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2020. pdf arxiv

• Xiao Hu, Ke Yi, and Yufei Tao. "Output-optimal Massively Parallel Algorithms for Similarity Joins." ACM Transactions on Database Systems (TODS), 44(2):6, Apr 2019. (invited) pdf

• Xiao Hu and Ke Yi. "Instance and Output Optimal Parallel Algorithms for Acyclic Joins." ACM Symposium on Principles of Database Systems (PODS), June 2019. pdf arxiv

• Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. "Random Sampling over Joins Revisited." ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2018. pdf

• Xiao Hu, Yufei Tao, and Ke Yi. "Output-optimal Parallel Algorithms for Similarity Joins." ACM Symposium on Principles of Database Systems (PODS), May 2017. pdf (invited to TODS)

• Xiao Hu and Ke Yi. "Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins." ACM Symposium on Principles of Database Systems (PODS), June 2016. pdf