{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T02:04:36Z","timestamp":1768010676957,"version":"3.49.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p>\n            Regular simple path query (RPQ) is one of the fundamental operators in graph analytics. In an RPQ, the input is a graph, a source node and a regular expression. The goal is to identify all nodes that are connected to the source through a simple path whose label sequence satisfies the given regular expression. The regular expression acts as a formal specification of the search space that is of interest to the user. Although regular expressions have high expressive power, they act as barrier to non-technical users. Furthermore, to fully realize the power of regular expressions, the user must be familiar with the domain of the graph dataset. In this study, we address this bottleneck by bridging RPQs with the\n            <jats:italic>query-by-example<\/jats:italic>\n            paradigm. More specifically, we ask the user for an exemplar pair that characterizes the paths of interest, and the regular expression is automatically inferred from this exemplar. This novel problem introduces several new challenges. How do we infer the regex? Given that answering RPQs is NP-hard, how do we scale to large graphs? We address these challenges through a unique combination of\n            <jats:italic>Biermann and Feldman's algorithm<\/jats:italic>\n            with\n            <jats:italic>NFA-guided random walks with restarts.<\/jats:italic>\n            Extensive experiments on multiple real, million-scale datasets establish that RQuBE is at least 3 orders of magnitude faster than baseline strategies with an average accuracy in excess of 90%.\n          <\/jats:p>","DOI":"10.14778\/3489496.3489510","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:28:36Z","timestamp":1644020916000},"page":"299-311","source":"Crossref","is-referenced-by-count":4,"title":["Answering regular path queries through exemplars"],"prefix":"10.14778","volume":"15","author":[{"given":"Komal","family":"Chauhan","sequence":"first","affiliation":[{"name":"IIT Delhi, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kartik","family":"Jain","sequence":"additional","affiliation":[{"name":"IIT Delhi, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sayan","family":"Ranu","sequence":"additional","affiliation":[{"name":"IIT Delhi, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srikanta","family":"Bedathur","sequence":"additional","affiliation":[{"name":"IIT Delhi, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amitabha","family":"Bagchi","sequence":"additional","affiliation":[{"name":"IIT Delhi, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. CORE Rankings Portal. http:\/\/portal.core.edu.au\/conf-ranks\/.  [n.d.]. CORE Rankings Portal. http:\/\/portal.core.edu.au\/conf-ranks\/."},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"Statistical mechanics of complex networks","volume":"74","year":"2002","unstructured":"2002 . Statistical mechanics of complex networks . Reviews of Modern Physics 74 , 1 (Jan. 2002), 47--97. 2002. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 1 (Jan. 2002), 47--97.","journal-title":"Reviews of Modern Physics"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/75556"},{"key":"e_1_2_1_7_1","volume-title":"Technical Report AIM-114. Stanford University.","author":"Biermann A. W.","year":"1970","unstructured":"A. W. Biermann and J. A. Feldman . 1970 . On the synthesis of finite-state acceptors. Technical Report AIM-114. Stanford University. A. W. Biermann and J. A. Feldman. 1970. On the synthesis of finite-state acceptors. Technical Report AIM-114. Stanford University."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376746"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015","author":"Bonifati Angela","year":"2015","unstructured":"Angela Bonifati , Radu Ciucanu , and Aur\u00e9lien Lemay . 2015 . Learning Path Queries on Graph Databases . In Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015 , Brussels, Belgium, March 23--27 , 2015. 109--120. Angela Bonifati, Radu Ciucanu, and Aur\u00e9lien Lemay. 2015. Learning Path Queries on Graph Databases. In Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, March 23--27, 2015. 109--120."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2074226.2074238"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000807"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1101\/321984"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/951513.951554"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807183"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(88)90053-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"D. A. Levin Y. Peres and E. L. Wilmer. 2017. Markov chains and mixing times (2e ed.). American Mathematical Soc.  D. A. Levin Y. Peres and E. L. Wilmer. 2017. Markov chains and mixing times (2e ed.). American Mathematical Soc.","DOI":"10.1090\/mbk\/107"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66917-5_13"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1980.4308394"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0048"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1129-y"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026485807148"},{"key":"e_1_2_1_28_1","volume-title":"Oliveira and Stephen Edwards","author":"Arlindo","year":"1995","unstructured":"Arlindo L. Oliveira and Stephen Edwards . 1995 . Inference of State Machines from Examples of Behavior . Arlindo L. Oliveira and Stephen Edwards. 1995. Inference of State Machines from Examples of Behavior."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389733"},{"key":"e_1_2_1_30_1","volume-title":"AI'87-Proceedings Australian Joint Artificial Intelligence Conference","author":"Patrick Jon D","year":"1987","unstructured":"Jon D Patrick and KE Chong . 1987 . Real-time inductive inference for analysing human behaviour . In AI'87-Proceedings Australian Joint Artificial Intelligence Conference , Sydney. 305--322. Jon D Patrick and KE Chong. 1987. Real-time inductive inference for analysing human behaviour. In AI'87-Proceedings Australian Joint Artificial Intelligence Conference, Sydney. 305--322."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397245"},{"key":"e_1_2_1_33_1","unstructured":"Eric Prud'hommeaux and Andy Seaborne. 2008. SPARQL Query Language for RDF. W3C Recommendation. http:\/\/www.w3.org\/TR\/rdf-sparql-query\/  Eric Prud'hommeaux and Andy Seaborne. 2008. SPARQL Query Language for RDF. W3C Recommendation. http:\/\/www.w3.org\/TR\/rdf-sparql-query\/"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01237940"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487692"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00049"},{"key":"e_1_2_1_37_1","volume-title":"The ubiquity of small-world networks. Brain connectivity 1, 5","author":"Telesford Qawi K","year":"2011","unstructured":"Qawi K Telesford , Karen E Joyce , Satoru Hayasaka , Jonathan H Burdette , and Paul J Laurienti . 2011. The ubiquity of small-world networks. Brain connectivity 1, 5 ( 2011 ), 367--375. Qawi K Telesford, Karen E Joyce, Satoru Hayasaka, Jonathan H Burdette, and Paul J Laurienti. 2011. The ubiquity of small-world networks. Brain connectivity 1, 5 (2011), 367--375."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13222-020-00353-9"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313448"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035955"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_2_1_43_1","volume-title":"IEEE Symposium on Pattern Recognition.","author":"Vernadat F","year":"1982","unstructured":"F Vernadat . 1982 . Regular grammatical inference by a successor method . In IEEE Symposium on Pattern Recognition. F Vernadat. 1982. Regular grammatical inference by a successor method. In IEEE Symposium on Pattern Recognition."},{"key":"e_1_2_1_44_1","unstructured":"Denny Vrande\u010di\u0107 and Markus Kr\u00f6tzsch. 2021. Wikidata:Database reports\/List of properties\/all. https:\/\/www.wikidata.org\/wiki\/Wikidata:Database_reports\/List_of_properties\/all  Denny Vrande\u010di\u0107 and Markus Kr\u00f6tzsch. 2021. Wikidata:Database reports\/List of properties\/all. https:\/\/www.wikidata.org\/wiki\/Wikidata:Database_reports\/List_of_properties\/all"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319882"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1282480.1282482"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.003"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3489496.3489510","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:13:49Z","timestamp":1672226029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3489496.3489510"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.14778\/3489496.3489510"],"URL":"https:\/\/doi.org\/10.14778\/3489496.3489510","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,10]]}}}