Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins

Title: "Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins"

Speaker: Xiao Hu, HKUST

Time/Date: Friday, Jun 3, 11am-12nn

Location: Room 3501 (via lift 25/26), HKUST

Abstract:

Nested-loop join is a worst-case I/O-optimal algorithm for 2 relations. 
Recently, a lot of efforts have been devoted to the "triangle query", for 
which an I/O-optimal algorithm is known. We extend these results to a 
fairly large class of acyclic joins. Acyclic joins can be computed 
optimally in internal memory using Yannakakis' algorithm from 1981, which 
simply performs a series of pairwise joins. However, no pairwise join 
algorithm can be I/O-optimal beyond 2 relations. To achieve I/O-optimality, 
the algorithm has to handle all the intermediate results carefully without 
writing them to disk. Unlike the optimal internal memory join algorithm 
which has a nice tight bound (the AGM bound), the I/O-complexity of joins 
turns out to be quite complex or even unknown. Yet, we are able to prove 
that our algorithm is I/O-optimal for certain classes of acyclic joins 
without deriving its bound explicitly.

More information on the CSE Theory Seminars can be found at
http://cse.hkust.edu.hk/tcsc/seminars.html