A novel Parallel Algorithm for Edit Distance Computation.

Muhammad Murtaza Yousaf; Muhammad Umair Sadiq; LAEEQ ASLAM; WAQARUL QOUNAIN; SHAHZAD SARWAR

Author(s)

Muhammad Murtaza Yousaf Punjab University College of Information Technology, University of the Punjab, Lahore, Pakistan

Muhammad Umair Sadiq Punjab University College of Information Technology, University of the Punjab, Lahore, Pakistan

LAEEQ ASLAM Punjab University College of Information Technology, University of the Punjab, Lahore, Pakistan

WAQARUL QOUNAIN Punjab University College of Information Technology, University of the Punjab, Lahore, Pakistan

SHAHZAD SARWAR Punjab University College of Information Technology, University of the Punjab, Lahore, Pakistan

Abstract

The edit distance between two sequences is the minimum number of weighted transformation-operations that are required to transform one string into the other. The weighted transformation-operations are insert, remove, and substitute. Dynamic programming solution to find edit distance exists but it becomes computationally intensive when the lengths of strings become very large. This work presents a novel parallel algorithm to solve edit distance problem of string matching. The algorithm is based on resolving dependencies in the dynamic programming solution of the problem and it is able to compute each row of edit distance table in parallel. In this way, it becomes possible to compute the complete table in min(m,n) iterations for strings of size m and n whereas state-of-the-art parallel algorithm solves the problem in max(m,n) iterations. The proposed algorithm also increases the amount of parallelism in each of its iteration. The algorithm is also capable of exploiting spatial locality while its implementation.Additionally, the algorithm works in a load balanced way that further improves its performance. The algorithm is implemented for multicore systems having shared memory. Implementation of the algorithm in OpenMP shows linear speedup and better execution time as compared to state-of-the-art parallel approach. Efficiency of the algorithm is also proven better in comparison to its competitor.

Publication Details

Page(s) 223-232

DOI DOI not available

Published Journal: Mehran University Research Journal of Engineering and Technology, Volume: 37, Issue: 1, Year: 2018

Request the full text from PASTIC

Keywords

Speedup., OpenMP, Levenshtein Distance

References

Lan , H.,Chan , H.,Xu , Y.,Schmidt , K.,Peng , B.,Liu , W., 2016.Parallel Algorithms for Large-Scale Biological Sequence Alignment on Xeon-Phi Based Clusters”,BMC Bioinformatics 17 11 -23

Qu , J.,Fang , Z.,Liu, 2016.“A Parallel Algorithm of String Matching Based on Message Passing Interface for Multicore Processors”,International Journal of Hybrid Information Technology 9 31 -38

Mitani , Y.,Ino , F.,Hagihara , K., 2017.Parallelizing Exact and Approximate String Matching via Inclusive Scan on a GPU”,IEEE Transactions on Parallel and Distributed Systems 28 1989 -2002

Yang , C.,K., 2014.“Parallel Approaches to Edit Distance and Approximate String Matching”, -

Dhraief , A.,Issaoui , R., 2011.Belghith A., “Parallel Computing the Longest Common Subsequence (LCS) on GPUs: Efficiency and Language Suitability”,1st International Conference on Advanced Communications and Computation -

Yang , J.,Xu , Y.,Shang , Y., 2010.An Efficient Parallel Algorithm for Longest Common Subsequence Problem on GPUs”,Proceedings of World Congress on Engineering -

Kloetzli , J.,Strege , B.,Decker , J.,Olano , M., 2008.Parallel Longest Common Subsequence using Graphics Hardware”,Eurographics Symposium on Parallel Graphics and Visualization -

Churchill , D.,Gillard , P.,Hamilton , M.,Wareham , T., 2004.“Prototyping Parallel Sequence Edit Distance Algorithms in FPGA Hardware”,Proceedings of 14thAnnual New Found Land Electrical and Computer Engineering Conference -

Niewiarowski , A.,Stanuszek , M., 2014.Parallelization of the Levenshtein Distance Algorithm”,Technical Transactions 109 -122