{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:29:30Z","timestamp":1768105770151,"version":"3.49.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["DAAD19-02-1-0389"],"award-info":[{"award-number":["DAAD19-02-1-0389"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0964474"],"award-info":[{"award-number":["CCF-0964474"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            This article presents a new, memory efficient and cache-optimized algorithm for simultaneously searching for a large number of patterns in a very large corpus. This algorithm builds upon the Rabin-Karp string search algorithm and incorporates a new type of Bloom filter that we call a\n            <jats:italic>feed-forward Bloom filter<\/jats:italic>\n            . While it retains the asymptotic time complexity of previous multiple pattern matching algorithms, we show that this technique, along with a CPU architecture-aware design of the Bloom filter, can provide speed-ups between 2\u00d7 and 30\u00d7, and memory consumption reductions as large as 50\u00d7 when compared with grep. Our algorithm is also well suited for implementations on GPUs: A modern GPU can search for 3 million patterns at a rate of 580MB\/s, and for 100 million patterns (a prohibitive number for traditional algorithms) at a rate of 170MB\/s.\n          <\/jats:p>","DOI":"10.1145\/2133803.2330085","type":"journal-article","created":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T12:50:57Z","timestamp":1350391857000},"source":"Crossref","is-referenced-by-count":11,"title":["Exact pattern matching with feed-forward bloom filters"],"prefix":"10.1145","volume":"17","author":[{"given":"Iulian","family":"Moraru","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David G.","family":"Andersen","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,9,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629577"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 7th USENIX Symposium on Networked Design and Implementation (NSDI'10)","author":"Cha S. K."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Chazelle B."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/256163.256168"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872787"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646233.682242"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/285237.285287"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1269899.1254916"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 17th AoM\/IAoM Conference on Computer Science.","author":"Kim S."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06)","author":"Kirsch A."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2006.315851"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-3-8"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM'96)","volume":"1075","author":"Muth R."},{"key":"e_1_2_1_19_1","unstructured":"Putze F. Sanders P. and Johannes S. 2007. Cache- hash- and space-efficient bloom filters. http:\/\/algo2.iti.kit.edu\/singler\/publications\/cacheefficientbloomfilters-wea2007.pdf.  Putze F. Sanders P. and Johannes S. 2007. Cache- hash- and space-efficient bloom filters. http:\/\/algo2.iti.kit.edu\/singler\/publications\/cacheefficientbloomfilters-wea2007.pdf."},{"key":"e_1_2_1_20_1","unstructured":"Wu S. and Manber U. 1994. A fast algorithm for multi-pattern searching. Tech. rep. TR-94-17 Department of Computer Science University of Arizona.  Wu S. and Manber U. 1994. A fast algorithm for multi-pattern searching. Tech. rep. TR-94-17 Department of Computer Science University of Arizona."},{"key":"e_1_2_1_21_1","unstructured":"www-rtw. Read the Web Project Webpage. http:\/\/rtw.ml.cmu.edu\/readtheweb.html.  www-rtw. Read the Web Project Webpage. http:\/\/rtw.ml.cmu.edu\/readtheweb.html."},{"key":"e_1_2_1_22_1","unstructured":"www-ssuis. Streptococcus Suis Sequencing Webpage. http:\/\/www.sanger.ac.uk\/Projects\/S_suis.  www-ssuis. Streptococcus Suis Sequencing Webpage. http:\/\/www.sanger.ac.uk\/Projects\/S_suis."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2330085","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133803.2330085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:05:52Z","timestamp":1750241152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2330085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":22,"alternative-id":["10.1145\/2133803.2330085"],"URL":"https:\/\/doi.org\/10.1145\/2133803.2330085","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}