Publications (9)
The Space-Time Complexity of Sum-Product Queries
Kyle Deeds, Timo Camillo Merkl, Reinhard Pichler +1
While extensive research on query evaluation has achieved consistent improvements in the time complexity of algorithms, the space complexity of query evaluation has been largely ig…
Degree Sequence Bound For Join Cardinality Estimation
Kyle Deeds, Dan Suciu, Magda Balazinska +1
Recent work has demonstrated the catastrophic effects of poor cardinality estimates on query processing time. In particular, underestimating query cardinality can result in overly…
Finch: Sparse and Structured Tensor Programming with Control Flow
Willow Ahrens, Teodoro Fields Collin, Radha Patel +3
From FORTRAN to NumPy, tensors have revolutionized how we express computation. However, tensors in these, and almost all prominent systems, can only handle dense rectilinear intege…
Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins
Kyle Deeds, Timo Camillo Merkl
In the last decade, various works have used statistics on relations to improve both the theory and practice of conjunctive query execution. Starting with the AGM bound which took a…
SafeBound: A Practical System for Generating Cardinality Bounds
Kyle Deeds, Dan Suciu, Magda Balazinska
Recent work has reemphasized the importance of cardinality estimates for query optimization. While new techniques have continuously improved in accuracy over time, they still gener…
Galley: Modern Query Optimization for Sparse Tensor Programs
Kyle Deeds, Willow Ahrens, Magda Balazinska +1
The tensor programming abstraction is a foundational paradigm which allows users to write high performance programs via a high-level imperative interface. Recent work on sparse ten…
Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation
Kyle Deeds, Diandre Sabale, Moe Kayali +1
Graph workloads pose a particularly challenging problem for query optimizers. They typically feature large queries made up of entirely many-to-many joins with complex correlations.…
GovScape: A Public Multimodal Search System for 70 Million Pages of Government PDFs
Ying-Hsiang Huang, Claire Gong, Shreya Shaji +10
Efforts over the past three decades have produced web archives containing billions of webpage snapshots and petabytes of data. The End of Term Web Archive alone contains, among oth…
Pessimistic Cardinality Estimation
Mahmoud Abo Khamis, Kyle Deeds, Dan Olteanu +1
Cardinality Estimation is to estimate the size of the output of a query without computing it, by using only statistics on the input relations. Existing estimators try to return an…