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). https://arxiv.org/pdf/2405.06767
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). https://arxiv.org/pdf/2404.16730
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. https://arxiv.org/pdf/2211.09864
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. https://arxiv.org/pdf/2201.04166.pdf
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. http://vldb.org/pvldb/vol14/p600-hentschel.pdf
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. https://dl.acm.org/doi/pdf/10.1145/3374135.3385266