{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T22:59:50Z","timestamp":1767826790753,"version":"3.49.0"},"reference-count":102,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["OAC-1835446"],"award-info":[{"award-number":["OAC-1835446"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Regular expression, or regex, is widely used to extract critical information from a large corpus of formatted text by finding patterns of interest. In tasks like log processing, the speed of regex matching is crucial. Data scientists and developers regularly use regex libraries that implement optimized regular expression matching using modern automata theory. However, computing state transitions in the underlying regex evaluation engine can be inefficient when a regex query contains a multitude of string literals. This inefficiency is further exasperated when analyzing large data volumes. This paper presents BLARE, Blazingly Fast Regular Expression, a regular expression matching framework that is inspired by the mechanisms that are used in database engines, which use a declarative framework to explore multiple equivalent execution plans, all of which produce the correct final result. Similarly, BLARE decomposes a regex into multiple regex and string components and then creates evaluation strategies in which the components can be evaluated in an order that is not strictly a left-to-right translation of the input regex query. Rather than using a cost-based optimization approach, BLARE uses an adaptive runtime strategy based on a multi-armed bandit approach to find an efficient execution plan. BLARE is also modular and can be built on top of any existing regex library. We implemented BLARE on four commonly used regex libraries, RE2, PCRE2, Boost Regex, and ICU Regex, and evaluated it using two production workloads and one open-source workload. BLARE was 1.6\u00d7 to 3.7\u00d7 faster than RE2 and 3.4\u00d7 to 7.9\u00d7 faster than Boost Regex. PCRE2 did not finish on one of the workloads, but on the remaining two workloads, BLARE improved the performance of PCRE2 by 3.1\u00d7 to over 100\u00d7. For the open-source dataset, BLARE provided a speed up of 61.7\u00d7 for ICU Regex. BLARE code is publicly available at https:\/\/github.com\/mush-zhang\/Blare.<\/jats:p>","DOI":"10.1145\/3589297","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-28","source":"Crossref","is-referenced-by-count":3,"title":["Exploiting Structure in Regular Expression Queries"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-2228-3945","authenticated-orcid":false,"given":"Ling","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2342-4060","authenticated-orcid":false,"given":"Shaleen","family":"Deep","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5760-8657","authenticated-orcid":false,"given":"Avrilia","family":"Floratou","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab, Sunnyvale, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-2547-8610","authenticated-orcid":false,"given":"Anja","family":"Gruenheid","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3653-2538","authenticated-orcid":false,"given":"Jignesh M.","family":"Patel","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6857-7505","authenticated-orcid":false,"given":"Yiwen","family":"Zhu","sequence":"additional","affiliation":[{"name":"Microsoft Gray Systems Lab, Redmond, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/NWeSP.2011.6088148"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOMS.2012.6211894"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2014.12.011"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/968280.968312"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1872007.1872032"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/infcom.2007.128"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2445572.2445576"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323548.1323573"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882486.1882495"},{"key":"e_1_2_2_11_1","unstructured":"2022. 8.5.7 ?posix-basic' regular expression syntax. Retrieved October 7 2022 from https:\/\/www.gnu.org\/software\/findutils\/manual\/html_node\/find_html\/posix_002dbasic-regular-expression-syntax.html."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253345"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","unstructured":"Benjamin C Brodie David E Taylor and Ron K Cytron. 2006. A scalable architecture for high-throughput regular-expression pattern matching. ACM SIGARCH computer architecture news 34 2 191--202. doi: 10.1109\/isca.2006.7.","DOI":"10.1109\/isca.2006.7"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","unstructured":"Anne Br\u00fcggemann-Klein and Derick Wood. 1998. One-unambiguous regular languages. Information and computation 140 2 229--253. doi: 10.1006\/inco.1997.2688.","DOI":"10.1006\/inco.1997.2688"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303996"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/jcn.2011.6157418"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0094-0"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735503"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994755"},{"key":"e_1_2_2_21_1","volume-title":"International Workshop on the Web and Databases.","author":"Choi Byron","year":"2002","unstructured":"Byron Choi. 2002. What are real dtds like? In International Workshop on the Web and Databases."},{"key":"e_1_2_2_22_1","unstructured":"[SW] Cisco Snort - Network Intrusion Detection and Prevention System. url: https:\/\/www.snort.org\/snort3 vcs: https:\/\/github.com\/snort3\/snort3."},{"key":"e_1_2_2_23_1","unstructured":"Russ Cox. 2012. Regular expression matching with a trigram index or how google code search worked. (2012)."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958947"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/icde.2002.994748"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-012--1312-y"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275503"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--27836--8_53"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.3390\/a14050133"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783747"},{"key":"e_1_2_2_32_1","unstructured":"[SW] Google Google-RE2 version release 2022-06-01. url: https:\/\/github.com\/google\/re2 vcs: https:\/\/github.com\/google\/re2."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042051"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460319.3464796"},{"key":"e_1_2_2_35_1","unstructured":"[SW] Md. Jahidul Hamid JPCRE2 version 10.32.01. url: https:\/\/docs.neuzunix.com\/jpcre2\/ vcs: https:\/\/github.com\/jpcre2\/jpcre2."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/b978--155860869--6"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983358"},{"key":"e_1_2_2_38_1","volume-title":"Retrieved","author":"Hazel Philip","year":"2019","unstructured":"Philip Hazel. 2019. Technical notes about pcre2. (July 2019). Retrieved October 11, 2022 from https:\/\/github.com\/PCRE\/pcre2\/blob\/6c941e3f778970b3012093da7bf888c875dd1739\/HACKING%5C#L454."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ancs.2013.6665178"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200064"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386367.3431290"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEEESTD.2018.8277153"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382232"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920987"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480108"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/icde.2008.4497471"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460877.1460879"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323548.1323574"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","unstructured":"Sailesh Kumar Sarang Dharmapurikar Fang Yu Patrick Crowley and Jonathan Turner. 2006. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. ACM SIGCOMM computer communication review 36 4 339--350. doi: 10.1145\/1159913.1159952.","DOI":"10.1145\/1159913.1159952"},{"key":"e_1_2_2_51_1","first-page":"361","article-title":"Indexing and querying xml data for regular path expressions","volume":"1","author":"Li Quanzhong","year":"2001","unstructured":"Quanzhong Li, Bongki Moon, et al. 2001. Indexing and querying xml data for regular path expressions. In VLDB. Vol. 1, 361--370.","journal-title":"VLDB."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2876473.2876478"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848024"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015047.1015055"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2014.2358839"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213598.2213609"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352112"},{"key":"e_1_2_2_58_1","volume-title":"Retrieved","year":"2023","unstructured":"2020. Luceneplusplus build instructions. (Aug. 2020). Retrieved January 08, 2023 from https:\/\/github.com\/luceneplusplus\/LucenePlusPlus\/blob\/9eb5e63e336546bc927e622fdda49919c4143e8e\/doc\/BUILDING.md."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2012.49"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526066"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324185.1324188"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371319"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2018.19"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442--8"},{"key":"e_1_2_2_65_1","volume-title":"Retrieved","year":"2022","unstructured":"Microsoft. 2022. Reference materials for kusto query language - re2 syntax. (Nov. 2022). Retrieved October 11, 2022 from https:\/\/learn.microsoft.com\/en-us\/azure\/data-explorer\/kusto\/query\/re2."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323548.1323571"},{"key":"e_1_2_2_67_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_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359078"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2014.125"},{"key":"e_1_2_2_70_1","first-page":"1","article-title":"Regexpcount, a symbolic package for counting problems on regular expressions and words","volume":"56","author":"Nicodeme Pierre","year":"2003","unstructured":"Pierre Nicodeme. 2003. Regexpcount, a symbolic package for counting problems on regular expressions and words. Fundamenta Informaticae, 56, 1--2, 71--88.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_2_71_1","unstructured":"[SW] Open Information Security Foundation Suricata. url: https:\/\/suricata.io\/ vcs: https:\/\/github.com\/OISF\/suricata."},{"key":"e_1_2_2_72_1","volume-title":"Retrieved","author":"Mysql","year":"2023","unstructured":"Oracle. [n. d.] Mysql 8.0 reference manual: 12.8.2 regular expressions. Retrieved January 08, 2023 from https:\/\/dev.mysql.com\/doc\/refman\/8.0\/en\/regexp.html."},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3476982"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554829"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476353"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000070"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786805.2786855"},{"key":"e_1_2_2_78_1","volume-title":"Retrieved","author":"Sch\u00e4ling Boris","year":"2014","unstructured":"Boris Sch\u00e4ling. 2014. The boost c libraries, chapter 8. boost.regex. (Sept. 2014). Retrieved January 08, 2023 from https:\/\/theboostcpplibraries.com\/boost.regex."},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471498"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035954"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933357"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2003.1214975"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.47"},{"key":"e_1_2_2_84_1","volume-title":"Retrieved","author":"Software Foundation The Apache","year":"2022","unstructured":"The Apache Software Foundation. 2022. Apache lucene 9.4.2 documentation. (Nov. 2022). Retrieved January 17, 2023 from https:\/\/lucene.apache.org\/core\/9_4_2\/index.html."},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063968"},{"key":"e_1_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354682"},{"key":"e_1_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2006.204"},{"key":"e_1_2_2_88_1","unstructured":"Stijn Vansummeren. 2003. Unique pattern matching in strings. arXiv preprint cs\/0302004."},{"key":"e_1_2_2_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/2046707.2046741"},{"key":"e_1_2_2_90_1","doi-asserted-by":"publisher","DOI":"10.1109\/icc.2011.5963291"},{"key":"e_1_2_2_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2022.3202523"},{"key":"e_1_2_2_92_1","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Wang Xiang","year":"2019","unstructured":"Xiang Wang, Yang Hong, Harry Chang, KyoungSoo Park, Geoff Langdale, Jiayu Hu, and Heqing Zhu. 2019. Hyperscan: a fast multi-pattern regex matcher for modern CPUs. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). USENIX Association, Boston, MA, 631--648. isbn: 978--1--931971--49--2. https:\/\/www.usenix.org\/conference\/nsdi19\/presentation\/wang-xiang."},{"key":"e_1_2_2_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"},{"key":"e_1_2_2_94_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2016.2566669"},{"key":"e_1_2_2_95_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2014.2358856"},{"key":"e_1_2_2_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_2_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2016.7511199"},{"key":"e_1_2_2_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185347.1185360"},{"key":"e_1_2_2_99_1","volume-title":"Ensemble Machine Learning: Methods and Applications","author":"Zhang Cha","year":"1993","unstructured":"Cha Zhang and Yunqian Ma. 2012. Ensemble Machine Learning: Methods and Applications. Springer Publishing Company, Incorporated. isbn: 1441993258."},{"key":"e_1_2_2_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807266"},{"key":"e_1_2_2_101_1","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488827"},{"key":"e_1_2_2_102_1","unstructured":"Li Zhou. 2015. A survey on contextual multi-armed bandits. arXiv preprint arXiv:1508.03326."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589297","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:13Z","timestamp":1750178773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":102,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589297"],"URL":"https:\/\/doi.org\/10.1145\/3589297","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}