Improved Time Warp Edit Distance -- A Parallel Dynamic Program in Linear Memory
This provides a highly efficient solution for sequence alignment tasks in fields like bioinformatics or speech recognition, though it appears incremental as it builds on existing TWED methods.
The authors tackled the computational challenge of Time Warp Edit Distance by developing a massively parallelizable algorithm that requires only linear storage, achieving phenomenal speedups for challenging problems.
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.