Parallel Approaches to Edit Distance and Approximate String Matching
Carnegie Mellon University
Carnegie Mellon University, 2014
@article{yang2014parallel,
title={Parallel Approaches to Edit Distance and Approximate String Matching},
author={Yang, Cary and Zhang, Kevin},
year={2014}
}
In this paper, we explore approaches to parallelizing the edit distance problem and the related approximate string matching problem. The edit distance is a measure of the number of individual character insertions, deletions, and substitutions requried to transform one string into another string. In the canonical dynamic programming solution to the edit distance, a chain of dependencies renders parallelization extremely difficult; thus, we investigate several different approaches to resolve this issue.
May 20, 2014 by hgpu
