Worst-case Optimal Join Algorithms

DOI10.1145/3180143zbMath1426.68081arXiv1203.1952OpenAlexW2963066364MaRDI QIDQ4561503

Ely Porat, Atri Rudra, Christopher Re, Hung Quang Ngo

Publication date: 6 December 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.1952

zbMATH Keywords

Loomis-Whitney inequalityjoin algorithmsBollobás-Thomason inequalityfractional cover bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Related Items

Answering conjunctive queries with inequalities, Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries, General space-time tradeoffs via relational queries, Unnamed Item, A probabilistic model for assigning queries at the edge, Reverse and dual Loomis-Whitney-type inequalities, Unnamed Item, A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling, A formally verified, optimized monitor for metric first-order dynamic logic