Kyle Deeds

Kyle Deeds

PhD Student at the University of Washington

Publications

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