论文标题
改进的时间扭曲编辑距离 - 线性内存中的平行动态程序
Improved Time Warp Edit Distance -- A Parallel Dynamic Program in Linear Memory
论文作者
论文摘要
编辑距离是一个经典的动态编程问题家族，其中包括时间扭曲的距离通过度量和时间弹性的概念来完善问题。一种新颖的改进的时间扭曲编辑距离算法，既可以平行，又需要线性存储。该方法使用三个对角线频段的游行来覆盖原始的动态程序空间。对角线更新的每个元素都可以并行计算。核心方法是TWED最长常见子序列数据依赖性的特征，并且适用于具有相似带子问题结构的动态程序。该算法已作为具有Python绑定的CUDA C库实现。挑战性问题的加速是惊人的。
Edit Distance is a classic family of dynamic programming problems, among which Time Warp Edit Distance refines the problem with the notion of a metric and temporal elasticity. A novel Improved Time Warp Edit Distance algorithm that is both massively parallelizable and requiring only linear storage is presented. This method uses the procession of a three diagonal band to cover the original dynamic program space. Every element of the diagonal update can be computed in parallel. The core method is a feature of the TWED Longest Common Subsequence data dependence and is applicable to dynamic programs that share similar band subproblem structure. The algorithm has been implemented as a CUDA C library with Python bindings. Speedups for challenging problems are phenomenal.
