doi: 10.18178/ijfcc.2017.6.1.479
On Performance Evaluation of BM-Based String Matching Algorithms in Distributed Computing Environment
Kunaphas Kongkitimanon
,
Boonsit Yimwadsana
- Faculty of Information and Communication Technology and Integrative Computational Bioscience Center, Mahidol University, Thailand.
Abstract
String matching algorithms plays an importantrole in many applications of computer science: in particularsearching, retrieving and processing of data. Various fields thatrely on computer science for computing and data processingsuch as science, informatics (e.g. biology, medical, andhealthcare), statistics, image, video/signal processing andcomputational aspect of business (e.g. finance, accounting, andcomputer security) would benefit greatly from efficient datasearch algorithm, in particular string matching. Anyapplications involving the use of database would use stringmatching algorithm. Many string matching algorithms such asTBM (Turbo Boyer Moore), BMH (Boyer-Moore-Horspool),BMHS (Boyer Moore Horspool Sundays, and BMHS2 (BoyerMoore Horspool Sundays 2) were introduced based on thecelebrated BM (Boyer-Moore) algorithm considered to be oneof the early efficient string searching algorithms. Althoughthese algorithm offers significant performance improvementover the BM algorithm, they were designed with the assumptionof single core computer architecture which executes thealgorithm in a serialized manner. Today,multiple-core-processor computers are very common, andapplications are designed to process big data thanks to theadvanced in computing technology of various fields. Highperformance computing system utilizing parallel anddistributed computing has started to become popular. Thiswork evaluates and compares the performance of theaforementioned string matching algorithms in parallel anddistributed environment for high performance computing withrespect to that of the serialized single-core computing platform.In this work, the variants of BM algorithms are implementedand evaluated on Apache Spark, a popular distributedcomputing platform, by executing a set of queries of differentsearch pattern lengths.
Keywords
- Apache spark
- Boyer Moore
- distributedcomputing
- string matching
How to Cite
Kunaphas Kongkitimanon and Boonsit Yimwadsana, "On Performance Evaluation of BM-Based String Matching Algorithms in Distributed Computing Environment," International Journal of Future Computer and Communication, vol. 6, no. 1, pp. 1-5, 2017. https://doi.org/ 10.18178/ijfcc.2017.6.1.479
Copyright & License
Copyright © 2017 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).