{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:11:03Z","timestamp":1779174663223,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:p>Regular path query (RPQ) is a basic operation for graph data analysis, and persistent RPQ in streaming graphs is a new-emerging research topic. In this paper, we propose a novel algorithm for persistent RPQ in streaming graphs, named LM-SRPQ. It solves persistent RPQ with a combination of intermediate result materialization and real-time graph traversal. Compared to prior art, it merges redundant storage and computation, achieving higher memory and time efficiency. We carry out extensive experiments with both real-world and synthetic streaming graphs to evaluate its performance. Experiment results confirm its superiority compared to prior art in both memory and time efficiency.<\/jats:p>","DOI":"10.14778\/3641204.3641214","type":"journal-article","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T22:05:43Z","timestamp":1714687543000},"page":"1047-1059","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Xiangyang","family":"Gou","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinyi","family":"Ye","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Zou","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,2]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.42731"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_6_1","volume-title":"The World Wide Web Conference. 127--138","author":"Bonifati Angela","year":"2019","unstructured":"Angela Bonifati, Wim Martens, and Thomas Timm. 2019. Navigating the maze of Wikidata query logs. In The World Wide Web Conference. 127--138."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3298989"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529348"},{"key":"e_1_2_1_9_1","volume-title":"A selectivity based approach to continuous pattern detection in streaming graphs. arXiv preprint arXiv:1503.00849","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. arXiv preprint arXiv:1503.00849 (2015)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/38714.38749"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_1_13_1","volume-title":"New Media Technologies and Semantic Systems","author":"Erling Orri","year":"2009","unstructured":"Orri Erling and Ivan Mikhailov. 2009. RDF Support in the Virtuoso DBMS. Networked Knowledge-Networked Media: Integrating Knowledge Management, New Media Technologies and Semantic Systems (2009), 7--24."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452800"},{"key":"e_1_2_1_15_1","volume-title":"Graph stream sketch: Summarizing graph streams with high speed and accuracy","author":"Gou Xiangyang","year":"2022","unstructured":"Xiangyang Gou, Lei Zou, Chenxingyu Zhao, and Tong Yang. 2022. Graph stream sketch: Summarizing graph streams with high speed and accuracy. IEEE Transactions on Knowledge and Data Engineering (2022)."},{"key":"e_1_2_1_16_1","volume-title":"Recservice: Distributed real-time graph processing at twitter. In 10th {USENIX} Workshop on Hot Topics in Cloud Computing (HotCloud 18).","author":"Grewal Ajeet","year":"2018","unstructured":"Ajeet Grewal, Jerry Jiang, Gary Lam, Tristan Jung, Lohith Vuddemarri, Quannan Li, Aaditya Landge, and Jimmy Lin. 2018. Recservice: Distributed real-time graph processing at twitter. In 10th {USENIX} Workshop on Hot Topics in Cloud Computing (HotCloud 18)."},{"key":"e_1_2_1_17_1","volume-title":"Theory of machines and computations","author":"Hopcroft John","unstructured":"John Hopcroft. 1971. An n log n algorithm for minimizing states in a finite automaton. In Theory of machines and computations. Elsevier, 189--196."},{"key":"e_1_2_1_18_1","volume-title":"Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong.","author":"Kim Kyoungmin","year":"2018","unstructured":"Kyoungmin Kim, In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong. 2018. Turboflux: A fast continuous subgraph matching system for streaming graph data. In Proceedings of the 2018 international conference on management of data. 411--426."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403074"},{"key":"e_1_2_1_20_1","volume-title":"The Semantic Web: Research and Applications: 4th European Semantic Web Conference, ESWC 2007, Innsbruck, Austria, June 3--7, 2007. Proceedings 4. Springer, 145--159","author":"Kochut Krys J","year":"2007","unstructured":"Krys J Kochut and Maciej Janik. 2007. SPARQLeR: Extended SPARQL for semantic association discovery. In The Semantic Web: Research and Applications: 4th European Semantic Web Conference, ESWC 2007, Innsbruck, Austria, June 3--7, 2007. Proceedings 4. Springer, 145--159."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_12"},{"key":"e_1_2_1_22_1","volume-title":"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."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_1_24_1","volume-title":"2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1675--1686","author":"Na Inju","year":"2022","unstructured":"Inju Na, Yang-Sae Moon, Ilyeop Yi, Kyu-Young Whang, and Soon J Hyun. 2022. Regular path query evaluation sharing a reduced transitive closure based on graph reduction. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1675--1686."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389733"},{"key":"e_1_2_1_26_1","volume-title":"2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 272--285","author":"Pacaci Anil","year":"2022","unstructured":"Anil Pacaci, Angela Bonifati, and M Tamer \u00d6zsu. 2022. Evaluating complex queries on streaming graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 272--285."},{"key":"e_1_2_1_27_1","volume-title":"Current Trends in Database Technology-EDBT 2006: EDBT 2006 Workshops PhD, DataX, IIDB, IIHA, ICSNW, QLQP, PIM, PaRMA, and Reactivity on the Web","author":"Patroumpas Kostas","year":"2006","unstructured":"Kostas Patroumpas and Timos Sellis. 2006. Window specification over data streams. In Current Trends in Database Technology-EDBT 2006: EDBT 2006 Workshops PhD, DataX, IIDB, IIHA, ICSNW, QLQP, PIM, PaRMA, and Reactivity on the Web, Munich, Germany, March 26--31, 2006, Revised Selected Papers 10. Springer, 445--464."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007387"},{"key":"e_1_2_1_31_1","volume-title":"Triest: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Transactions on Knowledge Discovery from Data (TKDD) 11, 4","author":"Stefani Lorenzo De","year":"2017","unstructured":"Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. 2017. Triest: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Transactions on Knowledge Discovery from Data (TKDD) 11, 4 (2017), 1--50."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319882"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149197"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data. 1875--1889","author":"Yakovets Nikolay","year":"2016","unstructured":"Nikolay Yakovets, Parke Godfrey, and Jarek Gryz. 2016. Query planning for evaluating SPARQL property paths. In Proceedings of the 2016 International Conference on Management of Data. 1875--1889."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3641204.3641214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T22:09:38Z","timestamp":1714687778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3641204.3641214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["10.14778\/3641204.3641214"],"URL":"https:\/\/doi.org\/10.14778\/3641204.3641214","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,1]]},"assertion":[{"value":"2024-05-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}