10 citations · 23 across the 11 of their papers we have counts for
17 papers
Join Size Bounds using Lp-Norms on Degree Sequences
Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu +1
Estimating the output size of a query is a fundamental yet longstanding problem in database query processing. Traditional cardinality estimators used by database systems can routin…
Optimizing Recursive Queries with Program Synthesis
Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q. Ngo +2
Most work on query optimization has concentrated on loop-free queries. However, data science and machine learning workloads today typically involve recursive or iterative computati…
The Complexity of Boolean Conjunctive Queries with Intersection Joins
Mahmoud Abo Khamis, George Chichirim, Antonia Kormpa +1
Intersection joins over interval data are relevant in spatial and temporal data settings. A set of intervals join if their intersection is non-empty. In case of point intervals, th…
Instance Optimal Join Size Estimation
Mahmoud Abo-Khamis, Sungjin Im, Benjamin Moseley +2
We consider the problem of efficiently estimating the size of the inner join of a collection of preprocessed relational tables from the perspective of instance optimality analysis.…
A Relational Gradient Descent Algorithm For Support Vector Machine Training
Mahmoud Abo-Khamis, Sungjin Im, Benjamin Moseley +2
We consider gradient descent like algorithms for Support Vector Machine (SVM) training when the data is in relational form. The gradient of the SVM objective can not be efficiently…
Approximate Aggregate Queries Under Additive Inequalities
Mahmoud Abo-Khamis, Sungjin Im, Benjamin Moseley +2
We consider the problem of evaluating certain types of functional aggregation queries on relational data subject to additive inequalities. Such aggregation queries, with a smallish…
Decision Problems in Information Theory
Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo +1
Constraints on entropies are considered to be the laws of information theory. Even though the pursuit of their discovery has been a central theme of research in information theory,…
Learning Models over Relational Data: A Brief Tutorial
Maximilian Schleich, Dan Olteanu, Mahmoud Abo-Khamis +2
This tutorial overviews the state of the art in learning models over relational databases and makes the case for a first-principles approach that exploits recent developments in da…
A Layered Aggregate Engine for Analytics Workloads
Maximilian Schleich, Dan Olteanu, Mahmoud Abo Khamis +2
This paper introduces LMFAO (Layered Multiple Functional Aggregate Optimization), an in-memory optimization and execution engine for batches of aggregates over the input database.…
Bag Query Containment and Information Theory
Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo +1
The query containment problem is a fundamental algorithmic problem in data management. While this problem is well understood under set semantics, it is by far less understood under…
Functional Aggregate Queries with Additive Inequalities
Mahmoud Abo Khamis, Ryan R. Curtin, Benjamin Moseley +4
Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering functional aggregate queries (FAQ) in which some…
AC/DC: In-Database Learning Thunderstruck
Mahmoud Abo Khamis, Hung Q. Ngo, XuanLong Nguyen +2
We report on the design and implementation of the AC/DC gradient descent solver for a class of optimization problems over normalized databases. AC/DC decomposes an optimization pro…
Boolean Tensor Decomposition for Conjunctive Queries with Negation
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Olteanu +1
We propose an algorithm for answering conjunctive queries with negation, where the negated relations have bounded degree. Its data complexity matches that of the best known algorit…
Juggling Functions Inside a Database
Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra
We define and study the Functional Aggregate Query (FAQ) problem, which captures common computational tasks across a very wide range of domains including relational databases, logi…
Learning Models over Relational Data using Sparse Tensors and Functional Dependencies
Mahmoud Abo Khamis, Hung Q. Ngo, XuanLong Nguyen +2
Integrated solutions for analytics over relational databases are of great practical importance as they avoid the costly repeated loop data scientists have to deal with on a daily b…
Computing Join Queries with Functional Dependencies
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu
Recently, Gottlob, Lee, Valiant, and Valiant (GLVV) presented an output size bound for join queries with functional dependencies (FD), based on a linear program on polymatroids. GL…
Sparse Approximation, List Decoding, and Uncertainty Principles
Mahmoud Abo Khamis, Anna C. Gilbert, Hung Q. Ngo +1
We consider list versions of sparse approximation problems, where unlike the existing results in sparse approximation that consider situations with unique solutions, we are interes…