The International Arab Journal of Information Technology (IAJIT)


A Framework for Distributed Pattern Matching Based on Multithreading

 Despite of the dramatic evolution in high performan ce computing we still need to devise new efficient algorithms to speed up the search process. In this paper, we pres ent a framework for a data%distributed and multithr eaded string matching approach in a homogeneous distributed environment. The main idea of this approach is to have multiple agents that concurrently search the text, each one from differe nt position. By searching the text from different positions the required pattern can be found more quickly than by searching the text from one position). Concurrent search can be achieved by two techniques; the first is by using multithreading on a single processor, in this technique each thread is responsible for searching one part of the text. The concurrency of the multit hreading technique is based on the time sharing pri nciple, so it provides us of an illusion of concurrency not pure concurrency. The second technique is by having multiprocessor m achine or distributed processors to search the text; in this technique al l of the processors search the text in a pure concu rrent way. Our approach combines the two concurrent search techniques to fo rm a hybrid one that takes advantage from the two t echniques. The proposed approach manipulates both exact string mat ching and approximate string matching with k%mismat ches. Experimental results demonstrate that this approach is an efficient solution to the problem in a homogeneous clustered system.

[1] Ababneh M., Oqeili S., and Abdeen R., Occurrences Algorithm for String Searching Based on Brute-Force Algorithm, Computer Journal of Science Publication , vol. 2, no. 1, pp. 82-85, 2006.

[2] Amihood A., Moshe L., and Ely P., Approximate Subset Matching with Don't Cares, in Proceedings of 12 th Annual ACM% SIAM Symposium on Discrete Algorithms , USA, pp. 305-306, 2001.

[3] Andersson A. and Thorup M., Dynamic String Searching, in Proceedings of 12 th Annual ACM% SIAM Symposium on Discrete Algorithms , USA, pp. 307-308, 2001.

[4] Bao R., Distributed Computing via RMI and CORBA, in Proceedings of Department Computer Since , USA, pp. 24-33, 2001.

[5] Bishop P. and Warren N., JavaSpaces in Practice , Addison Wesley, 2002.

[6] Boyer R. and Moore J., A Fast String Searching Algorithm, Computer Journal of Communications of the ACM , vol. 20, no. 10, pp. 762-772, 1977.

[7] Deitel P. and Deitel H., Java How to Program, Prentice Hall, 2003.

[8] Freeman E., Hupfer S., and Arnold K., JavaSpaces Principles Patterns and Practice , Addison Wesley, 2004.

[9] Gonzalo N., A Guided Tour to Approximate String Matching, Association for Computing Machinery Computing Surveys, vol. 33, no. 1, pp. 31-88, 2001.

[10] Huston1 L., Dynamic Load Balancing for Distributed Search, High Performance Distributed Computing, in Proceedings of 14 th IEEE International Symposium , USA, pp. 157- 166, 2005.

[11] Jin H. and Bernard A., High Performance Pattern Matching with Dynamic Load Balancing on Heterogeneous Systems, in Proceedings of 14 th Euromicro International Conference on Parallel, Distributed and Network%Based Processing , USA, pp. 285-290, 2006.

[12] Jonathan L., Analysis of Fundamental Exact and Inexact Pattern Matching Algorithms, Technical Document , Stanford University, 2004.

[13] Juval L., Programming NET Components , O Reilly and Associates, 2005.

[14] Knute D., Morris J., and Pratt V., Fast Pattern Matching in Strings, SIAM Journal of Computing , vol. 6, no. 2, pp. 323-350, 1977.

[15] Lecroq T. and Charras C., Handbook of Exact String Matching Algorithms , King's College London Publications, 2004.

[16] Mattern F., Tuning Distributed Control Algorithms for Optimal Functioning, Computer Journal of Global Optimization , vol. 2, no. 2, 1992.

[17] Mhashi M., Rawashdeh A., and Hammouri A., A Fast Approximate String Searching Algorithm, Computer Journal of Science Publication , vol. 1, no. 3, pp. 405-412, 2005.

[18] Michailidis P. and Margaritis K., On-Line Approximate String Searching Algorithms: Survey and Experimental Results, International Journal of Computer Mathematics, vol. 79, no. 8, pp. 867-888, 2002.

[19] Badoiu M. and Indyk P., Fast Approximate Pattern Matching with Few Indels via Embeddings, in Proceedings of 15 th Annual ACM%SIAM Symposium on Discrete Algorithms , Louisiana, pp. 651-652, 2004.

[20] Newmarch J., A Programmer's Guide to Jini Technology , Springer-Verlag New York, 2000.

[21] Panagiotis D. and Konstantinos G., Performance Analysis of Approximate String Searching Implementations for Heterogeneous Computing Platform, in Proceedings of IEEE International Conference on Parallel Processing Workshops , Berlin, pp. 173-180, 2003.

[22] Sedgewick R., Algorithms, Addison Wesley, 1983.

[23] Galvin S. and Gagne P., Operating Systems Concepts , John Wiley, 2004.

[24] Simon Y. and Inayatullah M., Improving Approximate Matching Capabilities for Meta Map Transfer Applications, in Proceedings of 3 rd International Symposium on Principles and 38 The International Arab Journal of Information Techn ology, Vol. 9, No. 1, January 2012 Practice of Programming in Java , Dublin, pp. 143-147, 2004.

[25] Steven S., The Algorithm Design Manual , Springer-Verlag, New York, 1997.

[26] Sun Microsystems Incorporation, Multithreading in the Solaris Operating Environment, Technical Paper , 2002.

[27] Thierry L. and Christian C., Handbook of Exact String Matching Algorithms , ACM Medium: Paperback, 2004.

[28] Yates R. and Neto B., Modern Information Retrieval , First Edition, Addison Wesley, 1999. Najib Kofahi is a professor of computer science at Yarmouk University (YU). He received his PhD in computer science from the University of Missouri-Rolla, USA in 1987. Currently, he is the Dean of the Faculty of Information Technology and Computer Sciences at YU, Jordan. He has several journal and conference research publications in a number of research areas includin g e- learning, operating systems, distributed systems, a nd performance evaluation. His teaching interests focu s on operating systems, algorithms and data structure s, computer organization and assembly language programming, and computer architecture. Ahmed Abusalama is currently working as a lecturer at Al Qassim University, The Kingdom of Saudi Arabia (KSA). He is teaching various compute modules at the preparatory year college. He received his Master in computer science from Yarmouk University, Jordan in 2006. He received his Bachelor degree in computer science fr om Al Albayt University, Jordan in 2004. He worked as a lecturer at Yarmouk University from 2006 to 2007 where he taught advanced object oriented analysis a nd design and basic computer skills courses (windows, MS office and internet).