Kyle Deeds

Kyle Deeds

Assistant Professor of Computer Science, Boston University

Publications

CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations

Published in PACMMOD (SIGMOD) 2026

CorrBound improves on the LPBound paper by incorporating intra- and inter-correlation statistics into the cardinality bound.

Recommended citation: Mayer, C., Zhang, H., Abo Khamis, M., Deeds, K., Olteanu, D., & Suciu, D. (2026). CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations. Proceedings of the ACM on Management of Data, 4(1), Article 19, 1-27. https://doi.org/10.1145/3786633
Download Paper

GovScape: A Public Multimodal Search System for 70 Million Pages of Government PDFs

Published in ACL 2026 (System Demonstrations)

GovScape is a public search system supporting metadata, text, semantic, and visual search across roughly 10 million federal government PDFs from the 2020 End of Term web crawl.

Recommended citation: Huang, Y.-H., Gong, C., Shaji, S., Yan, A. R., Harka, L., Du, A., Gopal, A. S., Klein, S. J., Shen, S. Z., Phillips, M. E., Owens, T., Deeds, K., & Lee, B. C. G. (2026). GovScape: A Public Multimodal Search System for 70 Million Pages of Government PDFs. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 3: System Demonstrations), 231-241. https://doi.org/10.18653/v1/2026.acl-demo.23
Download Paper

Degree Sequence Bounds

Published in ACM Transactions on Database Systems (TODS) 2025

This is the journal version of our ICDT 2023 paper, extending the degree sequence bound for join cardinality estimation with a full treatment of the underlying theory and algorithms.

Recommended citation: Deeds, K., Suciu, D., Balazinska, M., & Cai, W. (2025). Degree Sequence Bounds. ACM Transactions on Database Systems, 51(1), Article 4, 1-27. https://doi.org/10.1145/3716378
Download Paper

The Space-Time Complexity of Sum-Product Queries

Published in PODS 2026

This paper studies the combined space and time complexity of evaluating conjunctive and sum-product queries, giving algorithms that use asymptotically less space than prior approaches.

Recommended citation: Deeds, K., Merkl, T. C., Pichler, R., & Suciu, D. (2025). The Space-Time Complexity of Sum-Product Queries. Proceedings of the ACM on Management of Data, 3(5), Article 283, 1-21. https://doi.org/10.1145/3767719
Download Paper

Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins (Best Paper & Best Student Paper)

Published in ICDT 2025

This paper proposes a new statistic on relations that can be used to produce asymptotically tighter bounds on output size and runtime.

Recommended citation: Kyle Deeds and Timo Camillo Merkl. Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 17:1-17:18
Download Paper

Galley: Modern Query Optimization for Sparse Tensor Programs

Published in SIGMOD 2025

This applies database theory and compiler techniques to optimize sparse tensor programs.

Recommended citation: Kyle Deeds, Willow Ahrens, Magda Balazinska, and Dan Suciu. 2025. Galley: Modern Query Optimization for Sparse Tensor Programs. Proc. ACM Manag. Data 3, 3 (SIGMOD), Article 164 (June 2025), 24 pages. https://doi.org/10.1145/3725301
Download Paper

COLOR: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation

Published in PVLDB 2025

This work builds on the concept of stable colorings in graph theory and applies it to produce accurate, efficient cardinality estimates in graph databases.

Recommended citation: Kyle Deeds, Diandre Sabale, Moe Kayali, and Dan Suciu. Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation. PVLDB, 18(2): 130 - 143, 2024. doi:10.14778/3705829.3705834
Download Paper

Finch: Sparse and Structured Array Programming with Control Flow

Published in OOPSLA 2025

Finch is a compiler for sparse and structured array programs which jointly takes advantage of data and program structure to produce highly efficient code.

Recommended citation: Willow Ahrens, Teodoro Fields Collin, Radha Patel, Kyle Deeds, Changwan Hong, and Saman Amarasinghe. 2025. Finch: Sparse and Structured Tensor Programming with Control Flow. Proc. ACM Program. Lang. 9, OOPSLA1, Article 117 (April 2025), 31 pages. https://doi.org/10.1145/3720473." .
Download Paper

SafeBound: A Practical System for Generating Cardinality Bounds

Published in PACMMOD 2023

This project uses the degree sequence bounds that we proved previously, and incorporates them into a practical cardinality estimation framework.

Recommended citation: Deeds, K., Suciu, D., & Balazinska, M. (2022). SafeBound: A Practical System for Generating Cardinality Bounds. arXiv preprint arXiv:2211.09864.
Download Paper

Degree Sequence Bound for Join Cardinality Estimation

Published in ICDT 2023

This paper proves new bounds on the size of conjunctive queries based on the degree sequence statistic.

Recommended citation: Deeds, K., Suciu, D., Balazinska, M., & Cai, W. (2022). Degree sequence bound for join cardinality estimation. arXiv preprint arXiv:2201.04166.
Download Paper

Stacked Filters: Learning to Filter By Structure

Published in PVLDB 2020

This project improves on classical filter structures (e.g. Bloom Filters) by incorporating additional information about the distribution of negative elements.

Recommended citation: Deeds, K., Hentschel, B., & Idreos, S. (2020). Stacked filters: learning to filter by structure. Proceedings of the VLDB Endowment, 14(4), 600-612.
Download Paper

A Fast Filtering Algorithm for Massive Context-free Grammars

Published in ACM Southeast 2020

This paper presents a novel algorithm for efficiently pre-filtering rules to improve the parsing of massive context-free grammars.

Recommended citation: Dohmann, Jeremy, and Kyle Deeds. "A Fast Filtering Algorithm for Massive Context-free Grammars." Proceedings of the 2020 ACM Southeast Conference. 2020.
Download Paper