Polylogarithmic approximation for edit distance and the asymmetric query complexity

DOI10.1007/978-3-642-16367-8_16MaRDI QIDQ4933374zbMATH OpenOpenAlexFDO

Authors Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

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

zbMATH Keywords

edit distancequery complexitysampling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Algorithms on strings (68W32)

Abstract: We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor; specifically, for strings of length n and every fixed epsilon>0, it can compute a (log n)^O(1/epsilon) approximation in n^(1+epsilon) time. This is an exponential improvement over the previously known factor, 2^(O (sqrt(log n))), with a comparable running time (Ostrovsky and Rabani J.ACM 2007; Andoni and Onak STOC 2009). Previously, no efficient polylogarithmic approximation algorithm was known for any computational task involving edit distance (e.g., nearest neighbor search or sketching). This result arises naturally in the study of a new asymmetric query model. In this model, the input consists of two strings x and y, and an algorithm can access y in an unrestricted manner, while being charged for querying every symbol of x. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We then provide a nearly-matching lower bound on the number of queries. Our lower bound is the first to expose hardness of edit distance stemming from the input strings being "repetitive", which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance, which is edit distance on non-repetitive strings, such as permutations.

Recommendations

• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• Near-optimal sublinear time algorithms for Ulam distance
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• A sublinear algorithm for weakly approximating edit distance

Cites work

• A faster algorithm computing string edit distances
• A sublinear algorithm for weakly approximating edit distance
• Algorithms on Strings, Trees and Sequences
• Approximate nearest neighbors and sequence comparison with block operations
• Approximating edit distance in near-linear time
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Estimating the distance to a monotone function
• Fast and compact regular expression matching
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• Improved lower bounds for embeddings into L₁
• Incremental String Comparison
• Introduction to algorithms
• Low distortion embeddings for edit distance
• Lower bounds for edit distance and product metrics via Poincaré-type inequalities
• Near-optimal sublinear time algorithms for Ulam distance
• Nonembeddability theorems via Fourier analysis
• Oblivious string embeddings and edit distance approximations
• Optimal approximations of the frequency moments of data streams
• Space lower bounds for distance approximation in the data stream model
• Spot-checkers
• The computational hardness of estimating edit distance
• The String-to-String Correction Problem

Cited in

(20)

• Detecting life signatures with RNA sequence similarity measures
• Approximating the geometric edit distance
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Asymmetric signature schemes for efficient exact edit similarity query processing
• If the current clique algorithms are optimal, so is Valiant's parser
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Accurate and nearly optimal sublinear approximations to Ulam distance
• 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
• Approximating edit distance in near-linear time
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
• Approximating edit distance in near-linear time
• A simple algorithm for approximating the text-to-pattern Hamming distance
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Near-linear time edit distance for indel channels
• Weighted edit distance computation: strings, trees, and Dyck
• LCS approximation via embedding into locally non-repetitive strings

This page was built for publication: Polylogarithmic approximation for edit distance and the asymmetric query complexity

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