PaperlayerView exact revision on arXiv

Source-linked AI summary

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

arXiv:1005.4033v1cs.DS

TL;DR

Classical edit distance has resisted efficient polylogarithmic approximation, despite the need for faster computation. The paper studies an asymmetric query model and uses a query-efficient algorithm to obtain a near-linear-time approximation, alongside nearly matching query lower bounds. Its lower bound exposes repetitive-string hardness and separates edit distance from Ulam distance.

  • Problem

    Exact edit distance takes O(n^2) time, while previously known approximation factors for classical edit distance remained super-polylogarithmic.

    Source: §1 · p. 2

  • Method

    The paper studies a model with unrestricted access to y and charged queries to x, using sampling and an edit-distance characterization to build its algorithm.

    Source: §1.1 · p. 3, §1.3 · p. 6

  • Results

    For every fixed ε > 0, a (log n)^O(1/ε) approximation runs in n^(1+ε) time; for polylogarithmic approximation, edit distance has a 2^Ω(log n / log log n) query lower bound.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    The lower bound first exposes hardness from repetitive substrings and gives a rigorous separation between edit distance and Ulam distance.

    Source: §1.1 · pp. 3–4

    The initial shifted-string construction gives only an Ω(log n) query lower bound, so a different construction is needed for a superlogarithmic bound.

    Source: §2.2.1 · p. 12

Abstract

from arXiv · show

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.

1 Introduction

The introduction positions classical edit distance as important but costly to compute, then presents a near-linear-time polylogarithmic approximation and an asymmetric-query study with nearly matching bounds. It also describes algorithmic techniques, connections to other models, and directions for further work.

1 Introduction

  • Exact edit distance takes O(n^2) time, and near-quadratic computation has driven interest in approximation; Ulam distance and some edit-distance variants admit faster results.The classical exact Ulam algorithm runs in O(n log n) time; cited variants admit near-linear-time ˜O(log n) approximations.Source: §1 · p. 2

1.1 Results

  • For every fixed ε > 0, a (log n)^O(1/ε) approximation to edit distance runs in n^(1+ε) time, exponentially improving the previous factor in comparable time.The previous factor was 2˜O(√log n).Source: §1.1 · p. 3

1.2 Connections of Asymmetric Query Model to Other Models

  • The asymmetric query model gives unrestricted access to y and charges queries to x; its upper bound also yields a one-way communication protocol for DTEPβ.The protocol uses O(βn^ε) communication for polylogarithmic approximation, while the symmetric query model is more restrictive than the asymmetric one.Source: §1.1 · p. 3, §1.2 · p. 5

1.1 Results

  • The asymmetric model gives nearly matching query bounds across parameter regimes and separates edit distance from Ulam distance, even for polylogarithmic approximation.For polylogarithmic approximation, edit distance requires 2^Ω(log n / log log n) queries, while Ulam distance admits a constant approximation with O(log n) queries.Source: §1.1 · pp. 3–4

1.3 Techniques

  • The algorithm samples about n^ε positions of x, then computes edit distance in n^(1+ε) time; its query method estimates a characterized distance E.The characterization recursively partitions x into b blocks, uses displacement minima, and has approximation O(b log_b n).Source: §1.3 · p. 6
  • For b = (log n)^(1/ε), tree pruning samples children to estimate E, leaving n^O(ε) queried positions; non-uniform sampling handles β ≫ 1.The characterization avoids the multiplicative factor loss in earlier hierarchical recurrences; for constant b it gives logarithmic approximation, though efficient algorithms for that setting are not known.Source: §1.3 · p. 6
  • The lower bound recursively substitutes strings into shifted random strings, amplifying an Ω(log n) query bound to 2^Ω(log n / log log n) for polylogarithmic approximation.The proof develops a distribution-similarity notion that composes with substitution and uses random shifts to produce similar distributions.Source: Query Complexity Lower Bound · p. 7

1.4 Future Directions

  • Future directions include extending results to the symmetric model, strengthening embedding and communication bounds, tightening query bounds, and using the characterization for faster approximation.The paper also identifies nearest-neighbor search as a possible beneficiary of its techniques.Source: §1.4 · pp. 7–8

2 Outline of Our Results

This section outlines the upper- and lower-bound results for edit distance, covering query-efficient sampling, hard-distribution analysis, and a reduction of large-alphabet lower bounds to binary strings using rigid blocks to recover alignments.

2.1.1 Edit Distance Characterization: the E-distance

  • For b = 2, E-distance approximates edit distance within O(log n); for b = (log n)^O(1/ε), it can be approximated within 1 + ε in n^(1+ε) time.The algorithmic approach characterizes edit distance using E, then estimates E by querying a small number of symbols of x.Source: §2.1 · p. 8, §2.1.1 · p. 9

2.1.2 Sampling Algorithm

  • Non-uniform sampling assigns each node a precision that controls its additive estimation error, enabling tree pruning where uniform sampling can fail when β ≫ b.The precision requirement is additive error l_i/w; the approach uses different sampling rates for different nodes.Source: §2.1.2 · p. 10

2.2.1 The Hard Distributions

  • Randomly shifting random strings produces distributions requiring Ω(log n) queries to distinguish, while querying C log n consecutive symbols can distinguish this construction.Within each distribution, strings are at distance at most n/500; across the two distributions, they are at least n/20 apart.Source: §2.2.1 · p. 12
  • Recursive substitution constructions yield an Ω(log² n) query lower bound, and distinguishing edit distance O(n/polylog n) from Ω(n) requires n^Ω(1/log log n) queries.For two recursion levels, the distributions are close within each class but far across classes; under Ulam distance, O(log n) queries suffice for the corresponding threshold task.Source: §2.2.1 · p. 13

2.2.2 Bounding the Number of Queries

  • Uniform α-similarity forces even adaptive distinguishers with success probability at least 2/3 to make at least 1/(6α) queries, and substitution products compose similarity multiplicatively as αβ.Random cyclic shifts establish uniform similarity, and substitution-product composition yields the two-level Ω(log² n) lower bound.Source: §2.2.2 · pp. 13–14

2.2.3 Preserving Edit Distance

  • Substitution can shrink relative edit distance by an additive term depending polynomially on the maximum relative longest common substring between substituted symbols, requiring at most a polylogarithmic alphabet.The overview analyzes insertion-deletion distance, which is between edit distance and twice edit distance.Source: §2.2.3 · pp. 14–15
  • A lower bound for a large alphabet implies one for the binary alphabet with only a constant-factor loss in edit distance.Map each large-alphabet symbol to a random binary string of length Θ(log |Σ|).Source: §2.2.3 · p. 15
  • Substitution-product strings have rigid blocks, so their alignments largely respect block structure and yield alignments between the original strings.This is the main idea behind the distance-preservation proofs.Source: §2.2.3 · p. 15

3 Fast Algorithms via Asymmetric Query Complexity

This section develops an asymmetric-query approach to approximating edit distance, using a tree-based E-distance characterization and sampling. It establishes the sampling lemmas and proves the algorithm’s approximation, query, and near-linear-time guarantees.

3 Fast Algorithms via Asymmetric Query Complexity

  • DTEPβ admits approximation O(b log_b n) using β·(log n)^O(log_b n) queries into x and n·(log n)^O(log_b n) time.For constant β and integer t ≥ 2, an alternative algorithm achieves O(n^(1/t)) approximation with O(log n)^(t−1) queries in ˜O(n) time.Source: §3 · p. 15

3.1 Edit Distance Characterization: the E-distance

  • A recursively defined, asymmetric tree-based E-distance approximates edit distance within 6b log_b n for strings of length n.The characterization bounds E-distance between 1/2 and 5b log_b n times edit distance.Source: §3.1 · pp. 16–17

3.2 Sampling Algorithm

  • The sampling algorithm estimates E-distance within multiplicative 1 ± o(1) and additive n/β error using β·n^O(ε) samples of x.This suffices to distinguish E-distance at most n/β from at least 4n/β.Source: §3.2 · p. 19

3.2.1 Algorithm Description

  • The algorithm recursively samples nodes in an arity-b tree, assigning precision values that control subsampling, then queries x at sampled leaves and estimates E-distance.The estimation algorithm computes node-to-position estimates from sampled leaves and combines child estimates using a reconstruction procedure.Source: Sampling algorithm · pp. 19–20

3.2.2 Analysis Preliminaries: Approximators and a Concentration Bound

  • The analysis uses (ρ, f)-approximators, whose additive errors add under summation and whose multiplicative and additive errors compose across successive approximations.An (ρ, f)-approximator ˆτ satisfies τ/f − ρ ≤ ˆτ ≤ fτ + ρ.Source: §3.2.2 · pp. 20–21
  • The analysis uses Chernoff and Hoeffding bounds to control sums of independent bounded random variables.The Hoeffding-bound variant is derived from.Source: §3.2.2 · p. 21

3.2.3 Main Analysis Tools: Uniform and Non-uniform Sampling Lemmas

  • The Non-uniform Sampling Lemma reconstructs a sum from per-item approximators, achieving additive error ρ and multiplicative factor f · e^ε with probability at least 1 − δ.Its distribution W has expected weight O(1/ρ · log(1/δ) · log N / ε^3); the complementary uniform sampling lemma uses subsampling in a suitable regime.Source: §3.2.3 · pp. 21–22

3.2.4 Correctness and Sample Bound for the Main Algorithm

  • The estimation algorithm returns a (n/β, 1 + o(1))-approximator to the E-distance with high probability, using (log n)^(t−1) queries when b = n^(1/t) and β = O(1).The sample bound holds with probability at least 2/3; the correctness proof builds an approximation inductively by expanding and subsampling tree levels.Source: §3.2.4 · pp. 23, 25

3.3 Near-Linear Time Algorithm

  • n · (log n)^O(log_b n) time suffices to implement the estimation algorithm.Replacing δ_v′ with v′ increases the output by at most a 1 + o(1) factor; discretizing the sampling distribution incurs only an O(log n) loss in time.Source: §3.3 · pp. 25–26

4 Query Complexity Lower Bound

The section proves the lower bound through tools for indistinguishability and edit-distance behavior, then combines them in its most general theorems.

4 Query Complexity Lower Bound

  • The proof develops indistinguishability and edit-distance analysis tools before combining them in Theorems 4.15 and 4.16.The passage identifies these as the precise and most general forms of the lower bound.Source: §4 · p. 26

4.1 Preliminaries

These preliminaries fix the edit-distance variants and notation used for alignments, projections, substitutions, and shifts.

4.1 Preliminaries

  • The lower-bound section uses insertion-deletion distance ed, which excludes substitutions and lies between ed(x, y) and 2 ed(x, y).The passage assumes an alphabet of size at least two.Source: §4.1 · p. 26
  • An alignment is a monotone matching of equal-character positions, corresponding exactly to a common subsequence.The length of a longest common subsequence is denoted LCS(x, y).Source: §4.1 · p. 26
  • Projection notation x|Q selects coordinates Q from a string, and D|Q denotes the corresponding projection of a string distribution.Source: §4.1 · p. 26
  • A substitution product replaces each symbol of a string by its mapped block and concatenates the blocks; its distributional form uses independent samples conditioned on each symbol.The distributional construction also allows the original string to be sampled from a mother distribution.Source: §4.1 · pp. 26–27
  • S_r(x) denotes a cyclic left shift by r positions, while S_s(x) randomizes the shift offset uniformly over [s].Shifting selected coordinates corresponds to projecting the original string onto shifted coordinates.Source: §4.1 · p. 27

4.2 Tools for Analyzing Indistinguishability

This section develops uniform similarity as a way to turn limited query access into indistinguishability, then shows how random shifts and substitution products support lower-bound constructions.

4.2 Tools for Analyzing Indistinguishability

  • The section introduces distribution-similarity tools, derives their query-complexity consequence, and analyzes random shifts and substitution-product composition.Source: §4.2 · p. 27

4.2.1 Similarity of Distributions

  • Uniformly α-similar distributions on Σ^n have restrictions to every subset Q of [n] that are α|Q|-similar; Lemma 4.4 considers distinguishing them with q adaptive symbol queries.Source: §4.2.1 · p. 27

4.2.2 Random Shifts

  • With probability at least 2/3, random cyclic shifts of independent random strings produce uniformly similar distributions.The result bounds uniform similarity by a factor that decreases with the number of query positions.Source: §4.2.2 · pp. 29–30

4.2.3 Amplification of Uniform Similarity via Substitution Product

  • Substitution products multiply the similarity parameters: uniformly α-similar code distributions and uniformly β-similar inputs yield uniformly αβ-similar outputs.Source: §4.2.3 · p. 30

4.3 Tools for Analyzing Edit Distance

This section develops bounds for edit distance under substitution products, including an additive large-alphabet analysis and a multiplicative analysis useful for alphabet reduction.

4.3 Tools for Analyzing Edit Distance

  • The section supplies tools for tracking edit distance through substitution products, with separate guarantees for large and small alphabets.The small-alphabet result is used in the final reduction to a binary alphabet.Source: §4.3 · p. 32

4.3.1 Distance between random strings

  • The section invokes a known bound on the longest common subsequence of uniformly random strings as an ingredient in its distance analysis.Source: §4.3.1 · p. 33

4.3.2 Distance under substitution product (large alphabet)

  • For large alphabets, the substitution-product bounds are additive and are most effective when the original edit distance is linear and λB is small.λB is the maximum normalized LCS between distinct images of B.Source: §4.3.2 · p. 33

4.3.3 Distance under substitution product (any alphabet)

  • The any-alphabet analysis gives multiplicative bounds that can serve as a final step in reducing the alphabet, including to binary.A random mapping satisfies the stated properties with probability at least 1 − |Σ′|^-Ω(n′) when n′ ≥ 1000 log |Σ|.Source: §4.3.3 · pp. 35–36

4.4 The Lower Bound

The lower-bound construction creates distributions whose strings are far apart in edit distance but difficult to distinguish with limited queries. A more precise result gives an Ω(log^t n) query lower bound for polynomial approximation factors.

4.4.1 The Construction of Hard Distributions

  • The hard distributions are built probabilistically from random base strings and a randomized reduction to the binary alphabet.The construction is probabilistic only in the base-string selection and binary-alphabet mapping steps.Source: §4.4.1 · p. 37

4.4.2 Proof of the Query Complexity Lower Bound

  • The construction yields distributions that are far apart in edit distance, yet distinguishing between them requires many queries.The lower bound also applies after a randomized mapping to binary strings, with the distance gap scaled by a constant.Source: §4.4.2 · pp. 37, 39

4.4.3 A More Precise Lower Bound for Polynomial Approximation Factors

  • The more precise bound is Ω(log^t n) queries, including for constant-size alphabets and, with a constant-scaled gap, binary strings.Source: §4.4.3 · p. 40

Related papers

Loading 1005.4033v1…