A Novel Parallel Algorithm for Edit Distance Computation
Journal Title: Mehran University Research Journal of Engineering and Technology - Year 2018, Vol 37, Issue 1
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.
Authors and Affiliations
M. M. Yousaf, M. U. Sadiq, L. Aslam, Waqar-ul Qounain, S. Sarwar
Examining Knowledge Transfer Channels for Development of Environment Sector in Sindh
It is well understood that the creation and applications of new knowledge is the primary factor that drives economic growth. Aim ofthis research is to examine the KTCs (Knowledge Transfer Channels) in the universities of...
Illustration, Detection & Prevention of Sleep Deprivation Anomaly in Mobile Ad Hoc Networks
MANETs (Mobile Ad Hoc Networks) have applications in various walks of life from rescue operations to battle fieled operations, personal and commercial. However, routing operations in MANETs are still vulnerable to anomal...
Evaluation of Soil Engineering Characteristics in Jalalpur Region, Pakistan
This study deals with the evaluation of soil engineering characteristic along the proposed route of Jalalpur irrigation project. The proposed JIP (Jalalpur Irrigation Project) is located along the right bank of Jhelum Ri...
Detection and Classification of Rice Diseases: An Automated Approach Using Textural Features
Image processing techniques are widely used for the detection and classification of diseases for various plants. The structure of the plant and appearance of the disease on the plant pose a challenge for image processing...
Ground-Water Quality in Islamkot and Mithi Talukas of District Tharparkar, Sindh, Pakistan Jhaman Das Suthar
Surface water supplies are gradually becoming short in arid and semi-arid regions of the world. Thus, assessment of groundwater quality for crop use appears to be very essential for management and utilization of precious...