Computing Complex Temporal Join Queries Efficiently

Conference Paper

This paper studies multi-way join queries over temporal data, where each tuple is associated with a valid time interval indicating when the tuple is valid. A temporal join requires that joining tuples' valid intervals intersect. Previous work on temporal joins has focused on joining two relations, but pairwise processing is often inefficient because it may generate unnecessarily large intermediate results. This paper investigates how to efficiently process complex temporal joins involving multiple relations. We also consider a useful extension, durable temporal joins, which further selects results with long enough valid intervals so they are not merely transient patterns. We classify temporal join queries into different classes based on their computational complexity. We identify the class of r-hierarchical joins and show that a linear-time algorithm exists for a temporal join if and only it is r-hierarchical (assuming the 3SUM conjecture holds). We further propose output-sensitive algorithms for non-r-hierarchical joins. We implement our algorithms and evaluate them on both synthetic and real datasets.

Full Text

Duke Authors

Cited Authors

  • Hu, X; Sintos, S; Gao, J; Agarwal, PK; Yang, J

Published Date

  • June 10, 2022

Published In

Start / End Page

  • 2076 - 2090

International Standard Serial Number (ISSN)

  • 0730-8078

International Standard Book Number 13 (ISBN-13)

  • 9781450392495

Digital Object Identifier (DOI)

  • 10.1145/3514221.3517893

Citation Source

  • Scopus