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: 6407
Venue: SIGMOD
Year: 2022
Pagerank: 5.4608734e-05
Overall Rank: 8,235 | 43.51%
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 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
7,850	Differentially Private Data Release over Multiple Tables	2023	PODS	5.5316993e-05
8,575	LIT: Lightning-fast In-memory Temporal Indexing	2024	SIGMOD	5.4095946e-05
8,691	On Reporting Durable Patterns in Temporal Proximity Graphs	2024	PODS	5.3839057e-05
11,338	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	5.093636e-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
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
636	Answering Conjunctive Queries under Updates	2017	PODS	0.0001551856
710	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014715033
816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013827772
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,123	Path Problems in Temporal Graphs	2014	VLDB	0.00012089975
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
2,115	The Time Index: An Access Structure for Temporal Data	1990	VLDB	9.1449719e-05
2,568	Timeline Index: A Unified Data Structure for Processing Queries on Temporal Data in SAP HANA	2013	SIGMOD	8.4096765e-05
4,268	Joining Interval Data in Relational Databases	2004	SIGMOD	6.7925685e-05
4,371	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	6.738679e-05
4,482	Overlap Interval Partition Join	2014	SIGMOD	6.6753072e-05
5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.2436385e-05
6,172	On Spatially Partitioned Temporal Join	1994	VLDB	5.9512937e-05
6,805	Temporal Alignment	2012	SIGMOD	5.7678408e-05

Semantically Similar Papers

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