License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2022.9
URN: urn:nbn:de:0030-drops-158838
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15883/
Go to the corresponding LIPIcs Volume Portal

Tao, Yufei

Parallel Acyclic Joins with Canonical Edge Covers

pdf-format:
LIPIcs-ICDT-2022-9.pdf (0.9 MB)

Abstract

In PODS'21, Hu presented an algorithm in the massively parallel computation (MPC) model that processes any acyclic join with an asymptotically optimal load. In this paper, we present an alternative analysis of her algorithm. The novelty of our analysis is in the revelation of a new mathematical structure - which we name canonical edge cover - for acyclic hypergraphs. We prove non-trivial properties for canonical edge covers that offer us a graph-theoretic perspective about why Hu’s algorithm works.

BibTeX - Entry

@InProceedings{tao:LIPIcs.ICDT.2022.9,
  author =	{Tao, Yufei},
  title =	{{Parallel Acyclic Joins with Canonical Edge Covers}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15883},
  URN =		{urn:nbn:de:0030-drops-158838},
  doi =		{10.4230/LIPIcs.ICDT.2022.9},
  annote =	{Keywords: Joins, Conjunctive Queries, MPC Algorithms, Parallel Computing}
}

Keywords: Joins, Conjunctive Queries, MPC Algorithms, Parallel Computing
Collection: 25th International Conference on Database Theory (ICDT 2022)
Issue Date: 2022
Date of publication: 19.03.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI