String matching with multicore CPUs: Performing better with the Aho-Corasick algorithm

Multiple string matching is known as locating all the occurrences of a given number of patterns in an arbitrary string. It is used in bio-computing applications where the algorithms are commonly used for retrieval of information such as sequence analysis and gene/protein identification. Extremely la...

Full description

Saved in:
Bibliographic Details
Main Authors: Arudchutha, S., Nishanthy, T., Ragel, R. G.
Format: Conference Proceeding
Language:English
Subjects:
Aho-Corasick
Algorithm design and analysis
Instruction sets
Multicore processing
Multicore processor
Pattern matching
POSIX threads
Software algorithms
Throughput
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Multiple string matching is known as locating all the occurrences of a given number of patterns in an arbitrary string. It is used in bio-computing applications where the algorithms are commonly used for retrieval of information such as sequence analysis and gene/protein identification. Extremely large amount of data in the form of strings has to be processed in such bio-computing applications. Therefore, improving the performance of multiple string matching algorithms is always desirable. Multicore architectures are capable of providing better performance by parallelizing the multiple string matching algorithms. The Aho-Corasick algorithm is the one that is commonly used in exact multiple string matching algorithms. The focus of this paper is the acceleration of Aho-Corasick algorithm through a multicore CPU based software implementation. Through our implementation and evaluation of results, we prove that our method performs better compared to the state of the art.
ISSN:2164-7011
2690-3423
DOI:10.1109/ICIInfS.2013.6731987