Approximating dynamic time warping distance between run-length encoded strings

DOI10.4230/LIPICS.ESA.2022.90MaRDI QIDQ6969583zbMATH OpenFDO

Authors Zoe Xi, William Kuszmaul

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.90

zbMATH Keywords

approximation algorithmscomputational geometrydynamic time warping distancerun-length encodings

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A faster algorithm computing string edit distances
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Approximate matching of run-length compressed strings
• Approximating dynamic time warping and edit distance for a pair of point sequences
• Approximating dynamic time warping distance between run-length encoded strings
• Approximating edit distance in near-linear time
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Clustering of time series data -- a survey
• Constant factor approximations to edit distance on far input pairs in nearly linear time
• Constant-factor approximation of near-linear edit distance in near-linear time
• Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Edit distance for a run-length-encoded string and an uncompressed string
• Edit distance in near-linear time: it's a constant factor
• Edit distance of run-length encoded strings.
• scientific article; zbMATH DE number 7375961 (Why is no real title available?)
• scientific article; zbMATH DE number 7651119 (Why is no real title available?)
• scientific article; zbMATH DE number 7765364 (Why is no real title available?)
• Incremental String Comparison
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Quadratic conditional lower bounds for string problems and dynamic time warping
• RLE edit distance in near optimal time
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Streaming algorithms for embedding and computing edit distance in the low distance regime
• Tight hardness results for LCS and other sequence similarity measures

Cited in

(2)

• Õptimal dynamic time warping on run-length encoded strings
• Approximating dynamic time warping distance between run-length encoded strings

This page was built for publication: Approximating dynamic time warping distance between run-length encoded strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969583)