{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:06:44Z","timestamp":1768108004685,"version":"3.49.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>Multi-pattern matching involves matching a data item against a large database of \"signature\" patterns. Existing algorithms for multi-pattern matching do not scale well as the size of the signature database increases. In this paper, we present sigMatch -- a fast, versatile, and scalable technique for multi-pattern signature matching. At its heart, sigMatch organizes the signature database into a (processor) cache-efficient q-gram index structure, called the sigTree. The sigTree groups patterns based on common sub-patterns, such that signatures that don't match can be quickly eliminated from the matching process. The sigTree also uses parallel Bloom filters and a technique to reduce imbalances across groups, for improved performance. Using extensive empirical evaluation across three diverse domains, we show that sigMatch often outperforms existing methods by an order of magnitude or more.<\/jats:p>","DOI":"10.14778\/1920841.1920987","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1173-1184","source":"Crossref","is-referenced-by-count":16,"title":["SigMatch"],"prefix":"10.14778","volume":"3","author":[{"given":"Ramakrishnan","family":"Kandhan","sequence":"first","affiliation":[{"name":"University of Wisconsin--Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Teletia","sequence":"additional","affiliation":[{"name":"University of Wisconsin--Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jignesh M.","family":"Patel","sequence":"additional","affiliation":[{"name":"University of Wisconsin--Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alexa Web Rankings. http:\/\/www.alexa.com.  Alexa Web Rankings. http:\/\/www.alexa.com."},{"key":"e_1_2_1_2_1","unstructured":"ClamAV Anti-Virus System. http:\/\/www.clamav.net\/.  ClamAV Anti-Virus System. http:\/\/www.clamav.net\/."},{"key":"e_1_2_1_3_1","unstructured":"DARPA Intrusion Detection Evaluation Data Set. http:\/\/www.ll.mit.edu\/mission\/communications\/ist\/corpora\/ideval\/data\/1998data.html.  DARPA Intrusion Detection Evaluation Data Set. http:\/\/www.ll.mit.edu\/mission\/communications\/ist\/corpora\/ideval\/data\/1998data.html."},{"key":"e_1_2_1_4_1","unstructured":"Snort Intrusion Detection System. http:\/\/www.snort.org\/.  Snort Intrusion Detection System. http:\/\/www.snort.org\/."},{"key":"e_1_2_1_5_1","unstructured":"Spam Corp. http:\/\/www.spamcop.net.  Spam Corp. http:\/\/www.spamcop.net."},{"key":"e_1_2_1_6_1","unstructured":"Valgrind. http:\/\/www.valgrind.org\/.  Valgrind. http:\/\/www.valgrind.org\/."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376697"},{"key":"e_1_2_1_11_1","first-page":"418","volume-title":"ICDE","author":"Cho J.","year":"2002"},{"key":"e_1_2_1_12_1","first-page":"118","volume-title":"Commentz-Walter. A String Matching Algorithm Fast on the Average. In Proceedings of the 6th Colloquium, on Automata, Languages and Programming","author":"B.","year":"1979"},{"key":"e_1_2_1_13_1","first-page":"169","volume-title":"CIDR","author":"DeRose P.","year":"2007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2004.1268997"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJSN.2007.012824"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316782"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"e_1_2_1_18_1","first-page":"303","volume-title":"VLDB","author":"Li C.","year":"2007"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376635"},{"key":"e_1_2_1_20_1","first-page":"73","volume-title":"SSYM","author":"Miretskiy Y.","year":"2004"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1187438"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1402958.1402983"},{"key":"e_1_2_1_23_1","first-page":"1686","volume-title":"IEEE GLOBECOM","author":"Song H.","year":"2005"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2003.1195150"},{"key":"e_1_2_1_25_1","volume-title":"A Fast Algorithm for Multi-Pattern Searching. Technical report","author":"Wu S.","year":"1994"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/216585.216588"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185347.1185360"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICN.2008.119"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920987","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:46:56Z","timestamp":1672228016000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920987"}},"subtitle":["fast and scalable multi-pattern matching"],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920987"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920987","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}