Sitemap
A list of all the posts and pages found on the site. For you robots out there, there is an XML version available for digesting as well.
Pages
Kyle Deeds' Personal Website
About me
Posts
Blog Post number 4
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 3
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 2
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 1
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
publications
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
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
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
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
The Case for Cardinality Bounds: Principled Conservatism in Query Optimization
Published in ACM SIGMOD Blog
This blog post discusses the dual approaches for conservative cardinality estimation in SafeBound and FactorJoin.
Recommended citation: Deeds, K., & Wu. Z., The Case for Cardinality Bounds: Principled Conservatism in Query Optimization. Sept. 9th 2023. ACM SIGMOD Blog.
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
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
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
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
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
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
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
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