12093

Parallel Approaches to Edit Distance and Approximate String Matching

Cary Yang, Kevin Zhang
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}

}

Download Download (PDF)   View View   Source Source   

936

views

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. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: