35 citations · 151 across the 21 of their papers we have counts for
29 papers
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…
Convergence of Datalog over (Pre-) Semirings
Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler +2
Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in…
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,…
Maintaining Triangle Queries under Updates
Ahmet Kara, Milos Nikolic, Hung Q. Ngo +2
We consider the problem of incrementally maintaining the triangle queries with arbitrary free variables under single-tuple updates to the input relations. We introduce an approach…
Global Health Monitor: A Web-based System for Detecting and Mapping Infectious Diseases
Son Doan, Quoc-Hung Ngo, Ai Kawazoe +1
We present the Global Health Monitor, an online Web-based system for detecting and mapping infectious disease outbreaks that appear in news stories. The system analyzes English new…
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…
Rk-means: Fast Clustering for Relational Data
Ryan Curtin, Ben Moseley, Hung Q. Ngo +3
Conventional machine learning algorithms cannot be applied until a data matrix is available to process. When the data matrix needs to be obtained from a relational database via a f…
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…
Counting Triangles under Updates in Worst-Case Optimal Time
Ahmet Kara, Hung Q. Ngo, Milos Nikolic +2
We consider the problem of incrementally maintaining the triangle count query under single-tuple updates to the input relations. We introduce an approach that exhibits a space-time…
Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems
Hung Q. Ngo
Worst-case optimal join algorithms are the class of join algorithms whose runtime match the worst-case output size of a given join query. While the first provably worst-case optima…
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…
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu
Recent works on bounding the output size of a conjunctive query with functional dependencies and degree constraints have shown a deep connection between fundamental questions in in…
On Optimality Conditions for Auto-Encoder Signal Recovery
Devansh Arpit, Yingbo Zhou, Hung Q. Ngo +2
Auto-Encoders are unsupervised models that aim to learn patterns from observed data by minimizing a reconstruction cost. The useful representations learned are often found to be sp…
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…
Why Regularized Auto-Encoders learn Sparse Representation?
Devansh Arpit, Yingbo Zhou, Hung Ngo +1
While the authors of Batch Normalization (BN) identify and address an important problem involved in training deep networks-- \textit{Internal Covariate Shift}-- the current solutio…
FAQ: Questions Asked Frequently
Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra
We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probab…
Join Processing for Graph Patterns: An Old Dog with New Tricks
Dung Nguyen, Molham Aref, Martin Bravenboer +4
Join optimization has been dominated by Selinger-style, pairwise optimizers for decades. But, Selinger-style algorithms are asymptotically suboptimal for applications in graphic an…
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…
Joins via Geometric Resolutions: Worst-case and Beyond
Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré +1
We present a simple geometric framework for the relational join. Using this framework, we design an algorithm that achieves the fractional hypertree-width bound, which generalizes…