{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:44Z","timestamp":1775638484756,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:p>In many real datasets such as social media streams and cyber data sources, graphs change over time through a graph update stream of edge insertions and deletions. Detecting critical patterns in such dynamic graphs plays an important role in various application domains such as fraud detection, cyber security, and recommendation systems for social networks. Given a dynamic data graph and a query graph, the continuous subgraph matching problem is to find all positive matches for each edge insertion and all negative matches for each edge deletion. The state-of-the-art algorithm TurboFlux uses a spanning tree of a query graph for filtering. However, using the spanning tree may have a low pruning power because it does not take into account all edges of the query graph. In this paper, we present a symmetric and much faster algorithm SymBi which maintains an auxiliary data structure based on a directed acyclic graph instead of a spanning tree, which maintains the intermediate results of bidirectional dynamic programming between the query graph and the dynamic graph. Extensive experiments with real and synthetic datasets show that SymBi outperforms the state-of-the-art algorithm by up to three orders of magnitude in terms of the elapsed time.<\/jats:p>","DOI":"10.14778\/3457390.3457395","type":"journal-article","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T22:48:38Z","timestamp":1634856518000},"page":"1298-1310","source":"Crossref","is-referenced-by-count":25,"title":["Symmetric continuous subgraph matching with bidirectional dynamic programming"],"prefix":"10.14778","volume":"14","author":[{"given":"Seunghwan","family":"Min","sequence":"first","affiliation":[{"name":"Seoul National University"}]},{"given":"Sung Gwan","family":"Park","sequence":"additional","affiliation":[{"name":"Seoul National University"}]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[{"name":"Seoul National University"}]},{"given":"Dora","family":"Giammarresi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 Roma \"Tor Vergata\""}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[{"name":"LUISS University"}]},{"given":"Wook-Shin","family":"Han","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology (POSTECH)"}]}],"member":"320","published-online":{"date-parts":[[2021,10,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2743075"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_4_1","volume-title":"The CAIDA UCSD Anonymized Internet Traces","author":"CAIDA.","year":"2013","unstructured":"CAIDA. 2013. The CAIDA UCSD Anonymized Internet Traces 2013 . Retrieved September 3, 2020 from https:\/\/www.caida.org\/data\/passive\/passive_2013_dataset.xml. CAIDA. 2013. The CAIDA UCSD Anonymized Internet Traces 2013. Retrieved September 3, 2020 from https:\/\/www.caida.org\/data\/passive\/passive_2013_dataset.xml."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.67"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 18th International Conference on Extending Database Technology. 157--168","author":"Choudhury Sutanay","year":"2015","unstructured":"Sutanay Choudhury , Lawrence Holder , George Chin , Khushbu Agarwal , and John Feo . 2015 . A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs . In Proceedings of the 18th International Conference on Extending Database Technology. 157--168 . Sutanay Choudhury, Lawrence Holder, George Chin, Khushbu Agarwal, and John Feo. 2015. A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs. In Proceedings of the 18th International Conference on Extending Database Technology. 157--168."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463697"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380585"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0416-z"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816681"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484428"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196917"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323322"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35173-0_20"},{"key":"e_1_2_1_22_1","volume-title":"Time Constrained Continuous Subgraph Search Over Streaming Graphs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1082--1093","author":"Li Youhuan","year":"2019","unstructured":"Youhuan Li , Lei Zou , M. Tamer \u00d6zsu , and Dongyan Zhao . 2019 . Time Constrained Continuous Subgraph Search Over Streaming Graphs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1082--1093 . Youhuan Li, Lei Zou, M. Tamer \u00d6zsu, and Dongyan Zhao. 2019. Time Constrained Continuous Subgraph Search Over Streaming Graphs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1082--1093."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_1_25_1","volume-title":"Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, and Wook-Shin Han.","author":"Min Seunghwan","year":"2021","unstructured":"Seunghwan Min , Sung Gwan Park , Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, and Wook-Shin Han. 2021 . Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming ( full version). arXiv:2104.00886. Seunghwan Min, Sung Gwan Park, Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, and Wook-Shin Han. 2021. Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming (full version). arXiv:2104.00886."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612182"},{"key":"e_1_2_1_27_1","volume-title":"BEAMS: Bounded Event Detection in Graph Streams. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 1387--1388","author":"Namaki Mohammad Hossein","year":"2017","unstructured":"Mohammad Hossein Namaki , Keyvan Sasani , Yinghui Wu , and Tingjian Ge . 2017 . BEAMS: Bounded Event Detection in Graph Streams. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 1387--1388 . Mohammad Hossein Namaki, Keyvan Sasani, Yinghui Wu, and Tingjian Ge. 2017. BEAMS: Bounded Event Detection in Graph Streams. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 1387--1388."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541290"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0968-2"},{"key":"e_1_2_1_33_1","volume-title":"Fraud Detection: Discovering Connections with Graph Databases. White Paper-Neo Technology-Graphs are Everywhere 13","author":"Sadowski Gorka","year":"2014","unstructured":"Gorka Sadowski and Philip Rathle . 2014 . Fraud Detection: Discovering Connections with Graph Databases. White Paper-Neo Technology-Graphs are Everywhere 13 (2014). Gorka Sadowski and Philip Rathle. 2014. Fraud Detection: Discovering Connections with Graph Databases. White Paper-Neo Technology-Graphs are Everywhere 13 (2014)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735504"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915223"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_39_1","volume-title":"Data Breach Investigations Report. Retrieved","year":"2020","unstructured":"Verizon. 2020. Data Breach Investigations Report. Retrieved September 3, 2020 from https:\/\/enterprise.verizon.com\/resources\/reports\/2020-data-breach-investigations-report.pdf. Verizon. 2020. Data Breach Investigations Report. Retrieved September 3, 2020 from https:\/\/enterprise.verizon.com\/resources\/reports\/2020-data-breach-investigations-report.pdf."},{"key":"e_1_2_1_40_1","volume-title":"Efficient Continuous Multi-Query Processing over Graph Streams. arXiv preprint arXiv:1902.05134","author":"Zervakis Lefteris","year":"2019","unstructured":"Lefteris Zervakis , Vinay Setty , Christos Tryfonopoulos , and Katja Hose . 2019. Efficient Continuous Multi-Query Processing over Graph Streams. arXiv preprint arXiv:1902.05134 ( 2019 ). Lefteris Zervakis, Vinay Setty, Christos Tryfonopoulos, and Katja Hose. 2019. Efficient Continuous Multi-Query Processing over Graph Streams. arXiv preprint arXiv:1902.05134 (2019)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358101"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3457390.3457395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:45:27Z","timestamp":1672224327000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3457390.3457395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4]]},"references-count":42,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10.14778\/3457390.3457395"],"URL":"https:\/\/doi.org\/10.14778\/3457390.3457395","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,4]]}}}