{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T18:55:24Z","timestamp":1778266524000,"version":"3.51.4"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-20-07556, CCF-22-23870, IIS-1814493, IIS-2008107"],"award-info":[{"award-number":["CCF-20-07556, CCF-22-23870, IIS-1814493, IIS-2008107"]}]},{"name":"US-Israel grant","award":["2022131"],"award-info":[{"award-number":["2022131"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Finding patterns in graphs is a fundamental problem in databases and data mining. In many applications, graphs are temporal and evolve over time, so we are interested in finding durable patterns, such as triangles and paths, which persist over a long time. While there has been work on finding durable simple patterns, existing algorithms do not have provable guarantees and run in strictly super-linear time. The paper leverages the observation that many graphs arising in practice are naturally proximity graphs or can be approximated as such, where nodes are embedded as points in some high-dimensional space, and two nodes are connected by an edge if they are close to each other. We work with an implicit representation of the proximity graph, where nodes are additionally annotated by time intervals, and design near-linear-time algorithms for finding (approximately) durable patterns above a given durability threshold. We also consider an interactive setting where a client experiments with different durability thresholds in a sequence of queries; we show how to compute incremental changes to result patterns efficiently in time near-linear to the size of the changes.<\/jats:p>","DOI":"10.1145\/3651144","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["On Reporting Durable Patterns in Temporal Proximity Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2114-8886","authenticated-orcid":false,"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0604-6790","authenticated-orcid":false,"given":"Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Doubling dimension in real-world graphs. https:\/\/slideplayer.com\/slide\/5331329\/. Accessed: 2023-04--24."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_3_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)","author":"Agarwal P. K.","year":"2021","unstructured":"P. K. Agarwal, X. Hu, S. Sintos, and J. Yang. Dynamic enumeration of similarity joins. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 2021."},{"key":"e_1_2_1_4_1","volume-title":"On reporting durable patterns in temporal proximity graphs. https: \/\/arxiv.org\/abs\/2403.16312","author":"Agarwal P. K.","year":"2024","unstructured":"P. K. Agarwal, X. Hu, S. Sintos, and J. Yang. On reporting durable patterns in temporal proximity graphs. https: \/\/arxiv.org\/abs\/2403.16312, 2024."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/07067917X"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-015-0847-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319701"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.003"},{"key":"e_1_2_1_12_1","volume-title":"A comprehensive survey of graph embedding: Problems, techniques, and applications","author":"Cai H.","year":"2018","unstructured":"H. Cai, V. W. Zheng, and K. C.-C. Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE transactions on knowledge and data engineering, 30(9):1616--1637, 2018."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116278.3116568"},{"key":"e_1_2_1_14_1","first-page":"410","volume-title":"Klee's measure problem made easy. In 2013 IEEE 54th annual symposium on foundations of computer science","author":"Chan T. M.","year":"2013","unstructured":"T. M. Chan. Klee's measure problem made easy. In 2013 IEEE 54th annual symposium on foundations of computer science, pages 410--419. IEEE, 2013."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch68"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00273-3"},{"key":"e_1_2_1_17_1","volume-title":"k-nearest neighbour classifiers-a tutorial. ACM computing surveys (CSUR), 54(6):1--25","author":"Cunningham P.","year":"2021","unstructured":"P. Cunningham and S. J. Delany. k-nearest neighbour classifiers-a tutorial. ACM computing surveys (CSUR), 54(6):1--25, 2021."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11945529_12"},{"key":"e_1_2_1_19_1","volume-title":"26th International Conference on Database Theory (ICDT 2023","author":"Deng S.","year":"2023","unstructured":"S. Deng, S. Lu, and Y. Tao. Space-query tradeoffs in range subgraph counting and listing. In 26th International Conference on Database Theory (ICDT 2023). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik, 2023."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009099950"},{"key":"e_1_2_1_21_1","volume-title":"Computational topology: an introduction","author":"Edelsbrunner H.","year":"2022","unstructured":"H. Edelsbrunner and J. L. Harer. Computational topology: an introduction. American Mathematical Society, 2022."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2830326.2830353"},{"key":"e_1_2_1_23_1","unstructured":"J. Erickson. Static-to-dynamic transformations. http:\/\/jeffe.cs.illinois.edu\/teaching\/datastructures\/notes\/01- statictodynamic.pdf."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-017-11873-y"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00683-w"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 21st International Conference on Extending Database Technology","author":"Franzke M.","year":"2018","unstructured":"M. Franzke, T. Emrich, A. Z\u00fcfle, and M. Renz. Pattern search in temporal social networks. In Proceedings of the 21st International Conference on Extending Database Technology, 2018."},{"issue":"13","key":"e_1_2_1_27_1","first-page":"2223","article-title":"Durable top-k queries on temporal data","volume":"11","author":"Gao J.","year":"2018","unstructured":"J. Gao, P. K. Agarwal, and J. Yang. Durable top-k queries on temporal data. Proceedings of the VLDB Endowment, 11(13):2223--2235, 2018.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00068"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457305"},{"key":"e_1_2_1_30_1","volume-title":"Community detection in dynamic social networks based on multiobjective immune algorithm. Journal of computer science and technology, 27(3):455--467","author":"Gong M.-G.","year":"2012","unstructured":"M.-G. Gong, L.-J. Zhang, J.-J. Ma, and L.-C. Jiao. Community detection in dynamic social networks based on multiobjective immune algorithm. Journal of computer science and technology, 27(3):455--467, 2012."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064117"},{"key":"e_1_2_1_32_1","first-page":"94","volume-title":"Approximation algorithms for NP-hard problems","author":"Hochbaum D. S.","year":"1996","unstructured":"D. S. Hochbaum. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In Approximation algorithms for NP-hard problems, pages 94--143. 1996."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517893"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803390"},{"key":"e_1_2_1_36_1","volume-title":"27th Annual European Symposium on Algorithms (ESA 2019","author":"Kaplan H.","year":"2019","unstructured":"H. Kaplan, K. Klost,W. Mulzer, L. Roditty, P. Seiferth, and M. Sharir. Triangles and girth in disk graphs and transmission graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019."},{"key":"e_1_2_1_37_1","first-page":"364","volume-title":"Proceedings, Part II 10","author":"Kumar N.","year":"2008","unstructured":"N. Kumar, L. Zhang, and S. Nayar. What is a good nearest neighbors algorithm for finding similar patches in images? In Computer Vision--ECCV 2008: 10th European Conference on Computer Vision, Marseille, France, October 12--18, 2008, Proceedings, Part II 10, pages 364--378. Springer, 2008."},{"key":"e_1_2_1_38_1","first-page":"3349","volume-title":"ACL 2019--57th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference","author":"Kutuzov A.","year":"2020","unstructured":"A. Kutuzov, M. Dorgham, O. Oliynyk, C. Biemann, and A. Panchenko. Making fast graph-based algorithms with graph metric embeddings. In ACL 2019--57th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 3349--3355, 2020."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367590"},{"key":"e_1_2_1_40_1","first-page":"675","volume-title":"Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020","author":"Locicero G.","year":"2021","unstructured":"G. Locicero, G. Micale, A. Pulvirenti, and A. Ferro. Temporalri: a subgraph isomorphism algorithm for temporal networks. In Complex Networks & Their Applications IX: Volume 2, Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020, pages 675--687. Springer, 2021."},{"key":"e_1_2_1_41_1","volume-title":"Spinger","author":"Mark B.","year":"2008","unstructured":"d. B. Mark, C. Otfried, v. K. Marc, and O. Mark. Computational geometry algorithms and applications. Spinger, 2008."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019258"},{"key":"e_1_2_1_43_1","volume-title":"Worst-case optimal join algorithms. Journal of the ACM (JACM), 65(3):1--40","author":"Ngo H. Q.","year":"2018","unstructured":"H. Q. Ngo, E. Porat, C. R\u00e9, and A. Rudra. Worst-case optimal join algorithms. Journal of the ACM (JACM), 65(3):1--40, 2018."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90093-4"},{"key":"e_1_2_1_45_1","volume-title":"Springer Science & Business Media","author":"Overmars M. H.","year":"1987","unstructured":"M. H. Overmars. The design of dynamic data structures, volume 156. Springer Science & Business Media, 1987."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_1_47_1","volume-title":"9th International Conference on Learning Representations, ICLR 2021","author":"Pope P.","year":"2021","unstructured":"P. Pope, C. Zhu, A. Abdelkader, M. Goldblum, and T. Goldstein. The intrinsic dimension of images and its impact on learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3--7, 2021, 2021."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498269"},{"key":"e_1_2_1_49_1","volume-title":"d. Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319--2323","author":"Tenenbaum J. B.","year":"2000","unstructured":"J. B. Tenenbaum, V. d. Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319--2323, 2000."},{"key":"e_1_2_1_50_1","volume-title":"Proc. International Conference on Database Theory","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory, 2014."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582139"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939848"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00056"},{"key":"e_1_2_1_55_1","volume-title":"Orion: shortest path estimation for large social graphs. networks, 1:5","author":"Zhao X.","year":"2010","unstructured":"X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Y. Zhao. Orion: shortest path estimation for large social graphs. networks, 1:5, 2010."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.collaboratecom.2011.247162"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651144","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:18Z","timestamp":1755898758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651144"],"URL":"https:\/\/doi.org\/10.1145\/3651144","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}