Skip to main content

Computing Complex Temporal Join Queries Efficiently

Publication ,  Conference
Hu, X; Sintos, S; Gao, J; Agarwal, PK; Yang, J
Published in: Proceedings of the ACM SIGMOD International Conference on Management of Data
June 10, 2022

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.

Duke Scholars

Published In

Proceedings of the ACM SIGMOD International Conference on Management of Data

DOI

ISSN

0730-8078

Publication Date

June 10, 2022

Start / End Page

2076 / 2090
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Hu, X., Sintos, S., Gao, J., Agarwal, P. K., & Yang, J. (2022). Computing Complex Temporal Join Queries Efficiently. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 2076–2090). https://doi.org/10.1145/3514221.3517893
Hu, X., S. Sintos, J. Gao, P. K. Agarwal, and J. Yang. “Computing Complex Temporal Join Queries Efficiently.” In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2076–90, 2022. https://doi.org/10.1145/3514221.3517893.
Hu X, Sintos S, Gao J, Agarwal PK, Yang J. Computing Complex Temporal Join Queries Efficiently. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2022. p. 2076–90.
Hu, X., et al. “Computing Complex Temporal Join Queries Efficiently.” Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022, pp. 2076–90. Scopus, doi:10.1145/3514221.3517893.
Hu X, Sintos S, Gao J, Agarwal PK, Yang J. Computing Complex Temporal Join Queries Efficiently. Proceedings of the ACM SIGMOD International Conference on Management of Data. 2022. p. 2076–2090.

Published In

Proceedings of the ACM SIGMOD International Conference on Management of Data

DOI

ISSN

0730-8078

Publication Date

June 10, 2022

Start / End Page

2076 / 2090