*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: A Tale of Two Join Algorithms
Abstract:
In this talk we will talk about two new database join algorithms with provable optimality guarantees.
We first present a recent algorithm (PODS 2012) that is the first provably optimal (worst-case) algorithm to compute database joins. As a special case, this join algorithm implies (i) The first algorithmic versions of some well-known geometric inequalities due to Loomis and Whitney (and their generalizations by Bollobas and Thomason); (ii) Algorithmically list recoverable codes that work with parameters that no known algorithmic list recovery result work with (e.g. those based on the Reed-Solomon codes) and an application of this result in designing sublinear time decodable compressed sensing schemes; (ii) Worst-case optimal algorithm to list all occurrences of any fixed hypergraph H in a given large hypergraph G.
The second algorithm (PODS 2014) has stronger optimality guarantees: we present an adaptive join algorithm whose run time depends on the "difficulty" of the data. We believe that this algorithm has more practical applications since worst-case optimal algorithms might have terrible performance on "real data." As a special case, we present an (almost) instance optimal algorithm (with respect to comparison based algorithms) for a large class of join queries (namely Fagin's \beta-acyclic queries).
The talk will be self-contained and is based on join(t) works with Ngo, Nguyen, Porat and Re.
