Computing Complex Temporal Join Queries Efficiently

Summary: Multi-way temporal joins on intervals; reduces intermediates via overlap-aware processing. Durable temporal joins; classify joins; linear-time iff r-hierarchical (3SUM); output-sensitive methods for non-r-hierarchical cases; implemented. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h749b514b80968bfa
Venue: SIGMOD
Year: 2022
Pagerank: 5.4822011e-05
Overall Rank: 7,616 | 48.82%
DOI: 10.1145/3514221.3517893

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu (Duke University)
2. Stavros Sintos (University of Chicago)
3. Junyang Gao (Google)
4. Pankaj K. Agarwal (Duke University)
5. Jun Yang (Duke University)

BibTeX Citation

@inproceedings{hu_sigmod22,
        title = {{Computing Complex Temporal Join Queries Efficiently}},
        author = {Hu, Xiao and Sintos, Stavros and Gao, Junyang and Agarwal, Pankaj K. and Yang, Jun},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517893},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517893},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,294	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5616228e-05
8,013	Differentially Private Data Release over Multiple Tables	2023	PODS	5.4050229e-05
8,752	LIT: Lightning-fast In-memory Temporal Indexing	2024	SIGMOD	5.2857144e-05
8,841	On Reporting Durable Patterns in Temporal Proximity Graphs	2024	PODS	5.2655908e-05
10,863	Worst-Case Optimal BGPs on Temporal Graphs	2026	VLDB	4.9769913e-05
11,662	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029048509
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021236408
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015334386
685	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014778299
813	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013722638
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012068611
1,106	Path Problems in Temporal Graphs	2014	VLDB	0.0001199079
1,924	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3706925e-05
2,151	The Time Index: An Access Structure for Temporal Data	1990	VLDB	8.9510232e-05
2,611	Timeline Index: A Unified Data Structure for Processing Queries on Temporal Data in SAP HANA	2013	SIGMOD	8.2237793e-05
4,336	Joining Interval Data in Relational Databases	2004	SIGMOD	6.6528595e-05
4,466	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.584648e-05
4,570	Overlap Interval Partition Join	2014	SIGMOD	6.5270765e-05
5,481	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.1126446e-05
6,290	On Spatially Partitioned Temporal Join	1994	VLDB	5.8200527e-05
6,429	Temporal Alignment	2012	SIGMOD	5.7864574e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,595	Efficient Computation of Temporal Aggregates with Range Predicates	2001	PODS
2	1,514	Computing Joins Of Relations	1975	SIGMOD
3	6,958	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS
4	3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
5	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
6	7,438	Efficient Computation of Quantiles over Joins	2023	PODS
7	3,661	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
8	6,290	On Spatially Partitioned Temporal Join	1994	VLDB
9	4,064	Event-Join Optimization in Temporal Relational Databases	1989	VLDB
10	5,540	Temporal Query Processing and Optimization in Multiprocessor Database Machines	1992	VLDB