6 papers · 1 filter
Convolution Sum-Product Queries
Kyle Deeds, Timo Camillo Merkl, Dan Suciu
We study query evaluation for an extension of sum-product queries (SPQ) that allows atoms with linear combinations of variables (e.g. ), which we call convolution…
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…
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…
QirK: Question Answering via Intermediate Representation on Knowledge Graphs
Jan Luca Scheerer, Anton Lykov, Moe Kayali +4
We demonstrate QirK, a system for answering natural language questions on Knowledge Graphs (KG). QirK can answer structurally complex questions that are still beyond the reach of e…
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.…