Mahmoud Abo Khamis

Guanaco: A Global-Uniformity Algorithm for Near-Submodular-Width Conjunctive Query Evaluation

We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time with exponent equal to the submodular width plus epsilon. The algorithm and its running time generalize smoothly to general conjunctive que...