{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:49:10Z","timestamp":1773193750839,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":95,"publisher":"ACM","funder":[{"name":"Information & communications Technology Planning & Evaluation (IITP)","award":["RS-2023-00208606, RS-2024-00395134, 2021-0-01343"],"award-info":[{"award-number":["RS-2023-00208606, RS-2024-00395134, 2021-0-01343"]}]},{"name":"Samsung Electronics"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,10,18]]},"DOI":"10.1145\/3725843.3756052","type":"proceedings-article","created":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T17:21:19Z","timestamp":1760721679000},"page":"385-400","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0605-0888","authenticated-orcid":false,"given":"Tianao","family":"Ge","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9745-4372","authenticated-orcid":false,"given":"Xiaowen","family":"Chu","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6961-6394","authenticated-orcid":false,"given":"Hongyuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, Hoboken, New Jersey, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,10,17]]},"reference":[{"key":"e_1_3_3_1_2_2","unstructured":"2025. Boost Regex Library. https:\/\/github.com\/boostorg\/regex."},{"key":"e_1_3_3_1_3_2","unstructured":"2025. Clamav net. https:\/\/www.clamav.net\/."},{"key":"e_1_3_3_1_4_2","unstructured":"2025. HSCompile: MNRL HyperScan. https:\/\/github.com\/kevinaangstadt\/hscompile."},{"key":"e_1_3_3_1_5_2","unstructured":"2025. NVIDIA Nsight Compute Profiling Tool. https:\/\/docs.nvidia.com\/nsight-compute\/NsightCompute\/."},{"key":"e_1_3_3_1_6_2","unstructured":"2025. RE2. https:\/\/github.com\/google\/re2."},{"key":"e_1_3_3_1_7_2","unstructured":"2025. The User guide for the NVRTC library. https:\/\/docs.nvidia.com\/cuda\/nvrtc\/."},{"key":"e_1_3_3_1_8_2","unstructured":"2025. The Zeek Network Security Monitor. https:\/\/www.zeek.org."},{"key":"e_1_3_3_1_9_2","unstructured":"2025. YARA: The pattern matching swiss knife for malware researchers. https:\/\/virustotal.github.io\/yara\/."},{"key":"e_1_3_3_1_10_2","doi-asserted-by":"publisher","unstructured":"Alfred\u00a0V. Aho and Margaret\u00a0J. Corasick. 1975. Efficient string matching: an aid to bibliographic search. Commun. ACM (1975). 10.1145\/360825.360855","DOI":"10.1145\/360825.360855"},{"key":"e_1_3_3_1_11_2","volume-title":"Compilers Principles, Techniques & Tools","author":"Alfred V\u00a0Aho","year":"2007","unstructured":"V\u00a0Aho Alfred, S\u00a0Lam Monica, and D\u00a0Ullman Jeffrey. 2007. Compilers Principles, Techniques & Tools. Pearson Education."},{"key":"e_1_3_3_1_12_2","doi-asserted-by":"publisher","unstructured":"Mohammed Alser Julien Eudine and Onur Mutlu. 2025. Taming Large-scale Genomic Analyses via Sparsified Genomics. Nature Communications 16 1 (2025) 876. 10.1038\/s41467-024-55762-1","DOI":"10.1038\/s41467-024-55762-1"},{"key":"e_1_3_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/645926.671841"},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"crossref","unstructured":"K. Angstadt J. Wadden V. Dang T. Xie D. Kramp W. Weimer M. Stan and K. Skadron. 2018. MNCaRT: An Open-Source Multi-Architecture Automata-Processing Research and Execution Ecosystem. IEEE Computer Architecture Letters (CAL) (2018).","DOI":"10.1109\/LCA.2017.2780105"},{"key":"e_1_3_3_1_15_2","doi-asserted-by":"publisher","unstructured":"Matteo Avalle Fulvio Risso and Riccardo Sisto. 2016. Scalable Algorithms for NFA Multi-Striding and NFA-Based Deep Packet Inspection on GPUs. IEEE\/ACM Transactions on Networking (ToN) (2016). 10.1109\/TNET.2015.2429918","DOI":"10.1109\/TNET.2015.2429918"},{"key":"e_1_3_3_1_16_2","doi-asserted-by":"publisher","unstructured":"Ricardo Baeza-Yates and Gaston\u00a0H. Gonnet. 1992. A New Approach to Text Searching. Commun. ACM 35 10 (1992). 10.1145\/135239.135243","DOI":"10.1145\/135239.135243"},{"key":"e_1_3_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510047"},{"key":"e_1_3_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1364654.1364656"},{"key":"e_1_3_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1544012.1544037"},{"key":"e_1_3_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2008.4636093"},{"key":"e_1_3_3_1_21_2","unstructured":"Amit Bleiweiss and Nicole Luo. 2024. Mastering LLM Techniques: Data Preprocessing. https:\/\/developer.nvidia.com\/blog\/mastering-llm-techniques-data-preprocessing\/."},{"key":"e_1_3_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00068"},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2006.7"},{"key":"e_1_3_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO50266.2020.00081"},{"key":"e_1_3_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628079"},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649329.3657378"},{"key":"e_1_3_3_1_27_2","unstructured":"Niccolo\u2019 Cascarano Pierluigi Rolando Fulvio Risso and Riccardo Sisto. 2010. iNFAnt: NFA Pattern Matching on GPGPU Devices. SIGCOMM Computer Communication Review (CCR) (2010)."},{"key":"e_1_3_3_1_28_2","doi-asserted-by":"publisher","unstructured":"Qianxi Chen Yujiao Deng Qiang Wu and Zhixiong Di. 2025. An r-DFA-based Layout Pattern Match Method Supporting Fuzzy Matching. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2025). 10.1109\/TCAD.2025.3556969","DOI":"10.1109\/TCAD.2025.3556969"},{"key":"e_1_3_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO57630.2024.10444810"},{"key":"e_1_3_3_1_30_2","unstructured":"Russ Cox. 2007. Regular Expression Matching Can Be Simple and Fast. https:\/\/swtch.com\/\u00a0rsc\/regexp\/regexp1.html."},{"key":"e_1_3_3_1_31_2","volume-title":"Proceedings of the 12th USENIX Security Symposium (USENIX Security)","author":"Crosby Scott\u00a0A","year":"2003","unstructured":"Scott\u00a0A Crosby and Dan\u00a0S Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th USENIX Security Symposium (USENIX Security)."},{"key":"e_1_3_3_1_32_2","doi-asserted-by":"crossref","unstructured":"Paul Dlugosch Dave Brown Paul Glendenning Michael Leventhal and Harold Noyes. 2014. An Efficient and Scalable Semiconductor Architecture for Parallel Automata Processing. IEEE Transactions on Parallel and Distributed Systems (2014).","DOI":"10.1109\/TPDS.2014.8"},{"key":"e_1_3_3_1_33_2","doi-asserted-by":"publisher","unstructured":"Johannes Doleschal Benny Kimelfeld and Wim Martens. 2021. Database Principles and Challenges in Text Analysis. SIGMOD Rec. (2021). 10.1145\/3484622.3484624","DOI":"10.1145\/3484622.3484624"},{"key":"e_1_3_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3676642.3736126"},{"key":"e_1_3_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830809"},{"key":"e_1_3_3_1_36_2","doi-asserted-by":"publisher","unstructured":"Yuanwei Fang Chen Zou and Andrew\u00a0A. Chien. 2019. Accelerating raw data analysis with the ACCORDA software and hardware architecture. Proc. VLDB Endow. (2019). 10.14778\/3342263.3342634","DOI":"10.14778\/3342263.3342634"},{"key":"e_1_3_3_1_37_2","doi-asserted-by":"publisher","unstructured":"Fernando Florenzano Cristian Riveros Mart\u00edn Ugarte Stijn Vansummeren and Domagoj Vrgo\u010d. 2020. Efficient Enumeration Algorithms for Regular Document Spanners. ACM Trans. Database Syst. (2020). 10.1145\/3351451","DOI":"10.1145\/3351451"},{"key":"e_1_3_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3617232.3624848"},{"key":"e_1_3_3_1_39_2","doi-asserted-by":"publisher","unstructured":"Tianao Ge Tong Zhang and Hongyuan Liu. 2025. Towards Scalable and Non-blocking Automata Processing on GPUs with ngAP. ACM Trans. Comput. Syst. (2025). 10.1145\/3748646","DOI":"10.1145\/3748646"},{"key":"e_1_3_3_1_40_2","doi-asserted-by":"publisher","unstructured":"Alexis\u00a0Le Glaunec Lingkun Kong and Konstantinos Mamouras. 2024. HybridSA: GPU Acceleration of Multi-pattern Regex Matching Using Bit Parallelism. Proc. ACM Program. Lang. 8 OOPSLA2 (2024) 1699\u20131728. 10.1145\/3689771","DOI":"10.1145\/3689771"},{"key":"e_1_3_3_1_41_2","doi-asserted-by":"crossref","unstructured":"Victor\u00a0Mikhaylovich Glushkov. 1961. The Abstract Theory of Automata. Russian Mathematical Surveys 16 5 (1961) 1.","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_3_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783747"},{"key":"e_1_3_3_1_43_2","unstructured":"Robert Heeg. 2023. Possibilities and limitations of unstructured data. https:\/\/researchworld.com\/articles\/possibilities-and-limitations-of-unstructured-data."},{"key":"e_1_3_3_1_44_2","doi-asserted-by":"publisher","unstructured":"W.\u00a0Daniel Hillis and Guy\u00a0L. Steele. 1986. Data Parallel Algorithms. Commun. ACM (Dec. 1986) 1170\u20131183. 10.1145\/7902.7903","DOI":"10.1145\/7902.7903"},{"key":"e_1_3_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614313"},{"key":"e_1_3_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314148.3314356"},{"key":"e_1_3_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480108"},{"key":"e_1_3_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523456"},{"key":"e_1_3_3_1_49_2","doi-asserted-by":"publisher","unstructured":"Alexis Le\u00a0Glaunec Lingkun Kong and Konstantinos Mamouras. 2023. Regular Expression Matching using Bit Vector Automata. Proc. ACM Program. Lang. 7 OOPSLA1 (2023). 10.1145\/3586044","DOI":"10.1145\/3586044"},{"key":"e_1_3_3_1_50_2","doi-asserted-by":"publisher","unstructured":"Yinan Li Nikos\u00a0R. Katsipoulakis Badrish Chandramouli Jonathan Goldstein and Donald Kossmann. 2017. Mison: A Fast JSON Parser for Data Analytics. Proceedings of the VLDB Endowment (VLDB) 10 10 (2017) 1118\u20131129. 10.14778\/3115404.3115416","DOI":"10.14778\/3115404.3115416"},{"key":"e_1_3_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2012.6169041"},{"key":"e_1_3_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2018.00078"},{"key":"e_1_3_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378471"},{"key":"e_1_3_3_1_54_2","doi-asserted-by":"publisher","unstructured":"Hongyuan Liu Sreepathi Pai and Adwait Jog. 2023. Asynchronous Automata Processing on GPUs. Proceedings of the ACM on Measurement and Analysis of Computing Systems 7 1 (2023). 10.1145\/3579453","DOI":"10.1145\/3579453"},{"key":"e_1_3_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541988"},{"key":"e_1_3_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3079079.3079100"},{"key":"e_1_3_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485832.3485878"},{"key":"e_1_3_3_1_58_2","doi-asserted-by":"publisher","unstructured":"Daniele Parravicini Davide Conficconi Emanuele\u00a0Del Sozzo Christian Pilato and Marco\u00a0D. Santambrogio. 2021. CICERO: A Domain-Specific Architecture for Efficient Regular Expression Matching. ACM Trans. Embed. Comput. Syst. (2021). 10.1145\/3476982","DOI":"10.1145\/3476982"},{"key":"e_1_3_3_1_59_2","doi-asserted-by":"publisher","unstructured":"Junqiao Qiu and Ali Ebnenasir. 2023. Exploring Scalable Parallelization for Edit Distance-Based Motif Search. IEEE\/ACM Transactions on Computational Biology and Bioinformatics (2023). 10.1109\/TCBB.2022.3208867","DOI":"10.1109\/TCBB.2022.3208867"},{"key":"e_1_3_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378461"},{"key":"e_1_3_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446705"},{"key":"e_1_3_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3472456.3473512"},{"key":"e_1_3_3_1_63_2","doi-asserted-by":"publisher","unstructured":"Cristian Riveros Nicol\u00e1s Van Sint\u00a0Jan and Domagoj Vrgo\u010d. 2023. REmatch: A Novel Regex Engine for Finding All Matches. Proc. VLDB Endow. (2023). 10.14778\/3611479.3611488","DOI":"10.14778\/3611479.3611488"},{"key":"e_1_3_3_1_64_2","unstructured":"Matt Robinson. 2025. Preprocessing Unstructured Data for LLM Applications. https:\/\/www.deeplearning.ai\/short-courses\/preprocessing-unstructured-data-for-llm-applications\/."},{"key":"e_1_3_3_1_65_2","volume-title":"Proceedings of the USENIX Conference on System Administration (LISA)","author":"Roesch Martin","year":"1999","unstructured":"Martin Roesch. 1999. Snort - Lightweight Intrusion Detection for Networks. In Proceedings of the USENIX Conference on System Administration (LISA)."},{"key":"e_1_3_3_1_66_2","doi-asserted-by":"publisher","unstructured":"Indranil Roy and Srinivas Aluru. 2016. Discovering Motifs in Biological Sequences Using the Micron Automata Processor. IEEE\/ACM Transactions on Computational Biology and Bioinformatics 13 1 (2016) 99\u2013111. 10.1109\/TCBB.2015.2430313","DOI":"10.1109\/TCBB.2015.2430313"},{"key":"e_1_3_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378459"},{"key":"e_1_3_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00017"},{"key":"e_1_3_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358324"},{"key":"e_1_3_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.5555\/1058426.1058885"},{"key":"e_1_3_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035954"},{"key":"e_1_3_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3696443.3708916"},{"key":"e_1_3_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3079856.3080207"},{"key":"e_1_3_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123986"},{"key":"e_1_3_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498263"},{"key":"e_1_3_3_1_76_2","doi-asserted-by":"publisher","unstructured":"Ken Thompson. 1968. Programming Techniques: Regular expression search algorithm. Commun. ACM (1968). 10.1145\/363347.363387","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_3_1_77_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87403-4_7"},{"key":"e_1_3_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04342-0_14"},{"key":"e_1_3_3_1_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2011.6114181"},{"key":"e_1_3_3_1_80_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00069"},{"key":"e_1_3_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2016.7581271"},{"key":"e_1_3_3_1_82_2","volume-title":"VASim: An Open Virtual Automata Simulator for Automata Processing Application and Architecture Research","author":"Wadden Jack","year":"2016","unstructured":"Jack Wadden and Kevin Skadron. 2016. VASim: An Open Virtual Automata Simulator for Automata Processing Application and Architecture Research. Technical Report CS2016-03. University of Virginia."},{"key":"e_1_3_3_1_83_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2018.8573482"},{"key":"e_1_3_3_1_84_2","doi-asserted-by":"publisher","DOI":"10.5555\/3323234.3323286"},{"key":"e_1_3_3_1_85_2","unstructured":"Bruce\u00a0William Watson. 1993. A taxonomy of finite automata construction algorithms. (1993)."},{"key":"e_1_3_3_1_86_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640412"},{"key":"e_1_3_3_1_87_2","doi-asserted-by":"publisher","unstructured":"Sun Wu and Udi Manber. 1992. Fast Text Searching: Allowing Errors. Commun. ACM (1992). 10.1145\/135239.135244","DOI":"10.1145\/135239.135244"},{"key":"e_1_3_3_1_88_2","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374524"},{"key":"e_1_3_3_1_89_2","doi-asserted-by":"publisher","unstructured":"Chengcheng Xu Shuhui Chen Jinshu Su S.\u00a0M. Yiu and Lucas C.\u00a0K. Hui. 2016. A Survey on Regular Expression Matching for Deep Packet Inspection: Applications Algorithms and Hardware Platforms. IEEE Communications Surveys & Tutorials (2016). 10.1109\/COMST.2016.2566669","DOI":"10.1109\/COMST.2016.2566669"},{"key":"e_1_3_3_1_90_2","doi-asserted-by":"publisher","DOI":"10.1145\/1185347.1185360"},{"key":"e_1_3_3_1_91_2","doi-asserted-by":"publisher","DOI":"10.1145\/2482767.2482791"},{"key":"e_1_3_3_1_92_2","doi-asserted-by":"publisher","DOI":"10.5555\/3488766.3488827"},{"key":"e_1_3_3_1_93_2","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694369"},{"key":"e_1_3_3_1_94_2","volume-title":"Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)","author":"Zhao Zhijia","year":"2014","unstructured":"Zhijia Zhao, Bo Wu, and Xipeng Shen. 2014. Challenging the \u201cEmbarrassingly Sequential\": Parallelizing Finite State Machine-based Computations Through Principled Speculation. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)."},{"key":"e_1_3_3_1_95_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2018.00012"},{"key":"e_1_3_3_1_96_2","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145833"}],"event":{"name":"MICRO 2025: 58th IEEE\/ACM International Symposium on Microarchitecture","location":"Seoul Korea","acronym":"MICRO 2025","sponsor":["SIGMICRO ACM Special Interest Group on Microarchitectural Research and Processing"]},"container-title":["Proceedings of the 58th IEEE\/ACM International Symposium on Microarchitecture"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725843.3756052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T21:48:46Z","timestamp":1769464126000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725843.3756052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,17]]},"references-count":95,"alternative-id":["10.1145\/3725843.3756052","10.1145\/3725843"],"URL":"https:\/\/doi.org\/10.1145\/3725843.3756052","relation":{},"subject":[],"published":{"date-parts":[[2025,10,17]]},"assertion":[{"value":"2025-10-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}