Efficiency of multiple string searching has become more relevant with the large and redundant amount of data. The size of storage devices has increased in terms of Terabytes and modern processors are capable to perform parallel computation with multi-core architecture. Beowulf cluster architecture is considered for parallel computations, in which 40 nodes and two quad core processor servers perform multiple pattern searching operations with different algorithms. Multiple pattern searching is essential for intrusion detection systems (IDS), which has the ability to search through packets and identify content that matches known attacks. Latest advancements in DNA sequencing, web search engines, database operations, signal processing, error detection, speech and pattern recognition areas require multiple patterns searching problem to process terabytes of data. Space and time efficient string matching algorithms are therefore important for this purpose.

1. Sellers. P, The theory and computation of evolutionary distances: pattern recognition. Journal of Algorithms 1, 359–373, 1980.
2. http://www.snort.org
3. A. V. Aho and M. J. Corasick. “Efficient string matching: An aid to bibliographic search.” Communications of the ACM, 18(6), 1975, pp.333–340.
4. Sun Wu , Udi Manber, A fast algorithm for multi-pattern searching (1994)
5. http://webglimpse.net/pubs/TR94-17.pdf
6. N. Tuck, T. Sherwood, B. Calder, G. Varghese, “Deterministic memoryefficient string matching algorithms for intrusion detection,” In Proceedings of the IEEE INFOCOM Conference, 2004, pp. 333–340.
7. L. Salmela, J. Tarhio and J. Kytojoki: “Multi-pattern string matching with q-grams. ACM Journal of Experimental Algorithmics”, Volume 11, 2006.
8. Prasad J.C., K.S.M.Panicker, ‘Single pattern search implementations in a cluster computing environment’, IEEE Xplore Digital library, Digital Ecosystems and Technologies(DEST), 2010 4th IEEE International Conference 13-16 April 2010 on ISSN:2150-4938, Page 391-396.
9. A. Petitet, R. C. Whaley, J. Dongarra, A. Cleary,
10. Sept 2008, HPL - A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers, Innovative Computing Laboratory, University of Tenneesse. doi: http://www.netlib.org/benchmark/hpl/
11. Prasad J.C., K.S.M.Panicker,
12. 2009 ‘Beowulf Dakshina Cluster Architecture with Linux Debian Operating system for MPI Programming’, Proceedings of International Conference on Information Processing,, Bangalore, India ISBN: 978-93-80026-75-2, Page 350.
13. P.D.Michailidis, K.G.Margaritis
14. 2000, Parallel String Matching Algorithm: A bibliographical review, Technical Report, Dept.of Applied Informatics, University of Macedonia.
15. Panagiotis D. Michailidis and Konstantinos G. Margaritis
16. 2001, ‘Parallel Text Searching Application on a Heterogeneous Cluster of Workstations’, IEEE Computer Society Proceedings of the International Conference on Parallel Processing Workshops (ICPPW’01), Page. 153
17. Mansoor Alicherry, M. Muthuprasanna, Vijay Kumar, ‘High Speed Pattern Matching for Network IDS/IPS’, 2006 IEEE
18. ‘Replica Selection in the Globus Data Grid’, A. V. Aho and M. J. Corasick. “Efficient string matching: An aid to bibliographic search.” Communications of the ACM, 18(6), 1975, pp.333–340.

Beowulf cluster Multiple string matching algorithm performance MPI Programming