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
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ASAP.2005.8
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||