License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2018.2
URN: urn:nbn:de:0030-drops-86126
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8612/
Go to the corresponding LIPIcs Volume Portal

Yi, Ke

Join Algorithms: From External Memory to the BSP

pdf-format:
LIPIcs-ICDT-2018-2.pdf (0.2 MB)

Abstract

Database systems have been traditionally disk-based, which had motivated the extensive study on external memory (EM) algorithms. However, as RAMs continue to get larger and cheaper, modern distributed data systems are increasingly adopting a main memory based, shared-nothing architecture, exemplified by systems like Spark and Flink. These systems can be abstracted by the BSP model (with variants like the MPC model and the MapReduce model), and there has been a strong revived interest in designing BSP algorithms for handling large amounts of data.
With hard disks starting to fade away from the picture, EM algorithms may now seem less relevant. However, we observe that many of the recently developed join algorithms under the BSP model have a high degree of resemblance with their counterparts in the EM model. In this talk, I will present some recent results on join algorithms in the EM and BSP model, examine their relationships, and discuss a general theoretical framework for converting EM algorithms to
the BSP.

BibTeX - Entry

@InProceedings{yi:LIPIcs:2018:8612,
  author =	{Ke Yi},
  title =	{{Join Algorithms: From External Memory to the BSP}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Benny Kimelfeld and Yael Amsterdamer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8612},
  URN =		{urn:nbn:de:0030-drops-86126},
  doi =		{10.4230/LIPIcs.ICDT.2018.2},
  annote =	{Keywords: External memory model, BSP, join algorithms}
}

Keywords: External memory model, BSP, join algorithms
Collection: 21st International Conference on Database Theory (ICDT 2018)
Issue Date: 2018
Date of publication: 05.03.2018

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