Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation

DOI10.4230/LIPIcs.ICALP.2019.80OpenAlexW2965589715MaRDI QIDQ5091239

William Kuszmaul

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1904.09690

zbMATH Keywords

approximation algorithmdynamic time warpingedit distancetree metrics

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items

Approximating the geometric edit distance, A faster reduction of the dynamic time warping distance to the longest increasing subsequence length, Pattern matching under DTW distance, Fast exact dynamic time warping on run-length encoded time series, Unnamed Item, Tight Hardness Results for Consensus Problems on Circular Strings and Time Series

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Approximability of the discrete Fréchet distance
• Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences
• An Improved Algorithm For Approximate String Matching
• Oblivious string embeddings and edit distance approximations
• Algorithms for approximate string matching
• Dynamic programming algorithm optimization for spoken word recognition
• Incremental String Comparison
• The String-to-String Correction Problem
• Approximating Edit Distance in Near-Linear Time
• Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
• Efficiently Approximating Edit Distance Between Pseudorandom Strings
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics