Pattern matching under DTW distance

DOI10.1007/978-3-031-20643-6_23zbMath1525.68205arXiv2208.14669MaRDI QIDQ6111594

Anne Driemel, Tatiana Starikovskaya, Pierre Peterlongo, Garance Gourdel

Publication date: 4 August 2023

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

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

zbMATH Keywords

pattern matchingapproximation algorithmsdynamic time-warping distancesmall-distance regime

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast string matching with k differences
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• Fast exact dynamic time warping on run-length encoded time series
• Dynamic programming algorithm optimization for spoken word recognition
• Incremental String Comparison
• Dynamic Time Warping and Geometric Edit Distance
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Pattern matching under DTW distance