Low distortion embeddings for edit distance

DOI10.1145/1060590.1060623zbMath1192.68835OpenAlexW2148029272MaRDI QIDQ5901101

Yuval Rabani, Rafail Ostrovsky

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060623

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Information storage and retrieval of data (68P20)

Related Items

A relation between edit distance for ordered trees and edit distance for Euler strings, Approximating tree edit distance through string edit distance, Nonembeddability theorems via Fourier analysis, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, LCS approximation via embedding into locally non-repetitive strings, LCS Approximation via Embedding into Local Non-repetitive Strings