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.TIME.2020.18
URN: urn:nbn:de:0030-drops-129869
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12986/
Go to the corresponding LIPIcs Volume Portal

Hellings, Jelle ; Wu, Yuqing

Stab-Forests: Dynamic Data Structures for Efficient Temporal Query Processing

pdf-format:
LIPIcs-TIME-2020-18.pdf (0.7 MB)

Abstract

Many sources of data have temporal start and end attributes or are created in a time-ordered manner. Hence, it is only natural to consider joining datasets based on these temporal attributes. To do so efficiently, several internal-memory temporal join algorithms have recently been proposed. Unfortunately, these join algorithms are designed to join entire datasets and cannot efficiently join skewed datasets in which only few events participate in the join result.
To support high-performance internal-memory temporal joins of skewed datasets, we propose the skip-join algorithm, which operates on stab-forests. The stab-forest is a novel dynamic data structure for indexing temporal data that allows efficient updates when events are appended in a time-based order. Our stab-forests efficiently support not only traditional temporal stab-queries, but also more general multi-stab-queries. We conducted an experimental evaluation to compare the skip-join algorithm with state-of-the-art techniques using real-world datasets. We observed that the skip-join algorithm outperforms other techniques by an order of magnitude when joining skewed datasets and delivers comparable performance to other techniques on non-skewed datasets.

BibTeX - Entry

@InProceedings{hellings_et_al:LIPIcs:2020:12986,
  author =	{Jelle Hellings and Yuqing Wu},
  title =	{{Stab-Forests: Dynamic Data Structures for Efficient Temporal Query Processing}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Emilio Mu{\~n}oz-Velasco and Ana Ozaki and Martin Theobald},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12986},
  URN =		{urn:nbn:de:0030-drops-129869},
  doi =		{10.4230/LIPIcs.TIME.2020.18},
  annote =	{Keywords: Cache-friendly temporal joins, temporal data, skewed data, stab-queries, temporal indices}
}

Keywords: Cache-friendly temporal joins, temporal data, skewed data, stab-queries, temporal indices
Collection: 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)
Issue Date: 2020
Date of publication: 15.09.2020
Supplementary Material: Open-source code of the full implementation of the data structures, algorithms, and supporting tooling used can be found at https://jhellings.nl/projects/skipjoin/.

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