원문정보
초록
영어
With the coming of the big data era, the data processing in large scale comes out with a new challenge. However, string matching still plays an important role in the network security and information retrieval fields, because of the large size of pattern set with the overhead of memory and access memory time. Improving the string matching algorithm to adapt to the large scale tasks is desirable and meaningful. In this paper, we present and implement a parallel algorithm of multiple string matching based on multi-core platform. In addition, this work focuses on the partition of pattern set by using genetic algorithm through the internal relation of the patterns to reduce the memory overhead and execution performance. Compared with the classical ones, our experiments on both high and low hit-rate data demonstrate that the performance of algorithm enhances about on average by 20%-40% in general. Besides, the proposed algorithm reduces the memory cost on average by 4%-20%.
목차
1. Introduction
2. Related Works
2.1. Aho-Corasick Algorithm and Optimization
2.2. Parallel DFA on Multi-core Architecture
2.3. Set Partitioning with Genetic Algorithm
3. Parallel Multiple String Matching Algorithm Based on Set-Partition
3.1. Preliminary Knowledge
3.2. The Implementation of Parallel Algorithm
4. Experiments and Results
4.1. Analysis of the Memory Overhead
4.2. Change of Variable Core Number
4.3. Analysis with High and Low Hit Rate
5. Conclusions
Acknowledgements
References