Parallel Approaches to Edit Distance and Approximate String Matching

Cary Yang, Kevin Zhang
Carnegie Mellon University
Carnegie Mellon University, 2014


   title={Parallel Approaches to Edit Distance and Approximate String Matching},

   author={Yang, Cary and Zhang, Kevin},



Download Download (PDF)   View View   Source Source   



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.
Rating: 0.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: