SigMatch
Authors:
Open Access
- 1 September 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 3 (1-2) , 1173-1184
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- An efficient filter for approximate membership checking2008
- Multipattern string matching with q -gramsACM Journal of Experimental Algorithmics, 2007
- Hash-AV: fast virus signature scanning by cache-resident filtersInternational Journal of Security and Networks, 2007
- Deep packet inspection using parallel bloom filtersIEEE Micro, 2004
- Flexible String Matching Against Large Databases in Practice2004
- Efficient PDA synchronizationIEEE Transactions on Mobile Computing, 2003
- Hitting the memory wallACM SIGARCH Computer Architecture News, 1995
- A string matching algorithm fast on the average1979
- A fast string searching algorithmCommunications of the ACM, 1977
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970