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
Keywords
Related Articles
- EP ID EP253069
- DOI 10.22581/muet1982.1801.20
- Views 146
- Downloads 0
Optimization of Sono-Electrocoagulation Process for the Removal of Dye Using Central Composite Design
Sono-electrocaogulation process was successfully applied for the removal of RR120 (Reactive Red 120) in the presence of activated carbon. For this purpose, the process variables were optimized using CCD (Central Composit...
Effects of Cu and Zn Coated Urea on Eh, pH and Solubility of Cu and Zn in Rice Soils
The concentration of Cu (Copper) and Zn (Zinc) decreases upon flooded conditions of rice soil. To assess the effects of flooding and application of Cu and Zn coated urea on changes in Eh, pH and solubility of Cu and Zn,...
Analysis of Caustic Soda of Different Manufacturers in Pakistan for Mercerization of Cotton Textiles
Pakistan has sufficient production capacity of caustic soda to cater the needs of the local industry. Presently, Pakistan has four major plants with production capacity around 435,000 mega ton per year of caustic soda of...
Effectiveness and Future Prospects of Telemedicine/Remote Health Care Management Applications in Pakistan
Medical/Health care system is spraining in Pakistan because of innovative technology, activities and services as per their financial cost (position) which is increasing day by day. This research is intended for the asses...
Translating Activity Diagram from Duration Calculus for Modeling of Real-Time Systems and its Formal Verification using UPPAAL and DiVinE
The RTS (Real-Time Systems) are widely used in industry, home appliances, life saving systems, aircrafts, and automatic weapons. These systems need more accuracy, safety, and reliability. An accurate graphical modeling a...