{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:52:18Z","timestamp":1773939138205,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,14]],"date-time":"2020-06-14T00:00:00Z","timestamp":1592092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","award":["19-37-90101"],"award-info":[{"award-number":["19-37-90101"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,14]]},"DOI":"10.1145\/3398682.3399163","type":"proceedings-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T19:25:57Z","timestamp":1591730757000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Context-Free Path Querying with Single-Path Semantics by Matrix Multiplication"],"prefix":"10.1145","author":[{"given":"Arseniy","family":"Terekhov","sequence":"first","affiliation":[{"name":"Saint Petersburg State University, St. Petersburg, Russia"}]},{"given":"Artyom","family":"Khoroshev","sequence":"additional","affiliation":[{"name":"ITMO University, St. Petersburg, Russia"}]},{"given":"Rustam","family":"Azimov","sequence":"additional","affiliation":[{"name":"Saint Petersburg State University, St. Petersburg, Russia, JetBrains Research, St. Petersburg, Russia"}]},{"given":"Semyon","family":"Grigorev","sequence":"additional","affiliation":[{"name":"Saint Petersburg State University, St. Petersburg, Russia, JetBrains Research, St. Petersburg, Russia"}]}],"member":"320","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Foundations of Databases: The Logical Level","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases: The Logical Level ( 1 st ed.). Addison-Wesley Longman Publishing Co., Inc. , USA. Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases: The Logical Level (1st ed.). Addison-Wesley Longman Publishing Co., Inc., USA.","edition":"1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210259.3210264"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_3_2_1_4_1","volume-title":"Foundations of Software Science and Computation Structures, Javier Esparza and Andrzej S","author":"Bouyer Patricia","unstructured":"Patricia Bouyer and Vincent Jug\u00e9 . 2017. Dynamic Complexity of the Dyck Reachability . In Foundations of Software Science and Computation Structures, Javier Esparza and Andrzej S . Murawski (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 265--280. Patricia Bouyer and Vincent Jug\u00e9. 2017. Dynamic Complexity of the Dyck Reachability. In Foundations of Software Science and Computation Structures, Javier Esparza and Andrzej S. Murawski (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 265--280."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1981242.1981245"},{"key":"e_1_3_2_1_6_1","volume-title":"Electronics & Mobile Communication Conference (UEMCON). IEEE, 1--7.","author":"Bradford Phillip G","year":"2016","unstructured":"Phillip G Bradford and Venkatesh Choppella . 2016 . Fast point-to-point Dyck constrained shortest paths on a DAG. In 2016 IEEE 7th Annual Ubiquitous Computing , Electronics & Mobile Communication Conference (UEMCON). IEEE, 1--7. Phillip G Bradford and Venkatesh Choppella. 2016. Fast point-to-point Dyck constrained shortest paths on a DAG. In 2016 IEEE 7th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON). IEEE, 1--7."},{"key":"e_1_3_2_1_7_1","volume-title":"RedisGraph GraphBLAS Enabled Graph Database. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 285--286","author":"Cailliau P.","year":"2019","unstructured":"P. Cailliau , T. Davis , V. Gadepally , J. Kepner , R. Lipman , J. Lovitz , and K. Ouaknine . 2019 . RedisGraph GraphBLAS Enabled Graph Database. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 285--286 . https:\/\/doi.org\/10.1109\/IPDPSW. 2019 .00054 10.1109\/IPDPSW.2019.00054 P. Cailliau, T. Davis, V. Gadepally, J. Kepner, R. Lipman, J. Lovitz, and K. Ouaknine. 2019. RedisGraph GraphBLAS Enabled Graph Database. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 285--286. https:\/\/doi.org\/10.1109\/IPDPSW.2019.00054"},{"key":"e_1_3_2_1_8_1","volume-title":"Cusp: Generic Parallel Algorithms for Sparse Matrix and Graph Computations","author":"Dalton Steven","year":"2014","unstructured":"Steven Dalton , Nathan Bell , Luke Olson , and Michael Garland . 2014 . Cusp: Generic Parallel Algorithms for Sparse Matrix and Graph Computations . http:\/\/cusplibrary.github.io\/ Version 0.5.0. Steven Dalton, Nathan Bell, Luke Olson, and Michael Garland. 2014. Cusp: Generic Parallel Algorithms for Sparse Matrix and Graph Computations. http:\/\/cusplibrary.github.io\/ Version 0.5.0."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322125"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304621"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3166094.3166104"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of ICDT'14","author":"Hellings Jelle","year":"2014","unstructured":"Jelle Hellings . 2014 . Conjunctive context-free path queries . In Proceedings of ICDT'14 . 119--130. Jelle Hellings. 2014. Conjunctive context-free path queries. In Proceedings of ICDT'14. 119--130."},{"key":"e_1_3_2_1_13_1","volume-title":"Querying for Paths in Graphs using Context-Free Path Queries. arXiv preprint arXiv:1502.02242","author":"Hellings Jelle","year":"2015","unstructured":"Jelle Hellings . 2015. Querying for Paths in Graphs using Context-Free Path Queries. arXiv preprint arXiv:1502.02242 ( 2015 ). Jelle Hellings. 2015. Querying for Paths in Graphs using Context-Free Path Queries. arXiv preprint arXiv:1502.02242 (2015)."},{"key":"e_1_3_2_1_14_1","volume-title":"21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning (EPiC Series in Computing","volume":"180","author":"Hollingum Nicholas","year":"2017","unstructured":"Nicholas Hollingum and Bernhard Scholz . 2017 . Cauliflower: a Solver Generator for Context-Free Language Reachability. In LPAR-21 . 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning (EPiC Series in Computing , Vol. 46), Thomas Eiter and David Sands (Eds.). EasyChair, 171-- 180 . https:\/\/doi.org\/10.29007\/tbm7 10.29007\/tbm7 Nicholas Hollingum and Bernhard Scholz. 2017. Cauliflower: a Solver Generator for Context-Free Language Reachability. In LPAR-21. 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning (EPiC Series in Computing, Vol. 46), Thomas Eiter and David Sands (Eds.). EasyChair, 171--180. https:\/\/doi.org\/10.29007\/tbm7"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761646"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Jeremy Kepner and John Gilbert. 2011. Graph algorithms in the language of linear algebra. SIAM.  Jeremy Kepner and John Gilbert. 2011. Graph algorithms in the language of linear algebra. SIAM.","DOI":"10.1137\/1.9780898719918"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3335783.3335791"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Applied Computing","author":"Medeiros Ciro M.","unstructured":"Ciro M. Medeiros , Martin A. Musicante , and Umberto S. Costa . 2018. Efficient Evaluation of Context-free Path Queries for Graph Databases . In Proceedings of the 33rd Annual ACM Symposium on Applied Computing ( Pau, France) (SAC '18). ACM, New York, NY, USA, 1230--1237. https:\/\/doi.org\/10.1145\/3167132.3167265 10.1145\/3167132.3167265 Ciro M. Medeiros, Martin A. Musicante, and Umberto S. Costa. 2018. Efficient Evaluation of Context-free Path Queries for Graph Databases. In Proceedings of the 33rd Annual ACM Symposium on Applied Computing (Pau, France) (SAC '18). ACM, New York, NY, USA, 1230--1237. https:\/\/doi.org\/10.1145\/3167132.3167265"},{"key":"e_1_3_2_1_19_1","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE). 1710--1713","author":"Miao H.","unstructured":"H. Miao and A. Deshpande . 2019. Understanding Data Science Lifecycle Provenance via Graph Segmentation and Summarization . In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1710--1713 . H. Miao and A. Deshpande. 2019. Understanding Data Science Lifecycle Provenance via Graph Segmentation and Summarization. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1710--1713."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3327964.3328503"},{"key":"e_1_3_2_1_21_1","volume-title":"High-Performance and Memory-Saving Sparse General Matrix-Matrix Multiplication for NVIDIA Pascal GPU. In 2017 46th International Conference on Parallel Processing (ICPP). 101--110","author":"Nagasaka Y.","year":"2017","unstructured":"Y. Nagasaka , A. Nukada , and S. Matsuoka . 2017 . High-Performance and Memory-Saving Sparse General Matrix-Matrix Multiplication for NVIDIA Pascal GPU. In 2017 46th International Conference on Parallel Processing (ICPP). 101--110 . https:\/\/doi.org\/10.1109\/ICPP. 2017 .19 10.1109\/ICPP.2017.19 Y. Nagasaka, A. Nukada, and S. Matsuoka. 2017. High-Performance and Memory-Saving Sparse General Matrix-Matrix Multiplication for NVIDIA Pascal GPU. In 2017 46th International Conference on Parallel Processing (ICPP). 101--110. https:\/\/doi.org\/10.1109\/ICPP.2017.19"},{"key":"e_1_3_2_1_22_1","volume-title":"Musicante","author":"Santos Fred C.","year":"2018","unstructured":"Fred C. Santos , Umberto S. Costa , and Martin A . Musicante . 2018 . A Bottom-Up Algorithm for Answering Context-Free Path Queries in Graph Databases. In Web Engineering, Tommi Mikkonen, Ralf Klamma, and Juan Hern\u00e1ndez (Eds.). Springer International Publishing , Cham, 225--233. Fred C. Santos, Umberto S. Costa, and Martin A. Musicante. 2018. A Bottom-Up Algorithm for Answering Context-Free Path Queries in Graph Databases. In Web Engineering, Tommi Mikkonen, Ralf Klamma, and Juan Hern\u00e1ndez (Eds.). Springer International Publishing, Cham, 225--233."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1515\/jib-2008-100"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of the 34th IEEE\/ACM International Conference on Automated Software Engineering","author":"Vedurada Jyothi","year":"2019","unstructured":"Jyothi Vedurada and V. Krishna Nandivada . 2019. Batch Alias Analysis . In Proceedings of the 34th IEEE\/ACM International Conference on Automated Software Engineering ( San Diego, California) (ASE '19). IEEE Press, 936--948. https:\/\/doi.org\/10.1109\/ASE. 2019 .00091 10.1109\/ASE.2019.00091 Jyothi Vedurada and V. Krishna Nandivada. 2019. Batch Alias Analysis. In Proceedings of the 34th IEEE\/ACM International Conference on Automated Software Engineering (San Diego, California) (ASE '19). IEEE Press, 936--948. https:\/\/doi.org\/10.1109\/ASE.2019.00091"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241653.3241655"},{"key":"e_1_3_2_1_26_1","first-page":"2","article-title":"Complexity Results on Labeled Shortest Path Problems from Wireless Routing","volume":"54","author":"Ward Charles B.","year":"2010","unstructured":"Charles B. Ward and Nathan M. Wiegand . 2010 . Complexity Results on Labeled Shortest Path Problems from Wireless Routing Metrics. Comput. Netw. 54 , 2 (Feb. 2010), 208--217. https:\/\/doi.org\/10.1016\/j.comnet.2009.04.012 10.1016\/j.comnet.2009.04.012 Charles B. Ward and Nathan M. Wiegand. 2010. Complexity Results on Labeled Shortest Path Problems from Wireless Routing Metrics. Comput. Netw. 54, 2 (Feb. 2010), 208--217. https:\/\/doi.org\/10.1016\/j.comnet.2009.04.012","journal-title":"Metrics. Comput. Netw."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 2008 37th International Conference on Parallel Processing (ICPP '08)","author":"Ward Charles B.","year":"2008","unstructured":"Charles B. Ward , Nathan M. Wiegand , and Phillip G. Bradford . 2008. A Distributed Context-Free Language Constrained Shortest Path Algorithm . In Proceedings of the 2008 37th International Conference on Parallel Processing (ICPP '08) . IEEE Computer Society, Washington, DC, USA, 373--380. https:\/\/doi.org\/10.1109\/ICPP. 2008 .67 10.1109\/ICPP.2008.67 Charles B. Ward, Nathan M. Wiegand, and Phillip G. Bradford. 2008. A Distributed Context-Free Language Constrained Shortest Path Algorithm. In Proceedings of the 2008 37th International Conference on Parallel Processing (ICPP '08). IEEE Computer Society, Washington, DC, USA, 373--380. https:\/\/doi.org\/10.1109\/ICPP.2008.67"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298576"},{"key":"e_1_3_2_1_29_1","volume-title":"International Semantic Web Conference. Springer, 632--648","author":"Zhang X.","unstructured":"X. Zhang , Z. Feng , X. Wang , G. Rao , and W. Wu . 2016. Context-free path queries on RDF graphs . In International Semantic Web Conference. Springer, 632--648 . X. Zhang, Z. Feng, X. Wang, G. Rao, and W. Wu. 2016. Context-free path queries on RDF graphs. In International Semantic Web Conference. Springer, 632--648."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328897.1328464"}],"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 3rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398682.3399163","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3398682.3399163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:31Z","timestamp":1750199611000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398682.3399163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,14]]},"references-count":30,"alternative-id":["10.1145\/3398682.3399163","10.1145\/3398682"],"URL":"https:\/\/doi.org\/10.1145\/3398682.3399163","relation":{},"subject":[],"published":{"date-parts":[[2020,6,14]]},"assertion":[{"value":"2020-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}