<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Worst Case Optimal Join Algorithms: Techniques, Results, and Open Problems</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Hung Q Ngo</string-name>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Relational AI Inc.</string-name>
        </contrib>
      </contrib-group>
      <abstract>
        <p>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 worse case optimal join algorithm was discovered relatively recently, the techniques and results surrounding these algorithms grow out of decades of research from a wide range of areas, intimately connecting graph theory, algorithms, information theory, constraint satisfaction, database theory, and geometric inequalities. These ideas are not just paper ware, one such algorithms was the work-horse join algorithm of a successful commercial database and data analytics engine. This talks aims to be a gentle introduction to worst case optimal algorithms, the intuition behind them, historical and recent developments, and connections to information theory, and several fundamental open problems.</p>
      </abstract>
    </article-meta>
  </front>
  <body />
  <back>
    <ref-list />
  </back>
</article>