CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Parallel String Matching Problems with Computing Models – An Analysis of the Most Recent Studies

by K Butchi Raju, Chinta Someswara Rao, S. Viswanadha Raju
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 76 - Number 15
Year of Publication: 2013
Authors: K Butchi Raju, Chinta Someswara Rao, S. Viswanadha Raju
10.5120/13321-0738

K Butchi Raju, Chinta Someswara Rao, S. Viswanadha Raju . Parallel String Matching Problems with Computing Models – An Analysis of the Most Recent Studies. International Journal of Computer Applications. 76, 15 ( August 2013), 7-25. DOI=10.5120/13321-0738

@article{ 10.5120/13321-0738,
author = { K Butchi Raju, Chinta Someswara Rao, S. Viswanadha Raju },
title = { Parallel String Matching Problems with Computing Models – An Analysis of the Most Recent Studies },
journal = { International Journal of Computer Applications },
issue_date = { August 2013 },
volume = { 76 },
number = { 15 },
month = { August },
year = { 2013 },
issn = { 0975-8887 },
pages = { 7-25 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume76/number15/13321-0738/ },
doi = { 10.5120/13321-0738 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:45:58.291238+05:30
%A K Butchi Raju
%A Chinta Someswara Rao
%A S. Viswanadha Raju
%T Parallel String Matching Problems with Computing Models – An Analysis of the Most Recent Studies
%J International Journal of Computer Applications
%@ 0975-8887
%V 76
%N 15
%P 7-25
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

we survey the current techniques to handle with the problem of parallel string matching with computing models. This is becoming a more and more relevant issue for many fast growing areas such as information retrieval and computational biology. We focus on current developments of parallel string matching, computing models, and the central ideas of the algorithms and their complexities. We present the performance of the different algorithms and their effectiveness. Finally this analysis helps the researchers to develop the better technique.

References
  1. Chinta Someswararao, K Butchiraju, S ViswanadhaRaju, "Recent Advancement is Parallel Algorithms for String matching on computing models - A survey and experimental results", LNCS, Springer,pp. 270-278, ISBN: 978-3-642-29279-8 ,2011.
  2. Chinta Someswararao, K Butchiraju, S ViswanadhaRaju, "PDM data classification from STEP- an object oriented String matching approach", IEEE conference on Application of Information and Communication Technologies, pp. 1-9, ISBN: 978-1-61284-831-0, 2011.
  3. Chinta Someswararao, K Butchiraju, S ViswanadhaRaju, "Recent Advancement is Parallel Algorithms for String matching - A survey and experimental results", IJAC, Vol 4 issue 4, pp-91-97, 2012.
  4. Simon Y. and Inayatullah M. , "Improving Approximate Matching Capabilities for Meta Map Transfer Applications," Proceedings of Symposium on Principles and Practice of Programming in Java, pp. 143-147, 2004.
  5. Chinta Someswararao, K Butchiraju, S ViswanadhaRaju, "Parallel Algorithms for String Matching Problem based on Butterfly Model", pp. 41-56, IJCST, Vol. 3, Issue 3, July – Sept, ISSN 2229-4333, 2012.
  6. Chinta Someswararao, K Butchiraju, S ViswanadhaRaju, "Recent Advancement is String matching algorithms- A survey and experimental results", IJCIS,Vol 6 No 3, pp. 56-61, 2013.
  7. S. viswanadha raju,"parallel string matching algorithm using grid", "international journal of distributed and parallel systems" (ijdps) vol. 3, no. 3, 2012.
  8. Leslie G. Valiant, A bridging model for parallel computation, Commun. ACM, volume 33, issue 8, August, 1990, pages 103—111
  9. I. Foster. Designing and Building Paral lel Programs. Addison Wesley, 1996.
  10. I. Foster and S. Tuecke. Parallel Programming with PCN. Technical Report ANL-91/32, Argonne National Laboratory, Argonne, December 1991.
  11. J. Darlinton, M. Ghanem, H. W. To (1993), "Structured Parallel Programming", In Programming Models for Massively Parallel Computers. IEEE Computer Society Press. 1993
  12. N. Tuck, T. Sherwood, B. Calder, and G. Varghese. Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection. In Proceedings of IEEE Infocom, Hong Kong, March 2004.
  13. Y. H. Cho, S. Navab, and W. H. Mangione-Smith. Specialized Hardware for Deep Network Packet Filtering. In Proceedings of the 12th International Conference on Field-Programmable Logic and Applications (FPL'02), pages 452–461, London, UK, 2002. Springer-Verlag.
  14. I. Sourdis and D. Pnevmatikatos. Fast, Large-Scale String Match for a 10 Gbps FPGA-based Network Intrusion Detection System. In Proceedings of the 13th International Conference on Field Programmable Logic and Applications (FPL'03), Lisbon, Portugal, September 2003.
  15. S. Dharmapurikar, P. Krishnamurthy, T. S. Sproull, and J. W. Lockwood. Deep Packet Inspection using Parallel Bloom Filters. IEEE Micro, 24(1):52–61, 2004.
  16. J. Nandhini, Dr. M. Nithya, Dr. S. Prabhakaran "Advance virus detection using combined techniques of pattern matching and dynamic instruction sequences", International Journal of Communication and Computer Technologies, Volume 01 – No. 45, pp. 156-161 2013
  17. Safaa O. Al-Mamory et al. ," String Matching Enhancement for Snort IDS" , pp. 1020-1023.
  18. S. Dharmapurikar and J. W. Lockwood, "Fast and scalable pattern matching for network intrusion detection system", IEEE JSAC, Vol. 24, No. 10, pp. 1781–1792, 2006.
  19. N. Hua, H. Song and T. V. Lakshman, "Variable-stride multipattern matching for scalable deep packet inspection", in Proc. of INFOCOM, Rio de Janeiro, Brazil, pp. 415–423, 2009.
  20. H. Lu, K. Zheng, B. Liu, X. Zhang and Y. Liu, "A memoryefficient parallel string matching architecture for high-speed intrusion detection", IEEE JSAC, Vol. 24, No. 10, pp. 1793–1804, 2006.
  21. B. C. Brodie, D. E. Taylor and R. K. Cytron, "A scalable architecture for high-througshput regular-expression pattern matching", in Proc. Of ACM/IEEE International Symposium on Computer Architecture (ISCA), Boston, MA, USA, pp. 191–202, 2006.
  22. D. Ficara, G. Antichi, A. D. Pietro, S. Giordano, G. Procissi and F. Vitucci, "Sampling techniques to accelerate pattern matching in network intrusion detection systems", in Proc. of IEEE ICC, Cape Town, South Africa, pp. 1–5, 2010.
  23. Seongyong Ahn, Hyejong Hong, Hyunjin Kim, Jin-Ho Ahn, Dongmyong Baek and Sungho Kang, "A Hardware-Efficent Multi-character String Matching Architecture Using Brute-force Algorithm, ISOCC, pp. 464-467, 2009.
  24. WANG Xiaofei, HU Chengchen, TANG Yi, ZHANG Ting, WU Chunming, LIU Bin and WANG Xiaojun, "Parallel Length-based Matching Architecture for High Throughput Multi-Pattern Matching", Chinese Journal of Electronics, Vol. 21, No. 3, pp. 489-494,2012.
  25. HyunJin Kim and Seung-Woo Lee, "A Hardware-Based String Matching Using State Transition Compression for Deep Packet Inspection", ETRI Journal, Volume 35, Number 1,pp. 154-157 ,2013
  26. Yi-Hua E. Yang et al. ," Head-Body Partitioned String Matching for Deep Packet Inspection with Scalable and Attack-Resilient Performance" , IEEE, 2010.
  27. Akhtar Rasool and Nilay Khare, "Parallelization of KMP String Matching Algorithm on Different SIMD architectures-Multi-Core and GPGPU", International Journal of Computer Applications, pp. 26-28, 2012.
  28. cheng zhong and guo-liang chen, " a fast determinate string matching algorithm for the network intrusion detection systems", Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, pp. ,3173-3177, 2007
  29. Panwei Cao and Suping Wu , "Parallel Research on KMP Algorithm", pp. 4252-4255, IEEE, 2011.
  30. Wei Lin, Bin Liu , "Pipelined Parallel AC-based Approach for Multi-String Matching", 14th IEEE International Conference on Parallel and Distributed Systems, pp. 665- 672,2008.
  31. Chuanpeng Chen and Zhongping Qin A Bit-split Byte-parallel String Matching Architecture, IEEE ,pp. 214- 217, 2009.
  32. HyunJin Kim, Hyejeong Hong, Hong-Sik Kim, and Sungho Kang, "A Memory-Efficient Parallel String Matching for Intrusion Detection Systems", IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, pp. 1004-1006, 2009.
  33. Mustafa Abdul Sahib Naser, Nur'Aini Abdul Rashid, and Mohammed Faiz Aboalmaaly, "Quick-Skip Search Hybrid Algorithm for the Exact String Matching Problem" , International Journal of Computer Theory and Engineering Vol. 4, No. 2, pp. 259-265, 2012
  34. M. Alicherry, M. Muthuprasanna and V. Kumar, High speed pattern matching for network IDS/IPS, IEEE ICNP, pp. 187-196, 2006.
  35. D. Pao, W. Lin and B. Liu, A memory-efficient pipelined implementation of the Aho-Corasick string- matching algorithm, ACM Trans. on Archit. Code Optim. , vol. 7, pp. 1-27, 2010.
  36. W. Lin and B. Liu, Pipelined parallel AC-based approach for multi-string matching, IEEE ICPADS, pp. 665-672, 2008.
  37. N. Hua, H. Song and T. V. Lakshman, Variable-stride multi-pattern matching for scalable deep packet inspection, IEEE INFOCOM, pp. 415-423, 2009.
  38. D. P. Scarpazza, O. Villa and F. Petrini, Exact multi-pattern string matching on the cell/b. e. processor, ACM CF, 2008.
  39. Y. Sugawara, M. Inaba and K. Hiraki, Over 10Gbps string matching mechanism for multi-stream packet scanning systems, Field Programmable Logic and Application, vol. 3203, pp. 484-493, 2004.
  40. Chien-Chi Chen and Sheng-De Wang , "A Multi-Character Transition String Matching Architecture Based On Aho-Corasick Algorithm", International Journal of Innovative Computing, Information and Control, pp. 8367-8386,2012.
  41. HyunJin Kim et al. ," A Memory-Efficient Bit-Split Parallel String Matching using Pattern Dividing for Intrusion Detection Systems", IEEE Transactions On Parallel And Distributed Systems, Third Draft, September 2010, pp. 1-8,2011.
  42. Yi-Hua E. Yang and Viktor K. Prasanna, "Robust and Scalable String Pattern Matching for Deep Packet Inspection on Multi-core Processors", IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, pp. 1-11,2012.
  43. Yue Hu et al. ," A Fast Algorithm for Multi-String Matching Based on Automata Optimization" 2nd International Conference on Future Computer and Communication,pp. 379-383,Vol 2,2010
  44. Junghak Kim et al. ,"Programmable Architecture for NFA-based String Matching" , pp. 484-489, IEEE, 2010.
  45. Yi Tang et al. ," Independent Parallel Compact Finite Automatons for Accelerating Multi-String Matching", IEEE Globecom 2010 proceedings, 2010.
  46. Xiaofei Wang, Yang Xu, Junchen Jiang, Olga Ormond, Bin Liu, and Xiaojun Wang "StriFA: Stride Finite Automata for High-Speed Regular Expression Matching in Network Intrusion Detection Systems", IEEE SYSTEMS JOURNAL, VOL. 7, NO. 3, pp. 374-384, 2013.
  47. Weirong Jiang et al. ," Scalable Multi-Pipeline Architecture for High Performance Multi-Pattern String Matching",IEEE,2010.
  48. Yu Cheng and Tao Zhang, "Design of Fast Multiple String Searching Based on Improved Prefix Tree", 2010 Third International Conference on Knowledge Discovery and Data Mining, pp. 111-114, 2010.
  49. Shmuel T. Klein and Dana Shapira" The String-to-Dictionary Matching Problem",2011 Data Compression Conference, pp. 143-152, IEEE, 2011.
  50. KSMV Kumar, S. Viswanadha Raju and A. Govardhan, "Overlapped Text Partition Algorithm for Pattern Matching on Hypercube Networked Model", GJCST, pp. 1-8,2013.
  51. Yao Xin , Benben Liu, Biao Min, WillX. Y. Li, Ray C. C. Cheung, Anthony S. Fong, Ting Fung Chan" Parallel architecture for DNA sequence inexact matching with Burrows-Wheeler Transform", Microelectronics Journal, pp. 670-682,Elsevier,2013.
  52. Hoang Le, and Viktor K. Prasanna, "A Memory-Efficient and Modular Approach for Large-Scale String Pattern Matching", IEEE Transactions on Computers, VOL. 62, NO. 5, pp. 844-857, 2013.
  53. Jiaying Wang, Xiaochun Yang, Bin Wang, "Cache-Aware Parallel Approximate Matching and Join Algorithms Using BWT", ACM, 2013.
  54. Christoph Strecha et al. ," LDAHash: Improved matching with smaller descriptors", IEEE Transactions On Pattern Analysis And Machine Intelligence, pp. 1-14, 2011.
  55. Edward Fernandez et al. ," String Matching in Hardware using the FM-Index", IEEE International Symposium on Field-Programmable Custom Computing Machines, pp. 218-225, IEEE computer society, 2011
  56. TAN Jianlong et al. ," Speeding up Pattern Matching by Optimal Partial String Extraction", the first international workshop on security in computers, networking and communications, pp. 1030-1035, IEEE, 2011.
  57. Rajesh Prasad, Anuj Kumar Sharma, Alok Singh, Suneeta Agarwal1 and Sanjay Misra, "Efficient bit-parallel multi-patterns approximate string matching algorithms", Scientific Research and Essays Vol. 6(4), pp. 876-881, 18 February, 2011.
  58. Mosleh M. Abu-Alhaj et al. ," An Innovative Platform To Improve The Performance Of Exact-String Matching ALGORITHMS",2010, (IJCSIS) International Journal of Computer Science and Information Security,pp. 280-283, Vol. 7, No. 1, 2010
  59. Mosleh M. Abu-Alhaj et al. ," An Innovative Platform To Improve The Performance Of Exact-String Matching ALGORITHMS",2010, (IJCSIS) International Journal of Computer Science and Information Security,pp. 280-283, Vol. 7, No. 1, 2010
  60. Benedikt Forchhammer, Thorsten Papenbrock, Thomas Stening, Sven Viehmeier, Uwe Draisbach, Felix Naumann, "Duplicate Detection on GPUs", pp. 165-188,2013
  61. Antonino Tumeo and G et al. ," Aho-Corasick String Matching on Shared and Sistributed Memory Parallel Architectures", IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, pp. 1-9, IEEE, 2011.
  62. Antonino Tumeo, Oreste Villa, and Daniel G. Chavarr?´a-Miranda, "Aho-Corasick String Matching on Shared and Distributed-Memory Parallel Architectures", IEEE Transactions on Parallel and Distributed Systems, VOL. 23, NO. 3, PP. 436-443, 2012.
  63. Vinod. O, B. M. Sagar, "Hash-Based String Matching Algorithm For Network Intrusion Prevention systems (NIPS)", International Journal of Advanced Computer Theory and Engineering, Volume-2, Issue-2, pp. 31-35, 2013.
  64. Oren Ben-Kiki, Philip Bille, Dany Breslauer, Leszek Gasieniec, Roberto Grossi, Oren Weimann "Towards Optimal Packed String Matching", pp. 1-33, ---July 10, 2013.
  65. H. D. Cheng and K. S. Fu, "VLSI Architecture for String Matching and Pattern Matching," Pattern Recognition, Vol. 20, pp. 125-141, 1987.
  66. Daniel P. Lopresti, "P-NAC : A Systolic Array for Comparing Nucleic Acid Sequences," Computer, pp. 98- 99, July 1987.
  67. Amar Mukhopadhyay, "Hardware Algorithms for Nonnumeric Computation," IEEE trans. on Computers, Vol. C-28, No. 6, pp. 384-394, June 1979.
  68. Bradly Fawcett, "Reconfiguring a Computing Pattern," Electronic Engineering Times, Manhasset, pp. 64- , April. 1995.
  69. M. J. Foster and H. T. Kung, "The Design of Special- Purpose VLSI Chips," Computer, pp. 26-38, Jan. 1980.
  70. Carla Correa Tavares dos Reis and Oswaldo Cruz, "Approximate String Matching Algorithm Using Parallel Methods for Molecular Sequence Camparisons", IEEE, pp. 140-143,2005.
  71. Muhammad Zubair et al. ," Text Scanning approach for Exact String Matching", International Conference on Networking and Information Technology,pp. 118-121,2010.
  72. Yunho Oh , Doohwan Oh , Won W. Ro "GPU-Friendly Parallel Genome Matching with Tiled Access and Reduced State Transition Table", Springer, pp. 526-551, 2013.
  73. Tomohiro I , Shunsuke Inenaga, Masayuki Takeda "Palindrome pattern matching" Theoretical Computer Science, pp. 162-170,Elsevier,2013.
  74. Fang Xiangyan et al. ," The Research and Improving for Multi-pattern String Matching Algorithm", IEEE, 2010.
  75. Zhengda Xiong "A Composite Boyer-Moore Algorithm for the String Matching Problem", The 11th International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 492-496, IEEE, 2010.
  76. Golnaz Badkobeh,Gabriele Fici,Steve Kroonc,Zsuzsanna Liptákd, " Binary jumbled string matching for highly run-length compressible texts", Information Processing Letters, pp. 604-608,2013.
  77. Dan Guo , Xuegang Hu , Fei Xie , XindongWu "Pattern matching with wildcards and gap-length constraints based on a centrality-degree graph" ,Springer, pp. 57-74, 2013.
Index Terms

Computer Science
Information Sciences

Keywords

Text processing IRS computing models string matching parallel algorithms.

Powered by PhDFocusTM