Oblivious string embeddings and edit distance approximations

DOI10.1145/1109557.1109644MaRDI QIDQ3581511zbMATH OpenOpenAlexFDO

Authors Tuğkan Batu, Funda Ergün, Cenk Sahinalp

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Cited in

(25)

• Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings
• Binary vectors for fast distance and similarity estimation
• Approximating tree edit distance through string edit distance
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• LCS Approximation via Embedding into Local Non-repetitive Strings
• Sketching and embedding are equivalent for norms
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• Towards hardness of approximation for polynomial time problems
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• scientific article; zbMATH DE number 7375961 (Why is no real title available?)
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• Near-linear time edit distance for indel channels
• Locally consistent decomposition of strings with applications to edit distance sketching
• Computing all-vs-all MEMs in grammar-compressed text
• Approximation algorithms for LCS and LIS with truly improved running times
• LCS approximation via embedding into locally non-repetitive strings
• Improved approximation for longest common subsequence over small alphabets
• A linear-time \(n^{0.4}\)-approximation for longest common subsequence
• Streaming and small space approximation algorithms for edit distance and longest common subsequence
• Many flavors of edit distance
• Edit distance in near-linear time: it's a constant factor

This page was built for publication: Oblivious string embeddings and edit distance approximations

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