Published in Arxiv
This applies database theory and compiler techniques to optimize sparse tensor programs.
Recommended citation: Deeds, K., Ahrens, W., Balazinska, M., & Suciu, D. (2025). Galley: Modern Query Optimization for Sparse Tensor Programs. Arxiv.
Download Paper
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: Deeds, Kyle, et al. "Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation." arXiv preprint arXiv:2405.06767 (2024).
Download Paper
Published in Arxiv
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: Ahrens, Willow, Teodoro Fields Collin, Radha Patel, Kyle Deeds, Changwan Hong, and Saman Amarasinghe. "Finch: Sparse and Structured Array Programming with Control Flow." arXiv preprint arXiv:2404.16730 (2024).
Download Paper
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
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
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
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