{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:59:02Z","timestamp":1781326742344,"version":"3.54.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/100017055","name":"National Natural Science Foundation of China-Shandong Joint Fund","doi-asserted-by":"publisher","award":["U24A20232"],"award-info":[{"award-number":["U24A20232"]}],"id":[{"id":"10.13039\/100017055","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62272106"],"award-info":[{"award-number":["62272106"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Persistent Regular Path Query (RPQ) on streaming graphs is widely applicable to many online analysis applications. Existing research primarily focuses on the single-worker scenario, while scaling out to distributed RPQ processing on multiple workers is desirable when facing a high workload. Existing distributed solutions are designed for general streaming queries, and various bottlenecks exist that significantly limit the performance when performing streaming RPQ evaluation. The challenge is how to execute queries with multiple workers while introducing limited overhead and ensuring sufficient speedup as the number of workers increases.<\/jats:p>\n                  <jats:p>This paper introduces a distributed processing strategy called DRPQ by carefully dividing a query into multiple partially matched query tasks. The idea is to form query tasks based on initial matches of the graph against the given regular expression, and to dynamically distribute these tasks to workers to balance their workloads. To reduce redundant evaluation across different workers, a grouping method is proposed to find query tasks that are likely to share evaluation processes, and send them to the same workers. Extensive experiments on two real-world graph datasets demonstrate that DRPQ is significantly more efficient and scalable than existing distributed solutions. Furthermore, the proposed grouping method proves to be particularly effective, nearly doubling the throughput in most cases.<\/jats:p>","DOI":"10.1145\/3769782","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1770-9013","authenticated-orcid":false,"given":"Siyuan","family":"Zhang","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7518-5466","authenticated-orcid":false,"given":"Kai","family":"Zhang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2926-4814","authenticated-orcid":false,"given":"Zhenying","family":"He","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1169-8032","authenticated-orcid":false,"given":"Yinan","family":"Jing","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-8587","authenticated-orcid":false,"given":"Zhigang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9059-3713","authenticated-orcid":false,"given":"X. Sean","family":"Wang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236208"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-19433-7_41"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963495"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457256"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00277"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526856"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems. 175-188","author":"Baeza Pablo Barcel\u00f3","year":"2013","unstructured":"Pablo Barcel\u00f3 Baeza. 2013. Querying graph databases. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems. 175-188."},{"key":"e_1_2_1_11_1","volume-title":"Navigating the Maze of Wikidata Query Logs. the web conference","author":"Bonifati Angela","year":"2019","unstructured":"Angela Bonifati, Wim Martens, and Thomas Timm. 2019. Navigating the Maze of Wikidata Query Logs. the web conference (2019)."},{"key":"e_1_2_1_12_1","unstructured":"Jean-Paul Calbimonte. 2017. Linked data notifications for rdf streams. In Proceedings of the Web Stream Processing workshop (WSP 2017) and the 2nd International Workshop on Ontology Modularity Contextuality and Evolution (WOMoCoE 2017) co-located with 16th International Semantic Web Conference (ISWC 2017). 22 October 2017."},{"key":"e_1_2_1_13_1","volume-title":"ISWC 2010","author":"Calbimonte Jean-Paul","year":"2010","unstructured":"Jean-Paul Calbimonte, Oscar Corcho, and Alasdair JG Gray. 2010. Enabling ontology-based access to streaming data sources. In The Semantic Web-ISWC 2010: 9th International Semantic Web Conference, ISWC 2010, Shanghai, China, November 7-11, 2010, Revised Selected Papers, Part I 9. Springer, 96-111."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3298989"},{"key":"e_1_2_1_15_1","unstructured":"Xin Chen You Peng Sibo Wang and Jeffrey Xu. [n.d.]. DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs. ([n.d.])."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_17_1","volume-title":"A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs. Extending Database Technology,Extending Database Technology (Feb","author":"Choudhury Sutanay","year":"2015","unstructured":"Sutanay Choudhury, LawrenceB. Holder, George Chin, Khushbu Agarwal, and John Feo. 2015. A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs. Extending Database Technology,Extending Database Technology (Feb 2015)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/38714.38749"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2457317.2457353"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02184-8_2"},{"key":"e_1_2_1_21_1","volume-title":"PathFinder: Returning Paths in Graph Queries. In International Semantic Web Conference. Springer, 135-154","author":"Far\u00edas Benjam\u00edn","year":"2024","unstructured":"Benjam\u00edn Far\u00edas, Wim Martens, Carlos Rojas, and Domagoj Vrgo\u010d. 2024. PathFinder: Returning Paths in Graph Queries. In International Semantic Web Conference. Springer, 135-154."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-190365"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_2_1_24_1","first-page":"17","volume-title":"10th USENIX symposium on operating systems design and implementation (OSDI 12)","author":"Gonzalez Joseph E","year":"2012","unstructured":"Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. {PowerGraph}: Distributed {Graph-Parallel} Computation on Natural Graphs. In 10th USENIX symposium on operating systems design and implementation (OSDI 12). 17-30."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3641204.3641214"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452800"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592799"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380567"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-015-0375-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196917"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72667-8_12"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2335484.2335491"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_12"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-023-00742-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25073-6_24"},{"key":"e_1_2_1_37_1","volume-title":"Graph summarization methods and applications: A survey. ACM computing surveys (CSUR)","author":"Liu Yike","year":"2018","unstructured":"Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph summarization methods and applications: A survey. ACM computing surveys (CSUR), Vol. 51, 3 (2018), 1-34."},{"key":"e_1_2_1_38_1","volume-title":"Representing paths in graph database pattern matching. arXiv preprint arXiv:2207.13541","author":"Martens Wim","year":"2022","unstructured":"Wim Martens, Matthias Niewerth, Tina Popp, Stijn Vansummeren, and Domagoj Vrgoc. 2022. Representing paths in graph database pattern matching. arXiv preprint arXiv:2207.13541 (2022)."},{"key":"e_1_2_1_39_1","unstructured":"Kento Miura Toshiyuki Amagasa Hiroyuki Kitagawa R Bordawekar and T Lahiri. 2019. Accelerating Regular Path Queries using FPGA.. In ADMS@ VLDB. 47-54."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00171"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.2017EDL8060"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2949689.2949711"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274399"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389733"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00025"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654955"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the European Semantic Web Conference. 583-596","author":"Tanon Thomas Pellissier","unstructured":"Thomas Pellissier Tanon, Gerhard Weikum, and F Yago Suchanek. [n.d.]. 4: A reason-able knowledge base. In Proceedings of the European Semantic Web Conference. 583-596."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13222-020-00353-9"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319882"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983877"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"e_1_2_1_58_1","volume-title":"AMW","volume":"1087","author":"Yakovets Nikolay","year":"2013","unstructured":"Nikolay Yakovets, Parke Godfrey, and Jarek Gryz. 2013. Evaluation of SPARQL Property Paths via Recursive SQL. AMW, Vol. 1087 (2013)."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639260"},{"key":"e_1_2_1_60_1","first-page":"641","volume-title":"USA","author":"Zhang Ying","year":"2012","unstructured":"Ying Zhang, Pham Minh Duc, Oscar Corcho, and Jean-Paul Calbimonte. 2012. SRBench: a streaming RDF\/SPARQL benchmark. In The Semantic Web-ISWC 2012: 11th International Semantic Web Conference, Boston, MA, USA, November 11-15, 2012, Proceedings, Part I 11. Springer, 641-657."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769782","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:51:10Z","timestamp":1781326270000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":61,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769782"],"URL":"https:\/\/doi.org\/10.1145\/3769782","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}