{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T15:11:40Z","timestamp":1780326700677,"version":"3.54.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,2,28]],"date-time":"2019-02-28T00:00:00Z","timestamp":1551312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1439011,CCF-1421823"],"award-info":[{"award-number":["CCF-1439011,CCF-1421823"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>\n            This article presents REGISTOR, a platform for\n            <jats:italic>r<\/jats:italic>\n            egular\n            <jats:italic>e<\/jats:italic>\n            xpression\n            <jats:italic>g<\/jats:italic>\n            rabbing\n            <jats:italic>i<\/jats:italic>\n            nside\n            <jats:italic>stor<\/jats:italic>\n            age. The main idea of Registor is accelerating regular expression (regex) search inside storage where large data set is stored, eliminating the I\/O bottleneck problem. A special hardware engine for regex search is designed and augmented inside a flash SSD that processes data on-the-fly during data transmission from NAND flash to host. To make the speed of regex search match the internal bus speed of a modern SSD, a deep pipeline structure is designed in Registor hardware consisting of a file semantics extractor, matching candidates finder, regex matching units (REMUs), and results organizer. Furthermore, each stage of the pipeline makes the use of maximal parallelism possible. To make Registor readily usable by high-level applications, we have developed a set of APIs and libraries in Linux allowing Registor to process files in the SSD by recombining separate data blocks into files efficiently. A working prototype of Registor has been built in our newly designed NVMe-SSD. Extensive experiments and analyses have been carried out to show that Registor achieves high throughput, reduces the I\/O bandwidth requirement by up to 97%, and reduces CPU utilization by as much as 82% for regex search in large datasets.\n          <\/jats:p>","DOI":"10.1145\/3310149","type":"journal-article","created":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T12:41:51Z","timestamp":1553604111000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["REGISTOR"],"prefix":"10.1145","volume":"15","author":[{"given":"Shuyi","family":"Pei","sequence":"first","affiliation":[{"name":"University of Rhode Island and Shenzhen Dapu Microelectronics Co. Ltd., Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Rhode Island and Shenzhen Dapu Microelectronics Co. Ltd., Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qing","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Rhode Island and Shenzhen Dapu Microelectronics Co. Ltd., Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750386"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12525-016-0219-0"},{"key":"e_1_2_1_3_1","volume-title":"Retrieved","year":"2018","unstructured":"Amazon. 2018 . Amazon S3 . Retrieved February 26, 2019 from https:\/\/aws.amazon.com\/s3\/. Amazon. 2018. Amazon S3. Retrieved February 26, 2019 from https:\/\/aws.amazon.com\/s3\/."},{"key":"e_1_2_1_4_1","volume-title":"Retrieved","year":"2018","unstructured":"Apache. 2018 . Lucene . Retrieved February 26, 2019 from https:\/\/lucene.apache.org\/. Apache. 2018. Lucene. Retrieved February 26, 2019 from https:\/\/lucene.apache.org\/."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3102980.3102990"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2008.4636093"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150019.1136500"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628079"},{"key":"e_1_2_1_9_1","volume-title":"Retrieved","author":"Cox Russ","year":"2009","unstructured":"Russ Cox . 2009 . Regular Expression Matching: The Virtual Machine Approach . Retrieved February 26, 2019 from https:\/\/swtch.com\/&sim;rsc\/regexp\/regexp2.html. Russ Cox. 2009. Regular Expression Matching: The Virtual Machine Approach. Retrieved February 26, 2019 from https:\/\/swtch.com\/&sim;rsc\/regexp\/regexp2.html."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.8"},{"key":"e_1_2_1_11_1","volume-title":"Retrieved","author":"Express NVM","year":"2018","unstructured":"NVM Express . 2018 . NVM Express Revision 1.3a October 24, 2017 . Retrieved February 26, 2019 from http:\/\/nvmexpress.org\/wp-content\/uploads\/NVM-Express-1_3a-20171024_ratified.pdf. NVM Express. 2018. NVM Express Revision 1.3a October 24, 2017. Retrieved February 26, 2019 from http:\/\/nvmexpress.org\/wp-content\/uploads\/NVM-Express-1_3a-20171024_ratified.pdf."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830809"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123983"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452335.1452339"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijinfomgt.2014.10.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.22"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 49th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO\u201916)","author":"Gogte Vaibhav","unstructured":"Vaibhav Gogte , Aasheesh Kolli , Michael J. Cafarella , Loris D\u2019Antoni , and Thomas F. Wenisch . 2016. HARE: Hardware accelerator for regular expressions . In Proceedings of the 49th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO\u201916) . IEEE, Los Alamitos, CA, 1--12. Vaibhav Gogte, Aasheesh Kolli, Michael J. Cafarella, Loris D\u2019Antoni, and Thomas F. Wenisch. 2016. HARE: Hardware accelerator for regular expressions. In Proceedings of the 49th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO\u201916). IEEE, Los Alamitos, CA, 1--12."},{"key":"e_1_2_1_18_1","volume-title":"Retrieved","year":"2019","unstructured":"Google. 2019 . RE2 . Retrieved February 26, 2019 from https:\/\/github.com\/google\/re2. Google. 2019. RE2. Retrieved February 26, 2019 from https:\/\/github.com\/google\/re2."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.23"},{"key":"e_1_2_1_20_1","volume-title":"Retrieved","author":"Hazel Philip","year":"2019","unstructured":"Philip Hazel . 2019 . PCRE\u2014Perl Compatible Regular Expressions . Retrieved February 26, 2019 from https:\/\/www.pcre.org\/. Philip Hazel. 2019. PCRE\u2014Perl Compatible Regular Expressions. Retrieved February 26, 2019 from https:\/\/www.pcre.org\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/568438.568455"},{"key":"e_1_2_1_22_1","volume-title":"Retrieved","year":"2017","unstructured":"Github. 2017 . Performance Comparison of Regular Expression Engines . Retrieved February 26, 2019 from https:\/\/zherczeg.github.io\/sljit\/regex_perf.html. Github. 2017. Performance Comparison of Regular Expression Engines. Retrieved February 26, 2019 from https:\/\/zherczeg.github.io\/sljit\/regex_perf.html."},{"key":"e_1_2_1_23_1","unstructured":"Titan IC. 2018. Hyperion F1 10G Regex File Scan. http:\/\/titan-ic.com\/products\/hyperion-f1-10g-regex-file-scan  Titan IC. 2018. Hyperion F1 10G Regex File Scan. http:\/\/titan-ic.com\/products\/hyperion-f1-10g-regex-file-scan"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750412"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 6th International Conference on Contemporary Computing (IC3\u201913)","author":"Katal A.","unstructured":"A. Katal , M. Wazid , and R. H. Goudar . 2013. Big data: Issues, challenges, tools and good practices . In Proceedings of the 6th International Conference on Contemporary Computing (IC3\u201913) . IEEE, Los Alamitos, CA, 404--409. A. Katal, M. Wazid, and R. H. Goudar. 2013. Big data: Issues, challenges, tools and good practices. In Proceedings of the 6th International Conference on Contemporary Computing (IC3\u201913). IEEE, Los Alamitos, CA, 404--409."},{"key":"e_1_2_1_26_1","volume-title":"Retrieved","author":"Kosako K.","year":"2019","unstructured":"K. Kosako . 2019 . PCRE\u2014Perl Compatible Regular Expressions . Retrieved February 26, 2019 from https:\/\/github.com\/kkos\/oniguruma. K. Kosako. 2019. PCRE\u2014Perl Compatible Regular Expressions. Retrieved February 26, 2019 from https:\/\/github.com\/kkos\/oniguruma."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151659.1159952"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628118"},{"key":"e_1_2_1_29_1","volume-title":"Flex and Bison: Text Processing Tools","author":"Levine John","unstructured":"John Levine . 2009. Flex and Bison: Text Processing Tools . O\u2019Reilly Media Inc . John Levine. 2009. Flex and Bison: Text Processing Tools. O\u2019Reilly Media Inc."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2012.254"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2012.6169041"},{"key":"e_1_2_1_32_1","volume-title":"Retrieved","year":"2019","unstructured":"Linux. 2019 . Source to sys\/ioctl.h . Retrieved February 26, 2019 from https:\/\/unix.superglobalmegacorp.com\/Net2\/newsrc\/sys\/ioctl.h.html. Linux. 2019. Source to sys\/ioctl.h. Retrieved February 26, 2019 from https:\/\/unix.superglobalmegacorp.com\/Net2\/newsrc\/sys\/ioctl.h.html."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2012.49"},{"key":"e_1_2_1_34_1","volume-title":"Retrieved","year":"2018","unstructured":"Micron. 2018 . MT29F8G16ADADAH4-IT . Retrieved February 26, 2019 from https:\/\/www.micron.com\/products\/nand-flash\/slc-nand\/part-catalog\/mt29f8g16adadah4-it. Micron. 2018. MT29F8G16ADADAH4-IT. Retrieved February 26, 2019 from https:\/\/www.micron.com\/products\/nand-flash\/slc-nand\/part-catalog\/mt29f8g16adadah4-it."},{"key":"e_1_2_1_35_1","volume-title":"Retrieved","year":"2018","unstructured":"Micron. 2018 . MT29F2T08CUHBBM4-3R . Retrieved February 26, 2019 from https:\/\/www.datasheets.com\/datasheet\/mt29f2t08cuhbbm4-3r:b-micron-technology-75292692. Micron. 2018. MT29F2T08CUHBBM4-3R. Retrieved February 26, 2019 from https:\/\/www.datasheets.com\/datasheet\/mt29f2t08cuhbbm4-3r:b-micron-technology-75292692."},{"key":"e_1_2_1_36_1","volume-title":"BEE3 Established","year":"2008","unstructured":"Microsoft. 2018. BEE3 Established : February 26, 2008 . https:\/\/www.microsoft.com\/en-us\/research\/project\/bee3\/ Microsoft. 2018. BEE3 Established: February 26, 2008. https:\/\/www.microsoft.com\/en-us\/research\/project\/bee3\/"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2654822.2541988"},{"key":"e_1_2_1_39_1","volume-title":"Retrieved","author":"SIG.","year":"2018","unstructured":"PCI- SIG. 2018 . Frequently Asked Questions: PCI Express - 3.0 . Retrieved February 26, 2019 from https:\/\/pcisig.com\/faq?field_category_value%5B%5D&equals;pci_express_3.0&keys&equals;&equals;&equals;. PCI-SIG. 2018. Frequently Asked Questions: PCI Express - 3.0. Retrieved February 26, 2019 from https:\/\/pcisig.com\/faq?field_category_value%5B%5D&equals;pci_express_3.0&keys&equals;&equals;&equals;."},{"key":"e_1_2_1_40_1","volume-title":"Retrieved","author":"SIG.","year":"2018","unstructured":"PCI- SIG. 2018 . Frequently Asked Questions: PCI Express - 4.0 . Retrieved February 26, 2019 from https:\/\/pcisig.com\/faq?field_category_value%5B%5D&equals;pci_express_4.0&keys&equals;&equals;&equals;. PCI-SIG. 2018. Frequently Asked Questions: PCI Express - 4.0. Retrieved February 26, 2019 from https:\/\/pcisig.com\/faq?field_category_value%5B%5D&equals;pci_express_4.0&keys&equals;&equals;&equals;."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211890.3211900"},{"key":"e_1_2_1_42_1","volume-title":"Retrieved","year":"2017","unstructured":"RegexLib. 2017 . Regular Expression Library . Retrieved February 26, 2019 from http:\/\/regexlib.com\/. RegexLib. 2017. Regular Expression Library. Retrieved February 26, 2019 from http:\/\/regexlib.com\/."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.94"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2012.6169044"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrg2857"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914)","author":"Seshadri Sudharsan","year":"2014","unstructured":"Sudharsan Seshadri , Mark Gahagan , Meenakshi Sundaram Bhaskaran , Trevor Bunker , Arup De , Yanqin Jin , Yang Liu , 2014 . Willow: A user-programmable SSD . In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914) . 67--80. Sudharsan Seshadri, Mark Gahagan, Meenakshi Sundaram Bhaskaran, Trevor Bunker, Arup De, Yanqin Jin, Yang Liu, et al. 2014. Willow: A user-programmable SSD. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914). 67--80."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201901)","author":"Sidhu Reetinder","unstructured":"Reetinder Sidhu and Viktor K. Prasanna . 2001. Fast regular expression matching using FPGAs . In Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201901) . IEEE, Los Alamitos, CA, 227--238. Reetinder Sidhu and Viktor K. Prasanna. 2001. Fast regular expression matching using FPGAs. In Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201901). IEEE, Los Alamitos, CA, 227--238."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035954"},{"key":"e_1_2_1_49_1","volume-title":"Retrieved","year":"2017","unstructured":"Snort. 2017 . Snort\u2014Network Intrusion Detection and Prevention System . Retrieved February 26, 2019 from https:\/\/www.snort.org\/. Snort. 2017. Snort\u2014Network Intrusion Detection and Prevention System. Retrieved February 26, 2019 from https:\/\/www.snort.org\/."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079856.3080207"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.5"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the IEEE 32nd International Conference on Data Engineering (ICDE\u201916)","author":"Tandon Prateek","unstructured":"Prateek Tandon , Faissal M. Sleiman , Michael J. Cafarella , and Thomas F. Wenisch . 2016. Hawk: Hardware support for unstructured log processing . In Proceedings of the IEEE 32nd International Conference on Data Engineering (ICDE\u201916) . IEEE, Los Alamitos, CA, 469--480. Prateek Tandon, Faissal M. Sleiman, Michael J. Cafarella, and Thomas F. Wenisch. 2016. Hawk: Hardware support for unstructured log processing. In Proceedings of the IEEE 32nd International Conference on Data Engineering (ICDE\u201916). IEEE, Los Alamitos, CA, 469--480."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST\u201913)","author":"Tiwari Devesh","year":"2013","unstructured":"Devesh Tiwari , Simona Boboila , Sudharshan S. Vazhkudai , Youngjae Kim , Xiaosong Ma , Peter Desnoyers , and Yan Solihin . 2013 . Active flash: Towards energy-efficient, in-situ data analytics on extreme-scale machines . In Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST\u201913) . 119--132. Devesh Tiwari, Simona Boboila, Sudharshan S. Vazhkudai, Youngjae Kim, Xiaosong Ma, Peter Desnoyers, and Yan Solihin. 2013. Active flash: Towards energy-efficient, in-situ data analytics on extreme-scale machines. In Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST\u201913). 119--132."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.15"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195546"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2016.7581271"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2007.41"},{"key":"e_1_2_1_59_1","volume-title":"Retrieved","author":"Gutenberg Project","year":"2018","unstructured":"Project Gutenberg . 2018 . The Entire Project Gutenberg Works of Mark Twain by Mark Twain . Retrieved February 26, 2019 from http:\/\/www.gutenberg.org\/ebooks\/3200?msg&equals;welcome_stranger. Project Gutenberg. 2018. The Entire Project Gutenberg Works of Mark Twain by Mark Twain. Retrieved February 26, 2019 from http:\/\/www.gutenberg.org\/ebooks\/3200?msg&equals;welcome_stranger."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2771937.2771945"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1477942.1477948"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2482767.2482791"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310149","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3310149","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3310149","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:15Z","timestamp":1750212795000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310149"}},"subtitle":["A Platform for Unstructured Data Processing Inside SSD Storage"],"short-title":[],"issued":{"date-parts":[[2019,2,28]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3310149"],"URL":"https:\/\/doi.org\/10.1145\/3310149","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,28]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}