loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2005 IEEE International Conference on Application-Specific Systems, Architecture Processors (ASAP'05)
A Parallel Automaton String Matching with Pre-Hashing and Root-Indexing Techniques for Content Filtering Coprocessor
Samos, Greece
July 23-July 25
ISBN: 0-7695-2407-9
Kuo-Kun Tseng, National Chiao Tung University, Taiwan
Ying-Dar Lin, National Chiao Tung University, Taiwan
Tsern-Huei Lee, National Chiao Tung University, Taiwan
Yuan-Cheng Lai, National Taiwan University of Science and Technology, Taiwan

We propose a new Parallel Automaton string matching approach and its hardware architecture for content filtering coprocessor. This new approach can improve the average matching time of the Parallel Automaton with Pre-Hashing and Root-Indexing techniques. The Pre-Hashing technique uses a hashing function to verify quickly the text against the partial patterns in the Automaton, and the Root-Indexing technique matches multiple bytes for the root state in one single matching. A popular Automaton algorithm, Aho-Corasick (AC) is chosen to be implemented by adding the two techniques; we employ these two techniques in a memory efficient version of AC namely Bitmap AC. For the average-case time, our approach improves Bitmap AC by 494% and 224% speedup for URL and Virus patterns, respectively. Since Pre- Hashing and Root-Indexing techniques can be concurrently executed with Bitmap AC in the hardware, our proposed approach has the same worst-case time as Bitmap AC.

Citation:
Kuo-Kun Tseng, Ying-Dar Lin, Tsern-Huei Lee, Yuan-Cheng Lai, "A Parallel Automaton String Matching with Pre-Hashing and Root-Indexing Techniques for Content Filtering Coprocessor," asap, pp.113-118, 2005 IEEE International Conference on Application-Specific Systems, Architecture Processors (ASAP'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.