{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T07:32:36Z","timestamp":1773041556214,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T00:00:00Z","timestamp":1772064000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T00:00:00Z","timestamp":1772064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62302521"],"award-info":[{"award-number":["62302521"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62402524"],"award-info":[{"award-number":["62402524"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We investigate temporal-clique subgraph pattern matching, where edges must both form a specific topological sub-structure and temporally overlap within a specified window. This problem has widespread applications across domains including social networks, life sciences, smart cities, and telecommunications. However, existing subgraph matching techniques are inefficient at processing such queries that combine both temporal and structural constraints. We propose a novel approach that effectively leverages both topological and temporal selectivities of the query to significantly improve processing performance. Our solution introduces key innovations across the query processing pipeline, including a specialized multi-way join operator, an optimized query planner, and an accurate cardinality estimator. Through additional optimizations, we further enhance the efficiency of our approach. Extensive experiments demonstrate that our method substantially outperforms state-of-the-art techniques while requiring minimal additional storage overhead.<\/jats:p>","DOI":"10.1007\/s00778-026-00963-x","type":"journal-article","created":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T19:25:03Z","timestamp":1772133903000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On topology and time: efficient evaluation for temporal-clique subgraph queries"],"prefix":"10.1007","volume":"35","author":[{"given":"Kaijie","family":"Zhu","sequence":"first","affiliation":[]},{"given":"Di","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Shichang","family":"Ding","sequence":"additional","affiliation":[]},{"given":"George","family":"Fletcher","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1488-1414","authenticated-orcid":false,"given":"Nikolay","family":"Yakovets","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,26]]},"reference":[{"key":"963_CR1","unstructured":"SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data, 2014"},{"key":"963_CR2","unstructured":"Divvy System Data. https:\/\/www.divvybikes.com\/system-data, 2019"},{"key":"963_CR3","unstructured":"NYC Citi Bike. https:\/\/www.citibikenyc.com\/system-data, 2019"},{"key":"963_CR4","unstructured":"NYC TLC Trip Record Data. https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page, 2019"},{"key":"963_CR5","unstructured":"Mawi working group traffic archive. https:\/\/mawi.wide.ad.jp\/mawi\/, 2025"},{"issue":"4","key":"963_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3129246","volume":"42","author":"CR Aberger","year":"2017","unstructured":"Aberger, C.R., Lamb, A., Tu, S., N\u00f6tzli, A., Olukotun, K., R\u00e9, C.: Emptyheaded: A relational engine for graph processing. ACM TODS 42(4), 1\u201344 (2017)","journal-title":"ACM TODS"},{"key":"963_CR7","doi-asserted-by":"crossref","unstructured":"Bhattarai, B., Liu, H., Huang, H.\u00a0H.: Ceci: Compact embedding cluster index for scalable subgraph matching. In SIGMOD, pages 1447\u20131462, (2019)","DOI":"10.1145\/3299869.3300086"},{"key":"963_CR8","doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing cartesian products. In SIGMOD, pages 1199\u20131214, (2016)","DOI":"10.1145\/2882903.2915236"},{"key":"963_CR9","doi-asserted-by":"crossref","unstructured":"Bonifati, A., Fletcher, G., Voigt, H., Yakovets, N.: Querying Graphs. Morgan & Claypool Publishers, (2018)","DOI":"10.1007\/978-3-031-01864-0"},{"issue":"11","key":"963_CR10","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.14778\/3137628.3137644","volume":"10","author":"P Bouros","year":"2017","unstructured":"Bouros, P., Mamoulis, N.: A forward scan based plane sweep algorithm for parallel interval joins. VLDB Endowment 10(11), 1346\u20131357 (2017)","journal-title":"VLDB Endowment"},{"issue":"3","key":"963_CR11","first-page":"424","volume":"32","author":"J Byun","year":"2019","unstructured":"Byun, J., Woo, S., Kim, D.: Chronograph: Enabling temporal graph traversals for efficient information diffusion analysis over time. IEEE TKDE 32(3), 424\u2013437 (2019)","journal-title":"IEEE TKDE"},{"key":"963_CR12","doi-asserted-by":"crossref","unstructured":"Cai, W., Balazinska, M., Suciu, D.: Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities. In SIGMOD, pages 18\u201335, (2019)","DOI":"10.1145\/3299869.3319894"},{"issue":"10","key":"963_CR13","doi-asserted-by":"publisher","first-page":"1845","DOI":"10.14778\/3467861.3467873","volume":"14","author":"X Chen","year":"2021","unstructured":"Chen, X., Wang, K., Lin, X., Zhang, W., Qin, L., Zhang, Y.: Efficiently answering reachability and path queries on temporal bipartite graphs. VLDB Endowment 14(10), 1845\u20131858 (2021)","journal-title":"VLDB Endowment"},{"key":"963_CR14","unstructured":"Choudhury, S., Holder, L., Chin, G., Agarwal K., Feo, J.: A selectivity based approach to continuous pattern detection in streaming graphs. In EDBT, pages 157\u2013168, (2015)"},{"issue":"13","key":"963_CR15","doi-asserted-by":"publisher","first-page":"1379","DOI":"10.14778\/2733004.2733010","volume":"7","author":"P Gupta","year":"2014","unstructured":"Gupta, P., Satuluri, V., Grewal, A., Gurumurthy, S., Zhabiuk, V., Li, Q., Lin, J.: Real-time twitter recommendation: Online motif detection in large dynamic graphs. VLDB Endowment 7(13), 1379\u20131380 (2014)","journal-title":"VLDB Endowment"},{"key":"963_CR16","doi-asserted-by":"crossref","unstructured":"Han, M., Kim, H., Gu, G., Park, K., Han, W.: Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In SIGMOD, pages 1429\u20131446, (2019)","DOI":"10.1145\/3299869.3319880"},{"key":"963_CR17","doi-asserted-by":"crossref","unstructured":"Hogan, A., Riveros, C., Rojas, C., Soto, A.: A worst-case optimal join algorithm for sparql. In ISWC, pages 258\u2013275. Springer, (2019)","DOI":"10.1007\/978-3-030-30793-6_15"},{"issue":"1","key":"963_CR18","first-page":"1","volume":"1","author":"T Jin","year":"2023","unstructured":"Jin, T., Li, B., Li, Y., Zhou, Q., Ma, Q., Zhao, Y., Chen, H., Cheng, J.: Circinus: Fast redundancy-reduced subgraph matching. PACMMOD 1(1), 1\u201326 (2023)","journal-title":"PACMMOD"},{"issue":"2","key":"963_CR19","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s00778-022-00749-x","volume":"32","author":"H Kim","year":"2023","unstructured":"Kim, H., Choi, Y., Park, K., Lin, X., Hong, S., Han, W.: Fast subgraph query processing and subgraph matching via static and dynamic equivalences. VLDB J. 32(2), 343\u2013368 (2023)","journal-title":"VLDB J."},{"issue":"1","key":"963_CR20","first-page":"1","volume":"2","author":"K Kim","year":"2024","unstructured":"Kim, K., Lee, S., Kim, I., Han, W.: Asm: Harmonizing autoregressive model, sampling, and multi-dimensional statistics merging for cardinality estimation. PACMMOD 2(1), 1\u201327 (2024)","journal-title":"PACMMOD"},{"key":"963_CR21","unstructured":"Kumar, R., Calders, T.: Finding simple temporal cycles in an interaction network. In TD-LSG@ PKDD\/ECML, pages 3\u20136, (2017)"},{"issue":"10","key":"963_CR22","doi-asserted-by":"publisher","first-page":"974","DOI":"10.14778\/2794367.2794368","volume":"8","author":"L Lai","year":"2015","unstructured":"Lai, L., Qin, L., Lin, X., Chang, L.: Scalable subgraph enumeration in mapreduce. VLDB Endowment 8(10), 974\u2013985 (2015)","journal-title":"VLDB Endowment"},{"issue":"3","key":"963_CR23","first-page":"217","volume":"10","author":"L Lai","year":"2016","unstructured":"Lai, L., Qin, L., Lin, X., Zhang, Y., Chang, L., Yang, S.: Scalable distributed subgraph enumeration. VLDB Endowment 10(3), 217\u2013228 (2016)","journal-title":"Scalable distributed subgraph enumeration. VLDB Endowment"},{"key":"963_CR24","doi-asserted-by":"crossref","unstructured":"Li, F., Wu, B., Yi, K., Zhao, Z.: Wander join: Online aggregation via random walks. In SIGMOD, pages 615\u2013629, (2016)","DOI":"10.1145\/2882903.2915235"},{"issue":"5","key":"963_CR25","first-page":"4713","volume":"35","author":"F Li","year":"2023","unstructured":"Li, F., Zou, Z., Li, J.: Durable subgraph matching on temporal graphs. IEEE TKDE 35(5), 4713\u20134726 (2023)","journal-title":"IEEE TKDE"},{"key":"963_CR26","doi-asserted-by":"crossref","unstructured":"Mackey, P., Porterfield, K., Fitzhenry, E., Choudhury, S., Chin, G.: A chronological edge-driven approach to temporal subgraph isomorphism. In IEEE Big Data, pages 3972\u20133979, (2018)","DOI":"10.1109\/BigData.2018.8622100"},{"issue":"11","key":"963_CR27","doi-asserted-by":"publisher","first-page":"1692","DOI":"10.14778\/3342263.3342643","volume":"12","author":"A Mhedhbi","year":"2019","unstructured":"Mhedhbi, A., Salihoglu, S.: Optimizing subgraph queries by combining binary and worst-case optimal joins. VLDB Endowment 12(11), 1692\u20131704 (2019)","journal-title":"VLDB Endowment"},{"issue":"1","key":"963_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-021-00397-0","volume":"6","author":"G Micale","year":"2021","unstructured":"Micale, G., Locicero, G., Pulvirenti, A., Ferro, A.: Temporalri: subgraph isomorphism in temporal networks with multiple contacts. Appl. Netw. Sci. 6(1), 1\u201322 (2021)","journal-title":"Appl. Netw. Sci."},{"key":"963_CR29","doi-asserted-by":"crossref","unstructured":"Milajerdi, S., Eshete, B., Gjomemo, R., Venkatakrishnan, V.: Poirot: Aligning attack behavior with kernel audit records for cyber threat hunting. In SIGSAC, pages 1795\u20131812, (2019)","DOI":"10.1145\/3319535.3363217"},{"key":"963_CR30","doi-asserted-by":"crossref","unstructured":"Min, S., Jang, J., Park, K., Giammarresi, D., Italiano, G.\u00a0F., Han, W.: Time-constrained continuous subgraph matching using temporal information for filtering and backtracking. In ICDE, pages 3257\u20133269, (2024)","DOI":"10.1109\/ICDE60146.2024.00252"},{"issue":"1","key":"963_CR31","doi-asserted-by":"publisher","first-page":"982","DOI":"10.14778\/1687627.1687738","volume":"2","author":"G Moerkotte","year":"2009","unstructured":"Moerkotte, G., Neumann, T., Steidl, G.: Preventing bad plans by bounding the impact of cardinality estimation errors. VLDB Endowment 2(1), 982\u2013993 (2009)","journal-title":"VLDB Endowment"},{"key":"963_CR32","doi-asserted-by":"crossref","unstructured":"Neumann, T., Moerkotte, G.: Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins. In ICDE, pages 984\u2013994, (2011)","DOI":"10.1109\/ICDE.2011.5767868"},{"issue":"2","key":"963_CR33","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1140\/epjb\/e2004-00124-y","volume":"38","author":"MEJ Newman","year":"2004","unstructured":"Newman, M.E.J.: Detecting community structure in networks. Eur. Phys. J. B 38(2), 321\u2013330 (2004)","journal-title":"Eur. Phys. J. B"},{"issue":"3","key":"963_CR34","first-page":"1","volume":"65","author":"HQ Ngo","year":"2018","unstructured":"Ngo, H.Q., Porat, E., R\u00e9, C., Rudra, A.: Worst-case optimal join algorithms. JACM 65(3), 1\u201340 (2018)","journal-title":"Worst-case optimal join algorithms. JACM"},{"key":"963_CR35","doi-asserted-by":"crossref","unstructured":"Nguyen, D., Aref, M., Bravenboer, M., Kollias, G., Ngo, H.\u00a0Q, R\u00e9, C., Rudra, A.: Join processing for graph patterns: An old dog with new tricks. In GRADES, pages 1\u20138. (2015)","DOI":"10.1145\/2764947.2764948"},{"key":"963_CR36","doi-asserted-by":"crossref","unstructured":"Piatov, D., Helmer, S., Dign\u00f6s, A.: An interval join optimized for modern hardware. In ICDE, pages 1098\u20131109. IEEE, (2016)","DOI":"10.1109\/ICDE.2016.7498316"},{"issue":"2","key":"963_CR37","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.jpdc.2012.10.005","volume":"73","author":"T Plantenga","year":"2013","unstructured":"Plantenga, T.: Inexact subgraph isomorphism in mapreduce. J. Parallel Distrib. Comput. 73(2), 164\u2013175 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"key":"963_CR38","doi-asserted-by":"crossref","unstructured":"Ramesh, S., Baranawal, A., Simmhan, Y.: A distributed path query engine for temporal property graphs. In CCGRID, pages 499\u2013508. IEEE, (2020)","DOI":"10.1109\/CCGrid49817.2020.00-43"},{"key":"963_CR39","first-page":"1","volume":"13","author":"G Sadowski","year":"2014","unstructured":"Sadowski, G., Rathle, P.: Fraud detection: Discovering connections with graph databases. White Paper-Neo Technology-Graphs are Everywhere 13, 1\u201313 (2014)","journal-title":"White Paper-Neo Technology-Graphs are Everywhere"},{"issue":"1","key":"963_CR40","first-page":"181","volume":"31","author":"K Semertzidis","year":"2018","unstructured":"Semertzidis, K., Pitoura, E.: Top-$$ k $$ durable graph pattern queries on temporal graphs. IEEE TKDE 31(1), 181\u2013194 (2018)","journal-title":"IEEE TKDE"},{"key":"963_CR41","doi-asserted-by":"crossref","unstructured":"Sun, S., Luo, Q.: In-memory subgraph matching: An in-depth study. In SIGMOD, pages 1083\u20131098, (2020)","DOI":"10.1145\/3318464.3380581"},{"issue":"2","key":"963_CR42","doi-asserted-by":"publisher","first-page":"176","DOI":"10.14778\/3425879.3425888","volume":"14","author":"S Sun","year":"2020","unstructured":"Sun, S., Sun, X., Che, Y., Luo, Q., He, B.: Rapidmatch: A holistic approach to subgraph query processing. VLDB Endowment 14(2), 176\u2013188 (2020)","journal-title":"VLDB Endowment"},{"issue":"9","key":"963_CR43","doi-asserted-by":"publisher","first-page":"788","DOI":"10.14778\/2311906.2311907","volume":"5","author":"Z Sun","year":"2012","unstructured":"Sun, Z., Wang, H., Wang, H., Shao, B., Li, J.: Efficient subgraph matching on billion node graphs. VLDB Endowment 5(9), 788\u2013799 (2012)","journal-title":"VLDB Endowment"},{"key":"963_CR44","doi-asserted-by":"crossref","unstructured":"Ullmann, J.R.: An algorithm for subgraph isomorphism. JACM 23(1), 31\u201342 (1976)","DOI":"10.1145\/321921.321925"},{"issue":"6","key":"963_CR45","first-page":"5485","volume":"35","author":"W van Leeuwen","year":"2022","unstructured":"van Leeuwen, W., Fletcher, G., Yakovets, N.: A general cardinality estimation framework for subgraph matching in property graphs. IEEE TKDE 35(6), 5485\u20135505 (2022)","journal-title":"IEEE TKDE"},{"key":"963_CR46","unstructured":"Veldhuizen, T.\u00a0L.: Leapfrog triejoin: A simple, worst-case optimal join algorithm. In ICDT, (2014)"},{"key":"963_CR47","doi-asserted-by":"crossref","unstructured":"Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., Wu, H.: Efficient algorithms for temporal path computation. IEEE TKDE 28(11), 2927\u20132942 (2016)","DOI":"10.1109\/TKDE.2016.2594065"},{"key":"963_CR48","doi-asserted-by":"crossref","unstructured":"Wu, H., Huang, Y., Cheng, J., Li, J., Ke, Y.: Reachability and time-based path queries in temporal graphs. In ICDE, pages 145\u2013156, (2016)","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"963_CR49","unstructured":"Wu, Z., Shaikhha, A., Zhu, R., Zeng, K., Han, Y., Zhou, J.: Bayescard: Revitilizing bayesian frameworks for cardinality estimation. arXiv:2012.14743, (2020)"},{"key":"963_CR50","doi-asserted-by":"crossref","unstructured":"Xu, Y., Huang, J., Liu, A., Li, Z., Yin, H., Zhao, L.: Time-constrained graph pattern matching in a large temporal graph. In APWeb-WAIM, pages 100\u2013115, (2017)","DOI":"10.1007\/978-3-319-63579-8_9"},{"issue":"6","key":"963_CR51","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1007\/s00778-019-00572-x","volume":"28","author":"T Zhang","year":"2019","unstructured":"Zhang, T., Gao, Y., Chen, L., Guo, W., Pu, S., Zheng, B., Jensen, C.S.: Efficient distributed reachability querying of massive temporal graphs. VLDB J. 28(6), 871\u2013896 (2019)","journal-title":"VLDB J."},{"key":"963_CR52","doi-asserted-by":"crossref","unstructured":"Zhu, K., Fletcher, G., Yakovets, N.: Leveraging temporal and topological selectivities in temporal-clique subgraph query processing. In ICDE, pages 672\u2013683, (2021)","DOI":"10.1109\/ICDE51399.2021.00064"},{"key":"963_CR53","doi-asserted-by":"crossref","unstructured":"Zhu, K., Fletcher, G., Yakovets, N., Papapetrou, O., Wu, Y.: Scalable temporal clique enumeration. In SSTD, (2019)","DOI":"10.1145\/3340964.3340987"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-026-00963-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-026-00963-x","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-026-00963-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T06:41:42Z","timestamp":1773038502000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-026-00963-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,26]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["963"],"URL":"https:\/\/doi.org\/10.1007\/s00778-026-00963-x","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,26]]},"assertion":[{"value":"26 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"13"}}