{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T15:04:40Z","timestamp":1775228680299,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":88,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["IIS-1814493, CCF-2007556, IIS-2008107"],"award-info":[{"award-number":["IIS-1814493, CCF-2007556, IIS-2008107"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,10]]},"DOI":"10.1145\/3514221.3517893","type":"proceedings-article","created":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T02:33:49Z","timestamp":1655001229000},"page":"2076-2090","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Computing Complex Temporal Join Queries Efficiently"],"prefix":"10.1145","author":[{"given":"Xiao","family":"Hu","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junyang","family":"Gao","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"DBLP. https:\/\/snap.stanford.edu\/data\/com-DBLP.html."},{"key":"e_1_3_2_1_2_1","unstructured":"Flights Dataset. https:\/\/github.com\/IITDBGroup\/2019-PVLDB-Reproducibility-Snapshot-Semantics-For-Temporal-Multiset-Relations\/tree\/master\/datasets\/flights."},{"key":"e_1_3_2_1_3_1","unstructured":"LDBC's Social Network Benchmark. https:\/\/ldbcouncil.org\/."},{"key":"e_1_3_2_1_4_1","unstructured":"MariaDB. https:\/\/mariadb.com\/kb\/en\/library\/system-versioned-tables\/."},{"key":"e_1_3_2_1_5_1","unstructured":"MarkLogic. https:\/\/www.marklogic.com\/."},{"key":"e_1_3_2_1_6_1","unstructured":"Oracle. https:\/\/www.oracle.com."},{"key":"e_1_3_2_1_7_1","unstructured":"PostgreSQL. https:\/\/www.postgresql.org."},{"key":"e_1_3_2_1_8_1","unstructured":"RapidMatch. https:\/\/github.com\/RapidsAtHKUST\/RapidMatch."},{"key":"e_1_3_2_1_9_1","unstructured":"SirixDB. https:\/\/sirix.io\/."},{"key":"e_1_3_2_1_10_1","unstructured":"SQL Server. https:\/\/www.microsoft.com\/en-us\/sql-server\/."},{"key":"e_1_3_2_1_11_1","unstructured":"TerminusDB. https:\/\/terminusdb.com\/."},{"key":"e_1_3_2_1_12_1","unstructured":"TPC-E Benchmark. http:\/\/www.tpc.org\/tpce\/."},{"key":"e_1_3_2_1_13_1","unstructured":"TPC-H Benchmark. http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_3_2_1_14_1","unstructured":"https:\/\/github.com\/huxiao2010\/TemporalJoin."},{"key":"e_1_3_2_1_15_1","unstructured":"https:\/\/github.com\/huxiao2010\/TemporalJoin\/blob\/main\/Temporal_Join_SIGMOD_Full.pdf."},{"key":"e_1_3_2_1_16_1","unstructured":"XTDB. https:\/\/github.com\/xtdb\/xtdb."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"M. A. Khamis H. Q. Ngo and D. Suciu. 2017. What do Shannon-type Inequalities Submodular Width and Disjunctive Datalog have to do with one another?. In PODS. 429--444.","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_3_2_1_18_1","volume-title":"Foundations of databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of databases. Vol. 8. Addison-Wesley Reading."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"M. Al-Kateb A. Ghazal A. Crolotte R. Bhashyam J. Chimanchode and S. Pakala. 2013. Temporal query processing in Teradata. In EDBT. 573--578.","DOI":"10.1145\/2452376.2452443"},{"key":"e_1_3_2_1_20_1","first-page":"570","article-title":"Scalable sweeping-based spatial join","volume":"98","author":"Arge L.","year":"1998","unstructured":"L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. 1998. Scalable sweeping-based spatial join. In VLDB, Vol. 98. 570--581.","journal-title":"VLDB"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"A. Atserias Ma. Grohe and D. Marx. 2008. Size bounds and query plans for relational joins. In FOCS. IEEE 739--748.","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050028"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"C. Berkholz J. Keppeler and N. Schweikardt. 2017. Answering conjunctive queries under updates. In PODS. 303--318.","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"M. B\u00f6hlen J. Gamper and C. S. Jensen. 2006. Multi-dimensional aggregation for temporal data. In EDBT. 257--275.","DOI":"10.1007\/11687238_18"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"P. Bouros N. Mamoulis D. Tsitsigkos and M. Terrovitis. 2021. In-Memory Interval Joins. The VLDB journal (2021) 1--25.","DOI":"10.1007\/s00778-020-00639-0"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170075"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0456-7"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2012.668546"},{"key":"e_1_3_2_1_30_1","first-page":"401","article-title":"Trill: A high-performance incremental query processor for diverse analytics","volume":"8","author":"Chandramouli B.","year":"2014","unstructured":"B. Chandramouli, J. Goldstein, M. Barnett, R. DeLine, D. Fisher, J. C. Platt, J. F. Terwilliger, and J. Wernsing. 2014. Trill: A high-performance incremental query processor for diverse analytics. The VLDB journal 8, 4 (2014), 401--412.","journal-title":"The VLDB journal"},{"key":"e_1_3_2_1_31_1","unstructured":"B. Chawda H. Gupta S. Negi T. A. Faruquie L. V. Subramaniam and M. K. Mohania. 2014. Processing Interval Joins On Map-Reduce.. In EDBT. 463--474."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"A. Dign\u00f6s M. H. B\u00f6hlen and J. Gamper. 2012. Temporal alignment. In SIGMOD. 433--444.","DOI":"10.1145\/2213836.2213886"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"A. Dign\u00f6s M. H. B\u00f6hlen and J. Gamper. 2014. Overlap interval partition join. In SIGMOD. 1459--1470.","DOI":"10.1145\/2588555.2612175"},{"key":"e_1_3_2_1_35_1","unstructured":"R. Elmasri G. T. Wuu and Y. Kim. 1990. The time index: An access structure for temporal data. In VLDB. 1--12."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"J. Enderle M. Hampel and T. Seidl. 2004. Joining interval data in relational databases. In SIGMOD. 683--694.","DOI":"10.1145\/1007568.1007645"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"R. Fagin and D. Olteanu. 2016. Dichotomies for Queries with Negation in Probabilistic Databases. TODS 41 1 (2016).","DOI":"10.1145\/2877203"},{"key":"e_1_3_2_1_39_1","unstructured":"M. Franzke T. Emrich A. Z\u00fcfle and M. Renz. 2018. Pattern search in temporal social networks. In EDBT."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"A. Gajentaan and M. H. Overmars. 1995. On a class of O (n2) problems in computational geometry. Computational geometry 5 3 (1995) 165--185.","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0111-3"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-012-1235-y"},{"key":"e_1_3_2_1_43_1","volume-title":"Tractability: Practical Approaches to Hard Problems 1","author":"Gottlob G.","year":"2014","unstructured":"G. Gottlob, G. Greco, and F. Scarcello. 2014. Treewidth and hypertree width. Tractability: Practical Approaches to Hard Problems 1 (2014)."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"H. Gunadhi and A. Segev. 1991. Query processing algorithms for temporal intersection joins. In ICDE. 336--344.","DOI":"10.1109\/ICDE.1991.131481"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"P. Holme and J. Saram\u00e4ki. 2012. Temporal networks. Physics reports 519 3 (2012) 97--125.","DOI":"10.1016\/j.physrep.2012.03.001"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"X. Hu and K. Yi. 2019. Instance and Output Optimal Parallel Algorithms for Acyclic Joins. In PODS. 450--463.","DOI":"10.1145\/3294052.3319698"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv227"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"M. Idris M. Ugarte and S. Vansummeren. 2017. The dynamic yannakakis algorithm: Compact and efficient query processing under updates. In SIGMOD. 1259--1274.","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_3_2_1_50_1","volume-title":"Tpc-bih: A benchmark for bitemporal databases","author":"Kaufmann M.","year":"2013","unstructured":"M. Kaufmann, P. M. Fischer, N. May, A. Tonder, and D. Kossmann. 2013. Tpc-bih: A benchmark for bitemporal databases. In TPCTC. Springer, 16--31."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"M. Kaufmann A. A. Manjili P. Vagenas P. M. Fischer D. Kossmann F. F\u00e4rber and N. May. 2013. Timeline index: a unified data structure for processing queries on temporal data in SAP HANA. In SIGMOD. 1173--1184.","DOI":"10.1145\/2463676.2465293"},{"key":"e_1_3_2_1_52_1","unstructured":"N. Kline and R. T. Snodgrass. 1995. Computing temporal aggregates. In ICDE. 222--231."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"G. Kossinets J. Kleinberg and D. Watts. 2008. The structure of information pathways in a social communication network. In SIGKDD. 435--443.","DOI":"10.1145\/1401890.1401945"},{"key":"e_1_3_2_1_54_1","volume-title":"Temporal graphs. Physica A: Statistical Mechanics and its Applications 388, 6","author":"Kostakos V.","year":"2009","unstructured":"V. Kostakos. 2009. Temporal graphs. Physica A: Statistical Mechanics and its Applications 388, 6 (2009), 1007--1023."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2011\/11\/P11005"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"H. Kriegel P. Kunath M. Pfeifle and M. Renz. 2005. Distributed intersection join of complex interval sequences. In DASFAA. Springer 748--760.","DOI":"10.1007\/11408079_68"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380776.2380786"},{"key":"e_1_3_2_1_58_1","unstructured":"J. Leskovec and A. Krevl. June 2014. SNAP Datasets: Stanford large network dataset collection. (June 2014)."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Y. Lin Y. Chi S. Zhu H. Sundaram and B. L. Tseng. 2008. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In WWW. 685--694.","DOI":"10.1145\/1367497.1367590"},{"key":"e_1_3_2_1_60_1","unstructured":"H. Lu B. C. Ooi and K. Tan. 1994. On spatially partitioned temporal join. In VLDB. 546--557."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"crossref","unstructured":"P. Mackey K. Porterfield E. Fitzhenry S. Choudhury and G. Chin. 2018. A chronological edge-driven approach to temporal subgraph isomorphism. In Big Data. 3972--3979.","DOI":"10.1109\/BigData.2018.8622100"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2016.1177801"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"H. Q. Ngo. 2018. Worst-case optimal join algorithms: Techniques results and open problems. In PODS. 111--124.","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.016105"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"crossref","unstructured":"A. Paranjape A. R. Benson and J. Leskovec. 2017. Motifs in temporal networks. In WSDM. 601--610.","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"crossref","unstructured":"M. Patrascu. 2010. Towards polynomial lower bounds for dynamic problems. In STOC. 603--610.","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"crossref","unstructured":"D. Piatov S. Helmer and A. Dign\u00f6s. 2016. An interval join optimized for modern hardware. In ICDE. 1098--1109.","DOI":"10.1109\/ICDE.2016.7498316"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"crossref","unstructured":"U. Redmond and P. Cunningham. 2013. Temporal subgraph isomorphism. In ASONAM. IEEE 1451--1452.","DOI":"10.1145\/2492517.2492586"},{"key":"e_1_3_2_1_72_1","unstructured":"C. M. Saracco M. Nicola and L. Gandhi. 2010. A matter of time: Temporal data management in DB2 for z. Technical Report. IBM Corporation New York."},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"crossref","unstructured":"K. Semertzidis and E. Pitoura. 2016. Durable graph pattern queries on historical graphs. In ICDE. 541--552.","DOI":"10.1109\/ICDE.2016.7498269"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"crossref","unstructured":"H. Shen B. C. Ooi and H. Lu. 1994. The TP-Index: A dynamic and efficient indexing mechanism for temporal databases. In ICDE. 274--281.","DOI":"10.1109\/ICDE.1994.283041"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"crossref","unstructured":"I. Sitzmann and P. J. Stuckey. 2000. Improving temporal joins using histograms. In DEXA. Springer 488--498.","DOI":"10.1007\/3-540-44469-6_46"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/181550.181562"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"crossref","unstructured":"M. D. Soo R. T. Snodgrass and C. S. Jensen. 1994. Efficient evaluation of the valid-time natural join. In ICDE. 282--292.","DOI":"10.1109\/ICDE.1994.283042"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2911181"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1672308.1672329"},{"key":"e_1_3_2_1_80_1","volume-title":"Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In ICDT. 96--106.","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen. 2014. Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In ICDT. 96--106."},{"key":"e_1_3_2_1_81_1","first-page":"721","article-title":"Path problems in temporal graphs","volume":"7","author":"Wu H.","year":"2014","unstructured":"H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. 2014. Path problems in temporal graphs. The VLDB journal 7, 9 (2014), 721--732.","journal-title":"The VLDB journal"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"crossref","unstructured":"H. Wu Y. Huang J. Cheng J. Li and Y. Ke. 2016. Reachability and time-based path queries in temporal graphs. In ICDE. 145--156.","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001728"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"crossref","unstructured":"Y. Yang D. Yan H. Wu J. Cheng S. Zhou and J. Lui. 2016. Diversified temporal subgraph pattern mining. In SIGKDD. 1965--1974.","DOI":"10.1145\/2939672.2939848"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"crossref","unstructured":"Z. Yang A. W. Fu and R. Liu. 2016. Diversified top-k subgraph querying in a large graph. In SIGMOD. 1167--1182.","DOI":"10.1145\/2882903.2915216"},{"key":"e_1_3_2_1_86_1","first-page":"82","article-title":"Algorithms for acyclic database schemes","volume":"81","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB, Vol. 81. 82--94.","journal-title":"VLDB"},{"key":"e_1_3_2_1_87_1","unstructured":"D. Zhang V. J. Tsotras and B. Seeger. 2002. Efficient temporal join processing using indices. In ICDE. 103--113."},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"crossref","unstructured":"Q. Zhao Y. Tian Q. He N. Oliver R. Jin and W. Lee. 2010. Communication motifs: a tool to characterize social communications. In CIKM. 1645--1648.","DOI":"10.1145\/1871437.1871694"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2022 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3517893","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514221.3517893","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514221.3517893","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:36Z","timestamp":1750188636000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3517893"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":88,"alternative-id":["10.1145\/3514221.3517893","10.1145\/3514221"],"URL":"https:\/\/doi.org\/10.1145\/3514221.3517893","relation":{},"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"2022-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}