1 Search Results for "Wu, Yuqing"


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

Authors: Jelle Hellings and Yuqing Wu

Published in: LIPIcs, Volume 178, 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)


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.

Cite as

Jelle Hellings and Yuqing Wu. Stab-Forests: Dynamic Data Structures for Efficient Temporal Query Processing. In 27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{hellings_et_al:LIPIcs.TIME.2020.18,
  author =	{Hellings, Jelle and Wu, Yuqing},
  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 =	{Mu\~{n}oz-Velasco, Emilio and Ozaki, Ana and Theobald, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2020.18},
  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}
}
  • Refine by Author
  • 1 Hellings, Jelle
  • 1 Wu, Yuqing

  • Refine by Classification
  • 1 Information systems → Join algorithms
  • 1 Information systems → Temporal data

  • Refine by Keyword
  • 1 Cache-friendly temporal joins
  • 1 skewed data
  • 1 stab-queries
  • 1 temporal data
  • 1 temporal indices

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail