Source-linked AI summary
Approximating Edit Distance in Near-Linear Time
Alexandr Andoni, Krzysztof Onak
TL;DR
Edit distance is fundamental in areas including computational biology and text processing, but prior embedding approaches posed dimension and space challenges. This paper gives a low-dimensional ℓ1-embedding approach and an approximation algorithm, with a sub-polynomial approximation in near-linear time.
Problem
Method
The algorithm embeds substrings of a concatenated input into low-dimensional vectors so their ℓ1 distance approximates edit distance.
Source: §3 · p. 6Results
A 2^O(sqrt(log n) log log n)-approximation for binary strings runs in n · 2^O(sqrt(log n) log log n) time.
Source: §1 · p. 2Takeaways & Limitations
The result also yields a sublinear-time algorithm distinguishing edit distance O(n^α) from Ω(n^β) in n^(α+2(1−β)+o(1)) time for α < β ≤ 1.
Source: §1 · p. 2, §4.1 · p. 13Direct use of the prior embedding would yield much higher dimension, and storing all its vectors would take quadratic space.
Source: §3 · p. 6
Abstract
from arXiv · showhide
We show how to compute the edit distance between two strings of length n up to a factor of 2^{\~O(sqrt(log n))} in n^(1+o(1)) time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n^(1/3+o(1)) approximation. Previously, approximation of 2^{\~O(sqrt(log n))} was known only for embedding edit distance into l_1, and it is not known if that embedding can be computed in less than quadratic time.
1 Introduction
The introduction frames fast, provably accurate edit-distance approximation as important for applications including genomic data and text processing. It presents a new approximation guarantee and related sublinear-time and pattern-matching applications, then outlines the techniques and recent work.
1 Introduction
- Edit distance is fundamental in computational biology and text processing, motivating fast algorithms with provable guarantees.The introduction describes it as an elementary measure of genomic-data dissimilarity and asks whether near-linear-time approximation is possible.Source: §1 · p. 1
- For two length-n binary strings, edit distance is approximable within factor 2^O(√log n log log n) in n·2^O(√log n log log n) time, versus the 2006 n^(1/3+o(1)) approximation.Source: §1 · p. 2
- For any α < β ≤1, the sublinear-time algorithm distinguishes distance O(n^α) from Ω(n^β) in O(n^(α+2(1−β)+o(1))) time.Source: §1 · p. 2
- For pattern matching with errors, the algorithm gives a 2^~O(√log n) approximation in O(N log N)·2^~O(√log n) time, versus the cited exact O(Nn/log² n) algorithm [MP80].Source: §1 · p. 2
1.1 Preliminaries and Notation
- Preliminaries define substring and high-probability notation, non-contracting embeddings and obliviousness, and thresholded Earth-Mover distance (TEMD).Source: §1.1 · p. 3
1.2 Techniques
- The technique starts from but builds non-oblivious low-dimensional vectors, embedding window EMD linearly before mapping min-products back into ℓ1 via sparse-graph Bourgain embeddings.Source: §1.2 · p. 4
1.3 Recent Work
- Recent work [AKO10] gives polylogarithmic approximation in n^(1+ε) time, but at comparable approximation does not improve running time and uses disjoint asymmetric-sampling techniques.Source: §1.3 · pp. 4–5
2 Short Overview of the Ostrovsky-Rabani Embedding
The Ostrovsky-Rabani embedding recursively represents strings through ℓ1 vectors for substrings, using a distance built from thresholded Earth-Mover distances. Its recursive guarantee depends on approximating that idealized distance by an ℓ1 embedding at each level.
2 Short Overview of the Ostrovsky-Rabani Embedding
- The embedding recursively maps strings to ℓ1 vectors, with the distance between vectors approximating edit distance.For each block, it embeds substrings recursively and collects their vectors into sets used to define the idealized distance.Source: §2 · p. 5
- At each level, the idealized distance is formed from a sum-product of thresholded Earth-Mover distances over sets of recursively embedded substrings.The construction uses blocks and substring lengths to define these sets and their associated distances.Source: §2 · p. 5
- The recursive guarantee requires approximating the idealized distance d*n; approximating it within a polylogarithmic factor suffices for the recurrence described.The overview states that this approximation can be embedded into ℓ1 at each recursion level.Source: §2 · pp. 5–6
- Ostrovsky and Rabani embed a relaxed version of TEMD into ℓ1 with O(log n) distortion, yielding an O(log n) factor for the idealized distance at each recursion level.Source: §2 · p. 6
3 Proof of the Main Theorem
The proof develops embedding-based techniques for approximating edit distance, including non-oblivious embeddings for substrings and an efficient TEMD approximation. It then builds a near-linear embedding route through tree and graph metrics to low-dimensional ℓ1, completing Theorem 3.1.
3 Proof of the Main Theorem
- Theorem 3.1 supplies an efficiently computable building block for approximating TEMD on the required sets.The vectors for all sets can be computed in ˜O(nα) time.Source: §3 · p. 7
- The construction runs in n · 2^{O(√(log n log log n))} time and estimates edit distance by comparing vectors for the two input strings.It builds substring vectors bottom-up over a carefully chosen set of lengths and uses a polylogarithmic-loss approximation of ideal vectors to keep the dimension manageable.Source: §3 · pp. 7–8
3.1 Proof of Theorem 3.1
- The proof has two stages: it embeds TEMD into a low-dimensional min-product of ℓ1 spaces, then embeds n points into ℓ1 of dimension O(log^2 n), with distortion log^O(1) n, assuming the semi-metric is a log^O(1) n approximation of some metric.Source: §3.1 · p. 8, §3.1.2 · p. 10
3.1.1 Embedding EMD into min-product of ℓ1
- The TEMD embedding has O(log² n) distortion with high probability in a min-product of ℓ1 spaces with O(log n) factors, and takes ˜O(nα) time.The embedding is linear in the sets, allowing consecutive sliding-window sets to be processed incrementally.Source: §3.1 · p. 8, §3.1.1 · p. 9
3.1.2 Embedding of min-product of ℓ1 into low-dimensional ℓ1
- The min-product of ℓ1 points can be embedded into a min-product of tree metrics with O(log n) distortion in ˜O(n · kl) time.The subsequent low-dimensional ℓ1 embedding applies when the min-product semi-metric approximates an actual metric.Source: §3.1.2 · p. 10
- Randomly shifted grids produce tree metrics that preserve nearby pairs with high probability while avoiding excessive contraction of farther pairs after O(log n) edge-weight scaling.For each threshold and min-product coordinate, the construction creates O(log n) trees; pairs farther than the threshold have probability at most n^(-c+1) of being too close in any of O(log^2 n) trees.Source: §3.1.2 · pp. 10–11
- A γ-near metric in a min-product of l tree metrics embeds into a connected weighted graph with O(nl) edges, distortion γ, and O(nl) running time.The construction identifies tree nodes corresponding to the same point and scales graph edge weights by γ to prevent contraction.Source: §3.1.2 · p. 11
- Bourgain’s embedding maps an n-node graph shortest-path metric into ℓ1 with O(log n) distortion in O(m log^3 n) time.The embedding uses O(log^2 n) coordinates and computes distances to sampled subsets using Dijkstra’s algorithm.Source: §3.1.2 · p. 12
3.1.3 Finalization of the proof of Theorem 3.1
- Scaling and rounding the embedded vectors preserves distances within factors kn and 3kn; the proof then obtains O(log n) tree distortion, O(log^3 n) near-metric expansion, and a final O(log^2 n)-distortion ℓ1 embedding.The graph embedding step has expansion at most the near-metric factor γ.Source: §3.1.3 · pp. 12–13
4 Applications
The section applies the paper’s edit-distance algorithm to sublinear-time distance distinction and approximate pattern matching.
4.1 Sublinear-time approximation
- It partitions both strings into equal-length blocks and samples block pairs, using the main algorithm to compare sampled pairs against a distance threshold.When the strings have large edit distance, many block pairs are far apart; when the distance is small, no pair exceeds the total distance.Source: §4.1 · p. 13
- For 0 ≤ α < β ≤ 1, the algorithm distinguishes edit distances O(n^α) and Ω(n^β) in time n^(α+2(1−β)+o(1)).Source: §4.1 · p. 13
4.2 Pattern matching
- For a pattern P, the method approximates its edit distance to every length-n text substring, supporting approximate-occurrence and closest-substring searches.The stated running time is O(N log N) · 2^O(√(log n log log n)), with approximation factor 2^O(√(log n log log n)).Source: §4.2 · pp. 13–14