Distributed Algorithm for Parallel Edit Distance Computation

Authors

  • Muhammad Umair Sadiq Punjab University College of Information Technology (PUCIT), University of the Punjab, Lahore, Pakistan
  • Muhammad Murtaza Yousaf Punjab University College of Information Technology (PUCIT), University of the Punjab, Lahore, Pakistan

DOI:

https://doi.org/10.31577/cai_2020_4_757

Keywords:

Edit distance, dynamic programming, parallel computing, distributed memory system, MPI, OpenMP, speedup

Abstract

The edit distance is the measure that quantifies the difference between two strings. It is an important concept because it has its usage in many domains such as natural language processing, spell checking, genome matching, and pattern recognition. Edit distance is also known as Levenshtein distance. Sequentially, the edit distance is computed by using dynamic programming based strategy that may not provide results in reasonable time when input strings are large. In this work, a distributed algorithm is presented for parallel edit distance computation. The proposed algorithm is both time and space efficient. It is evaluated on a hybrid setup of distributed and shared memory systems. Results suggest that the proposed algorithm achieves significant performance gain over the existing parallel approach.

Downloads

Download data is not yet available.

Downloads

Published

2021-01-12

How to Cite

Sadiq, M. U., & Yousaf, M. M. (2021). Distributed Algorithm for Parallel Edit Distance Computation. Computing and Informatics, 39(4), 757–779. https://doi.org/10.31577/cai_2020_4_757

Issue

Section

Special Section Articles