{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T13:00:38Z","timestamp":1793710838197,"version":"4.6.1"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,5,31]],"date-time":"2020-05-31T00:00:00Z","timestamp":1590883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Waterloo-Huawei Joint Innovation Lab"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,11]]},"DOI":"10.1145\/3318464.3389733","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T17:12:33Z","timestamp":1590772353000},"page":"1415-1430","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["Regular Path Query Evaluation on Streaming Graphs"],"prefix":"10.1145","author":[{"given":"Anil","family":"Pacaci","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Angela","family":"Bonifati","sequence":"additional","affiliation":[{"name":"Lyon 1 University, Villeurbanne, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Proc. 2nd Biennial Conf. on Innovative Data Systems Research. 277--289","author":"Abadi Daniel J.","unstructured":"Daniel J. Abadi , Yanif Ahmad , Magdalena Balazinska , Ugur c Cetintemel , Mitch Cherniack , Jeong-Hyon Hwang , Wolfgang Lindner , Anurag Maskey , Alex Rasin , Esther Ryvkina , Nesime Tatbul , Ying Xing , and Stanley B. Zdonik . 2005. The Design of the Borealis Stream Processing Engine . In Proc. 2nd Biennial Conf. on Innovative Data Systems Research. 277--289 . Daniel J. Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur cCetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag Maskey, Alex Rasin, Esther Ryvkina, Nesime Tatbul, Ying Xing, and Stanley B. Zdonik. 2005. The Design of the Borealis Stream Processing Engine. In Proc. 2nd Biennial Conf. on Innovative Data Systems Research. 277--289."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.42731"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963495"},{"key":"e_1_3_2_2_7_1","first-page":"121","article-title":"The CQL Continuous Query Language","volume":"15","author":"Arasu A.","year":"2006","unstructured":"A. Arasu , S. Babu , and J. Widom . 2006 . The CQL Continuous Query Language : Semantic Foundations and Query Execution. VLDB J. , Vol. 15 , 2 (2006), 121 -- 142 . A. Arasu, S. Babu, and J. Widom. 2006. The CQL Continuous Query Language: Semantic Foundations and Query Execution. VLDB J., Vol. 15, 2 (2006), 121--142.","journal-title":"Semantic Foundations and Query Execution. VLDB J."},{"key":"e_1_3_2_2_8_1","volume-title":"Proc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems. 1--16","author":"Babcock B.","unstructured":"B. Babcock , S. Babu , M. Datar , R. Motwani , and J. Widom . 2002. Models and Issues in Data Stream Systems . In Proc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems. 1--16 . B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. 2002. Models and Issues in Data Stream Systems. In Proc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems. 1--16."},{"key":"e_1_3_2_2_9_1","volume-title":"Proc. 32nd ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 175--188","author":"Baeza Pablo Barcel\u00f3","year":"2013","unstructured":"Pablo Barcel\u00f3 Baeza . 2013 . Querying graph databases . In Proc. 32nd ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 175--188 . Pablo Barcel\u00f3 Baeza. 2013. Querying graph databases. In Proc. 32nd ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 175--188."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2633993"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2467795"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526856"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938670"},{"key":"e_1_3_2_2_14_1","volume-title":"Proc. 18th Int. Conf. on Extending Database Technology","author":"Bonifati Angela","year":"2015","unstructured":"Angela Bonifati , Radu Ciucanu , and Aur\u00e9lien Lemay . 2015 . Learning Path Queries on Graph Databases . In Proc. 18th Int. Conf. on Extending Database Technology . Bruxelles, Belgium, 109--120. https:\/\/doi.org\/10.5441\/002\/edbt. 2015.11 Angela Bonifati, Radu Ciucanu, and Aur\u00e9lien Lemay. 2015. Learning Path Queries on Graph Databases. In Proc. 18th Int. Conf. on Extending Database Technology. Bruxelles, Belgium, 109--120. https:\/\/doi.org\/10.5441\/002\/edbt.2015.11"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00873ED1V01Y201808DTM051"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149196"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_3_2_2_18_1","unstructured":"Jean-Paul Calbimonte. 2017. Linked Data Notifications for RDF Streams.. In WSP\/WOMoCoE@ ISWC. 66--73.  Jean-Paul Calbimonte. 2017. Linked Data Notifications for RDF Streams.. In WSP\/WOMoCoE@ ISWC. 66--73."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17746-0_7"},{"key":"e_1_3_2_2_20_1","volume-title":"Proc. 19th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 58--66","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , and Moshe Y Vardi . 2000 . Query processing using views for regular path queries with inverse . In Proc. 19th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 58--66 . Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y Vardi. 2000. Query processing using views for regular path queries with inverse. In Proc. 19th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 58--66."},{"key":"e_1_3_2_2_21_1","first-page":"28","article-title":"Apache Flink#8482;: Stream and Batch Processing in a Single Engine","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone , Asterios Katsifodimos , Stephan Ewen , Volker Markl , Seif Haridi , and Kostas Tzoumas . 2015 . Apache Flink#8482;: Stream and Batch Processing in a Single Engine . Q. Bull. IEEE TC on Data Eng. , Vol. 38 , 4 (2015), 28 -- 38 . http:\/\/sites.computer.org\/debull\/A15dec\/p28.pdf Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink#8482;: Stream and Batch Processing in a Single Engine. Q. Bull. IEEE TC on Data Eng., Vol. 38, 4 (2015), 28--38. http:\/\/sites.computer.org\/debull\/A15dec\/p28.pdf","journal-title":"Q. Bull. IEEE TC on Data Eng."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/38714.38749"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25639-9_48"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Orri Erling and Ivan Mikhailov. 2009. RDF Support in the Virtuoso DBMS. In Networked Knowledge-Networked Media Tassilo Pellegrini S\u00f3ren Auer Klaus Tochtermann and Sebastian Schaffert (Eds.). 7--24.  Orri Erling and Ivan Mikhailov. 2009. RDF Support in the Virtuoso DBMS. In Networked Knowledge-Networked Media Tassilo Pellegrini S\u00f3ren Auer Klaus Tochtermann and Sebastian Schaffert (Eds.). 7--24.","DOI":"10.1007\/978-3-642-02184-8_2"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. 19th Int. Conf. on Extending Database Technology, Evaggelia Pitoura, Sofian Maabout, Georgia Koutrika, Am\u00e9 lie Marian, Letizia Tanca, Ioana Manolescu, and Kostas Stefanidis (Eds.). 636--639","author":"Fletcher George H. L.","year":"2016","unstructured":"George H. L. Fletcher , Jeroen Peters , and Alexandra Poulovassilis . 2016 . Efficient regular path query evaluation using path indexes . In Proc. 19th Int. Conf. on Extending Database Technology, Evaggelia Pitoura, Sofian Maabout, Georgia Koutrika, Am\u00e9 lie Marian, Letizia Tanca, Ioana Manolescu, and Kostas Stefanidis (Eds.). 636--639 . https:\/\/doi.org\/10.5441\/002\/edbt.2016.67 George H. L. Fletcher, Jeroen Peters, and Alexandra Poulovassilis. 2016. Efficient regular path query evaluation using path indexes. In Proc. 19th Int. Conf. on Extending Database Technology, Evaggelia Pitoura, Sofian Maabout, Georgia Koutrika, Am\u00e9 lie Marian, Letizia Tanca, Ioana Manolescu, and Kostas Stefanidis (Eds.). 636--639. https:\/\/doi.org\/10.5441\/002\/edbt.2016.67"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3208352.3208355"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066232"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Lukasz Golab and M. Tamer \u00d6zsu. 2010. Data Stream Systems .Morgan & Claypool.  Lukasz Golab and M. Tamer \u00d6zsu. 2010. Data Stream Systems .Morgan & Claypool.","DOI":"10.1007\/978-0-387-39940-9_113"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36285-1_12"},{"key":"e_1_3_2_2_35_1","volume-title":"Proc. 10th USENIX Workshop on Hot Topics in Cloud Computing .","author":"Grewal Ajeet","unstructured":"Ajeet Grewal , Jerry Jiang , Gary Lam , Tristan Jung , Lohith Vuddemarri , Quannan Li , Aaditya Landge , and Jimmy Lin . [n. d.]. RecService : Multi-Tenant Distributed Real-Time Graph Processing at Twitter . In Proc. 10th USENIX Workshop on Hot Topics in Cloud Computing . Ajeet Grewal, Jerry Jiang, Gary Lam, Tristan Jung, Lohith Vuddemarri, Quannan Li, Aaditya Landge, and Jimmy Lin. [n. d.]. RecService: Multi-Tenant Distributed Real-Time Graph Processing at Twitter. In Proc. 10th USENIX Workshop on Hot Topics in Cloud Computing ."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484443"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299887.3299892"},{"key":"e_1_3_2_2_39_1","volume-title":"An n log n algorithm for minimizing states in a finite automaton","author":"Hopcroft John","unstructured":"John Hopcroft . 1971. An n log n algorithm for minimizing states in a finite automaton . Elsevier Science Publishers , 189--196. John Hopcroft. 1971. An n log n algorithm for minimizing states in a finite automaton. Elsevier Science Publishers, 189--196."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Bruce M Kapron Valerie King and Ben Mountjoy. 2013. Dynamic graph connectivity in polylogarithmic worst case time. 1131--1142.  Bruce M Kapron Valerie King and Ben Mountjoy. 2013. Dynamic graph connectivity in polylogarithmic worst case time. 1131--1142.","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72667-8_12"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2335484.2335491"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e9 Koschmieder and Ulf Leser. 2012. Regular path queries on large graphs. In SSDBM12. 177--194.  Andr\u00e9 Koschmieder and Ulf Leser. 2012. Regular path queries on large graphs. In SSDBM12. 177--194.","DOI":"10.1007\/978-3-642-31235-9_12"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742788"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Jakub \u0141ka cki. 2011. Improved deterministic algorithms for decremental transitive closure and strongly connected components. 1438--1445.  Jakub \u0141ka cki. 2011. Improved deterministic algorithms for decremental transitive closure and strongly connected components. 1438--1445.","DOI":"10.1137\/1.9781611973082.111"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25073-6_24"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274585"},{"key":"e_1_3_2_2_49_1","volume-title":"Enumeration problems for regular path queries. arXiv preprint arXiv:1710.02317","author":"Martens Wim","year":"2017","unstructured":"Wim Martens and Tina Trautner . 2017. Enumeration problems for regular path queries. arXiv preprint arXiv:1710.02317 ( 2017 ). Wim Martens and Tina Trautner. 2017. Enumeration problems for regular path queries. arXiv preprint arXiv:1710.02317 (2017)."},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46547-0_15"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_3_2_2_54_1","volume-title":"Regular Path Query Evaluation on Streaming Graphs. arXiv preprint arXiv:2004.02012","author":"Pacaci Anil","year":"2020","unstructured":"Anil Pacaci , Angela Bonifati , and M. Tamer \u00d6zsu . 2020. Regular Path Query Evaluation on Streaming Graphs. arXiv preprint arXiv:2004.02012 ( 2020 ). Anil Pacaci, Angela Bonifati, and M. Tamer \u00d6zsu. 2020. Regular Path Query Evaluation on Streaming Graphs. arXiv preprint arXiv:2004.02012 (2020)."},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078447.3078459"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_3_2_2_57_1","volume-title":"Proc. 10th Int. Conf. on Extending Database Technology. 445--464","author":"Patroumpas Kostas","year":"2006","unstructured":"Kostas Patroumpas and Timos Sellis . 2006 . Window specification over data streams. In Advances in Database Technology , Proc. 10th Int. Conf. on Extending Database Technology. 445--464 . Kostas Patroumpas and Timos Sellis. 2006. Window specification over data streams. In Advances in Database Technology, Proc. 10th Int. Conf. on Extending Database Technology. 445--464."},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/13093618X"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_3_2_2_61_1","volume-title":"Proc. 29th Int. Conf. on Data Engineering. 1009--1020","author":"Seufert S.","year":"2013","unstructured":"S. Seufert , A. Anand , S. Bedathur , and G. Weikum . 2013. FERRARI: Flexible and efficient reachability range assignment for graph indexing . In Proc. 29th Int. Conf. on Data Engineering. 1009--1020 . https:\/\/doi.org\/10.1109\/ICDE. 2013 .6544893 S. Seufert, A. Anand, S. Bedathur, and G. Weikum. 2013. FERRARI: Flexible and efficient reachability range assignment for graph indexing. In Proc. 29th Int. Conf. on Data Engineering. 1009--1020. https:\/\/doi.org\/10.1109\/ICDE.2013.6544893"},{"key":"e_1_3_2_2_62_1","unstructured":"Andy Seaborne Steve Harris. [n. d.]. SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/  Andy Seaborne Steve Harris. [n. d.]. SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_3_2_2_64_1","volume-title":"Programming techniques: Regular expression search algorithm","author":"Thompson Ken","year":"1968","unstructured":"Ken Thompson . 1968. Programming techniques: Regular expression search algorithm ., Vol. 11 , 6 ( 1968 ), 419--422. Ken Thompson. 1968. Programming techniques: Regular expression search algorithm., Vol. 11, 6 (1968), 419--422."},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595641"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_3_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319882"},{"key":"e_1_3_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882944"},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35176-1_40"}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA","acronym":"SIGMOD\/PODS '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3389733","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3318464.3389733","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:44Z","timestamp":1750199924000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3389733"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,31]]},"references-count":69,"alternative-id":["10.1145\/3318464.3389733","10.1145\/3318464"],"URL":"https:\/\/doi.org\/10.1145\/3318464.3389733","relation":{},"subject":[],"published":{"date-parts":[[2020,5,31]]},"assertion":[{"value":"2020-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}