betaFeedback

WorksComputer Science

Small-Space Streaming Hamming Approximation

Abstract

For a preprocessed pattern of length mm and a streaming text, we give two algorithms that estimate the Hamming distance at every alignment to relative error ε\varepsilon. They use ε−8/5m2/5+o(1)\varepsilon^{-8/5}m^{2/5+o(1)} and ε−1m1/2+o(1)\varepsilon^{-1} m^{1/2+o(1)} words of space, respectively, including all retained pattern information. Each estimate is reported as soon as its window ends, and all estimates are simultaneously correct with high probability. The prior space bounds are O~(ε−3/2m)\widetilde{O}(\varepsilon^{-3/2}\sqrt{m}), due to Chan et al. [CGK+20], and O~((m/ε)2/3)\widetilde{O}((m/\varepsilon)^{2/3}), a consequence of their results and those of Clifford, Kociumaka, and Porat [CKP18]. For ε=Θ(m−a)\varepsilon=Θ(m^{-a}), the better of our two bounds improves on both prior space exponents for every fixed 0<a<1/20<a<1/2. A Fourier matcher uses O~(ε−2(m/K)2)\widetilde{O}(\varepsilon^{-2}(m/K)^2) words to estimate each distance dd within ε(d+K)\varepsilon(d+K), giving relative error at most 2ε2\varepsilon for d≥Kd\ge K. A threshold matcher based on random-prime residue refinements and the multi-stream dictionary matching algorithm of Golan, Kopelowitz, and Porat [GKP18] gives our second space bound directly. Combining it with the Fourier matcher gives the first. Both space bounds extend to L1L_1 matching over polynomially bounded integer symbols.

Introduction and results

Given a pattern P∈ΣmP \in\Sigma^m and a text T∈ΣnT \in\Sigma^n, the text-to-pattern Hamming distances are

ds=Ham⁡(P,T[s:s+m])=∣{j∈[0,m):P[j]≠T[s+j]}∣,0≤s≤n−m.d_s = \operatorname{Ham}(P,T[s:s+m]) = \lvert\{j \in[0,m): P[j] \ne T[s+j]\}\rvert,\qquad0 \le s \le n-m.

Indices are zero-based, and T[a:b]=T[a]⋯T[b−1]T[a:b]=T[a]\cdots T[b-1] denotes a half-open substring. Intervals used as index sets contain only integers. In the streaming setting, the answer for ss must be reported when T[s+m−1]T[s+m-1] arrives. A relative-ε\varepsilon estimate d^s\widehat{d}_s satisfies ∣d^s−ds∣≤εds\lvert\widehat{d}_s-d_s\rvert\le\varepsilon d_s; in particular, zero distances must be reported exactly.

Model. The pattern may be preprocessed in polynomial time and workspace before the text starts. During text processing, every retained representation of the pattern counts toward space, and the original pattern is no longer available. The text arrives once and is fixed independently of the algorithm’s randomness. We assume m≥2m\ge2, n≥mn\ge m, and that nn and ∣Σ∣\lvert\Sigma\rvert are polynomial in mm, with Σ={0,…,∣Σ∣−1}\Sigma=\{0,\ldots,\lvert\Sigma\rvert-1\}. We use O(log⁡(mn))O(\log(mn))-bit words. All answers must be correct simultaneously with probability at least 1−n−c1-n^{-c} for any fixed c>0c>0; this is what we mean by with high probability. Space and worst-case arrival time refer to the text-streaming phase. We allow m−C≤ε≤1/2m^{-C}\le\varepsilon\le1/2 for any fixed C>0C>0. The notation O~\widetilde{O} hides polylogarithmic factors in mm, nn, and 1/ε1/\varepsilon.

Our first ingredient estimates large distances using Fourier samples.

Theorem 1.1. For every integer 1≤K≤m1\le K\le m, the above model admits a streaming estimator using O~(ε−2(m/K)2)\widetilde{O}(\varepsilon^{-2}(m/K)^2) words and O~(ε−1+ε−3m/K2)\widetilde{O}(\varepsilon^{-1}+\varepsilon^{-3}m/K^2) worst-case time per arrival. Its estimates satisfy ∣Es−ds∣≤ε(ds+K)\lvert E_s-d_s\rvert\le\varepsilon(d_s+K) simultaneously at all alignments with high probability.

For ds≥Kd_s \ge K, this gives relative error at most 2ϵ2\epsilon. Our second ingredient uses a shared representation of pattern residues and text residue streams to estimate distances up to a chosen threshold.

Theorem 1.2. For every integer 1≤H≤m1 \le H \le m, there is a streaming Hamming matcher using ϵ−1min⁡{m,H/ϵ} mo(1)\epsilon^{-1}\sqrt{\min\{m,H/\epsilon\}}\,m^{o(1)} words and ϵ−2mo(1)\epsilon^{-2}m^{o(1)} worst-case time per arrival. With high probability, it gives relative-ϵ\epsilon estimates simultaneously at all alignments with ds≤Hd_s \le H. In particular, H=mH=m gives relative-ϵ\epsilon estimates at all alignments using ϵ−1m1/2+o(1)\epsilon^{-1}m^{1/2+o(1)} words.

Combining this threshold matcher with the Fourier matcher gives a second space bound for all alignments.

Theorem 1.3. Relative-ϵ\epsilon Hamming matching in our model admits space ϵ−8/5m2/5+o(1)\epsilon^{-8/5}m^{2/5+o(1)} and worst-case time ϵ−2mo(1)\epsilon^{-2}m^{o(1)} per arriving text symbol.

Choosing between the two relative-approximation algorithms and explicit storage of the pattern and current window gives space

O~(min⁡{ϵ−8/5m2/5+o(1), ϵ−1m1/2+o(1), m}).(1)\widetilde{O}\left(\min\left\{\epsilon^{-8/5}m^{2/5+o(1)},\ \epsilon^{-1}m^{1/2+o(1)},\ m\right\}\right). \tag*{(1)}

The o(1)o(1) term depends only on mm and tends to zero as m→∞m \to\infty. Balancing the Fourier matcher with the small-distance matcher of Chan et al. [2 Theorem B.5] gives O~(m2/5ϵ−2)\widetilde{O}(m^{2/5}\epsilon^{-2}) space, as shown in § 4.

Prior bounds. Starikovskaya, Svagerka, and Uznański [SSU20] give an algorithm using O~(ϵ−2m)\widetilde{O}(\epsilon^{-2}\sqrt{m}) space and O~(ϵ−2)\widetilde{O}(\epsilon^{-2}) arrival time in the stronger model where the pattern also arrives in one pass. Chan, Golan, Kociumaka, Kopelowitz, and Porat [2] use O~(ϵ−3/2m)\widetilde{O}(\epsilon^{-3/2}\sqrt{m}) space and O~(ϵ−3)\widetilde{O}(\epsilon^{-3}) arrival time with pattern preprocessing. An unpublished consequence of prior work gives O~((m/ϵ)2/3)\widetilde{O}((m/\epsilon)^{2/3}) space.1

Our Fourier matcher recovers the same bound by balancing its O~(ϵ−2(m/K)2)\widetilde{O}(\epsilon^{-2}(m/K)^2) space with the exact matcher’s O~(K)\widetilde{O}(K) at K=⌈(m/ϵ)2/3⌉K=\lceil(m/\epsilon)^{2/3}\rceil. When K<m/4K<m/4, use the exact answer when available and Theorem 1.1 with parameter ϵ/2\epsilon/2 otherwise, since then ds>Kd_s>K. For K≥m/4K\ge m/4, explicit storage suffices.

Figure 1 compares (1) with the minimum of these prior bounds and linear storage. For ϵ=Θ(m−a)\epsilon=\Theta(m^{-a}), our leading space exponent is smaller for every fixed 0<a<1/20<a<1/2.

Plot of space exponent $s(a)$ against accuracy exponent $a$

Figure 1. Space ms(a)+o(1)m^{s(a)+o(1)} for ε=Θ(m−a)\varepsilon=\Theta(m^{-a}). The dashed curve follows the published bound of Chan et al. up to a=1/5a=1/5 and the unpublished bound in footnote 1 thereafter. The solid curve gives (1), switching at a=1/6a=1/6.

For Theorem 1.1, we first analyze a simpler implementation. At an integer cutoff 1≤K≤m1\le K\le m, it uses O~(ϵ−2(m/K)2)\widetilde{O}(\epsilon^{-2}(m/K)^2) space and O~(ϵ−2m/K)\widetilde{O}(\epsilon^{-2}m/K) arrival time, with mixed relative and additive error O(ϵ(ds+K))O(\epsilon(d_s+K)). It stores Fourier sums for text blocks of length KK; zero padding makes the extra characters outside the window contribute only to the variance.

The residue threshold matcher of Theorem 1.2 multiplies the modulus by a random prime at each step and samples the increases in the number of occupied mismatch residues. Pair collisions control both the sampling variance and the deficit when refinement stops early. Exact dictionary matching evaluates the sampled increases. One affine-grid sampler, with a common sample budget across levels, lists the currently aligned pairs in bounded time.

Fourier-energy sampling has also been used in streaming sketches for periodicity [4 Section 3.3]. Here the centered moment bound and the causal block representation provide the needed text-to-pattern estimator.

Section 2 proves the Fourier matcher with the same space and a simpler, slower implementation. Section 3 proves Theorem 1.2. Section 4 combines the two matchers to prove Theorem 1.3. Appendix § 6 proves the static sampling tool and the faster Fourier implementation of Theorem 1.1. Appendices § 7 and § 8 give the Fourier precision argument and the L1L_1 reduction.

The Fourier matcher

For a vector x∈RNx \in\mathbb{R}^{N}, write ωN=exp⁡(2πi/N)\omega_N=\exp(2\pi i/N) and x^k=∑j=0N−1xjωN−kj\widehat{x}_k=\sum_{j=0}^{N-1}x_j\omega_N^{-kj} for its unnormalized Fourier transform. We estimate m−⟨x,w⟩m-\langle x,w\rangle by sampling a frequency. Frequencies that carry more of the pattern energy must be sampled with sufficiently high probability.

Lemma 2.1. Let x,w∈RNx,w\in\mathbb{R}^{N} with ∥x∥22=m\lVert x\rVert_2^2=m, and put a=x^a=\widehat{x}, b=w^b=\widehat{w}. Suppose pp is a distribution with pk>0p_k>0 and ∣ak∣2/(Npk)≤4m\lvert a_k\rvert^2/(Np_k)\le4m for every kk. Draw kk from pp and put

Y=Re⁡(ak(ak−bk))Npk.Y=\frac{\operatorname{Re}\left(a_k(a_k-b_k)\right)}{Np_k}.

Then EY=m−⟨x,w⟩\mathbb{E}Y=m-\langle x,w\rangle and EY2≤4m∥x−w∥22\mathbb{E}Y^2\le4m\lVert x-w\rVert_2^2.

Proof. In the mean, pkp_k cancels the denominator, leaving N−1Re⁡∑kak(ak−bk)=m−⟨x,w⟩N^{-1}\operatorname{Re}\sum_k a_k(a_k-b_k)=m-\langle x,w\rangle by the Parseval identity. For the second moment,

EY2≤1N∑k∣ak∣2Npk∣ak−bk∣2≤4mN∑k∣ak−bk∣2=4m∥x−w∥22.\mathbb{E}Y^2\le\frac{1}{N}\sum_k\frac{\lvert a_k\rvert^2}{Np_k}\lvert a_k-b_k\rvert^2\le\frac{4m}{N}\sum_k\lvert a_k-b_k\rvert^2=4m\lVert x-w\rVert_2^2.

Use a map h:Σ→[0,G)h:\Sigma\to[0,G) and represent each symbol aa by the standard basis vector f(a)=eh(a)∈RGf(a)=e_{h(a)}\in\mathbb{R}^{G}. Extend ff to strings by concatenation, denoted by ∘\circ, and write 0b0^b for bb numerical zeros. Let WW be the current window, let VV be the ℓ≤m\ell\le m characters retained immediately before it, and suppose the rr most recent characters of WW are omitted. At length N=2mGN = 2mG, put

x=f(P)∘0mG,w=f(W[0:m−r])∘0rG∘0(m−ℓ)G∘f(V).x = f(P) \circ0^{mG}, \qquad w = f(W[0:m-r]) \circ0^{rG} \circ0^{(m-\ell)G} \circ f(V).

Let DD count mismatches under hh in the retained prefix. A matching pair contributes one to the inner product, a mismatching pair contributes two to the squared difference, and each unpaired symbol contributes one to the squared difference. Thus ⟨x,w⟩=m−r−D\langle x,w\rangle= m-r-D and ∥x−w∥22=2D+ℓ+r\lVert x-w\rVert_2^2 = 2D+\ell+r. Lemma 2.1 gives

E(Y−r)=D,Var⁡(Y−r)≤4m(2D+ℓ+r).(2)\mathbb{E}(Y-r)=D,\qquad\operatorname{Var}(Y-r)\leq4m(2D+\ell+r). \tag*{(2)}

Appendix § 7 constructs an exactly sampleable dyadic distribution pp with the required bound from the pattern alone.

Proposition 2.2. For every integer 1≤K≤m1\leq K\leq m and accuracy ε\varepsilon in the model of § 1, there is a streaming estimator using O~(ε−2(m/K)2)\widetilde{O}(\varepsilon^{-2}(m/K)^2) words and O~(ε−2m/K)\widetilde{O}(\varepsilon^{-2}m/K) worst-case time per arrival that reports estimates EsE_s satisfying

∣Es−ds∣≤ε(ds+K)(3)\lvert E_s-d_s\rvert\leq\varepsilon(d_s+K) \tag*{(3)}

simultaneously for all alignments ss, with high probability.

Proof. Take G=∣Σ∣G=\lvert\Sigma\rvert and h(a)=ah(a)=a, so the one-hot encoding preserves every mismatch. Partition the text into blocks of length KK. When t=s+m−1t=s+m-1 arrives, the blocks meeting the window also cover the preceding string V=T[s0:s]V=T[s_0:s], where s0=K⌊s/K⌋s_0=K\lfloor s/K\rfloor. Thus ℓ=s−s0<K\ell=s-s_0<K, r=0r=0, and D=dsD=d_s. By (2), the mean of L=⌈48m/(ε2K)⌉L=\lceil48m/(\varepsilon^2K)\rceil independent samples is unbiased and has variance

Var⁡YL≤ε212K(2ds+K)≤ε212(ds+K)2.\frac{\operatorname{Var}Y}{L}\leq\frac{\varepsilon^2}{12}K(2d_s+K)\leq\frac{\varepsilon^2}{12}(d_s+K)^2.

Chebyshev’s inequality bounds the error by ε(ds+K)/2\varepsilon(d_s+K)/2 with failure probability at most 1/31/3. Take the median of O(log⁡n)O(\log n) independent means and union bound over alignments. Numerical error contributes at most εK/2\varepsilon K/2 by Appendix § 7, giving (3).

During preprocessing, retain for each sampled frequency kk the two coefficients ∣ak∣2/(Npk)\lvert a_k\rvert^2/(Np_k) and ak/(Npk)a_k/(Np_k) needed for YY. Each symbol has just one nonzero coordinate. Consequently, even over the full alphabet, the contribution of an arriving symbol to the conjugated text transform at kk is a single phase. For each live block BB keep

Qk(B,t)=∑u∈B:u≤tωNk(Gu+T[u]).(4)Q_k(B,t)=\sum_{\substack{u\in B:u\leq t}}\omega_N^{k(Gu+T[u])}. \tag*{(4)}

Maintain the sum over live blocks, starting with an empty queue. Update the current block and the total on arrival. When s0s_0 advances, subtract and discard the oldest block. Multiplying the total by ωN−Gks\omega_N^{-Gks} gives w^bk\widehat{w}_{bk}, since a retained symbol at uu occupies coordinate (G(u−s)+T[u]) mod N(G(u-s)+T[u])\bmod N in ww. There are O(m/K)O(m/K) live blocks per frequency and O~(ε−2m/K)\widetilde{O}(\varepsilon^{-2}m/K) sampled frequencies. Scanning these frequencies per arrival gives the stated time and space. Only pattern preprocessing uses the full transform of length 2m∣Σ∣2m\lvert\Sigma\rvert.

The pattern-dependent Fourier samples use offline preprocessing. Obtaining the same matcher with one-pass pattern preprocessing remains open in this approach.

A residue threshold matcher

To prove Theorem 1.2, we use the following sampling lemma from Appendix § 6.§ 3. Its resource bounds hold for every seed.

Lemma 3.1. Let QQ be prime and let M,tM,t be integers with 1≤M≤Q21 \le M \le Q^2 and 1≤t≤Q1 \le t \le Q. There are random sets A,B⊆[0,M)A,B \subseteq[0,M), each of size at most QtQt, represented in O(Qt)O(Qt) words, with the following properties. For each integer shift ss, the representation enumerates C(s)={z∈A:(s+z) mod M∈B}C(s)=\{z \in A:(s+z)\bmod M \in B\} in O(t2)O(t^2) time. For fixed nonnegative weights wzw_z, put q=(t/Q)2q=(t/Q)^2 and Y=q−1∑z∈C(s)wzY=q^{-1}\sum_{z\in C(s)}w_z. Then

EY=∑zwz,Var⁡Y≤83(q−1−1)∑zwz2.\mathbb{E}Y=\sum_z w_z,\qquad\operatorname{Var}Y\le\frac{8}{3}(q^{-1}-1)\sum_z w_z^2.

Proof of Theorem 1.2. We handle bounded mm by explicit storage. For sufficiently large mm, put

R=2⌈log⁡2mlog⁡2log⁡2m⌉,h=⌈log⁡Rm⌉.R=2\left\lceil\sqrt{\log_2 m\log_2\log_2 m}\right\rceil,\qquad h=\left\lceil\log_R m\right\rceil.

Let P\mathcal{P} be the primes in [R,2R)[R,2R) and put γ=h/∣P∣\gamma=h/|\mathcal{P}|. The standard prime-counting bound gives 1/R≤γ=O(log⁡m/R)<11/R\le\gamma=O(\log m/R)<1. Choose independent uniform p1,…,ph∈Pp_1,\ldots,p_h\in\mathcal{P} and set M0=1M_0=1 and Mi=p1⋯piM_i=p_1\cdots p_i. Thus Mh≥mM_h\ge m. For every fixed integer 0<x<m0<x<m,

Pr⁡[Mi∣x]≤γi.(5)\Pr[M_i\mid x]\le\gamma^i. \tag*{(5)}

Indeed, conditional on Mi−1∣xM_{i-1}\mid x, the remaining quotient x/Mi−1<mx/M_{i-1}<m has at most hh prime divisors in P\mathcal{P}, since each is at least RR and Rh≥mR^h\ge m. The next independent prime divides it with probability at most γ\gamma. This also allows repeated primes.

Choose the depth

ℓ=min⁡{h,⌈log⁡1/γ(6H/ε)⌉}.\ell=\min\left\{h,\left\lceil\log_{1/\gamma}(6H/\varepsilon)\right\rceil\right\}.

It depends only on m,H,εm,H,\varepsilon. Fix an alignment ss, its mismatch set E⊆[0,m)E\subseteq[0,m), and d=∣E∣≤Hd=|E|\le H. Let Hi=∣E mod Mi∣H_i=|E\bmod M_i|. For i<ℓi<\ell and b∈[0,Mi)b\in[0,M_i), let gi,bg_{i,b} be one less than the number of occupied residues modulo Mi+1M_{i+1} inside residue bb modulo MiM_i, or zero if it is empty. Then

Hℓ=H1+∑i=1ℓ−1∑bgi,b,(6)H_\ell=H_1+\sum_{i=1}^{\ell-1}\sum_b g_{i,b}, \tag*{(6)}

since ∑bgi,b=Hi+1−Hi\sum_b g_{i,b}=H_{i+1}-H_i. Each occupied child contains a mismatch, so gi,b2g_{i,b}^2 is at most the number of ordered pairs of distinct mismatches in the parent. Similarly, d−Hℓd-H_\ell is at most the number of unordered pairs colliding modulo MℓM_\ell. By (5),

E∑bgi,b2≤γid(d−1),E[d−Hℓ]≤12γℓd(d−1).\mathbb{E}\sum_b g_{i,b}^2\le\gamma^i d(d-1),\qquad\mathbb{E}[d-H_\ell]\le\frac{1}{2}\gamma^\ell d(d-1).

If ℓ<h\ell<h, the second bound is at most εd/12\varepsilon d/12. If ℓ=h\ell=h, the deficit is zero because Mh≥mM_h\ge m.

The estimator. For 1≤i<h1\le i<h, put Ui=(2R)i≥MiU_i=(2R)^i\ge M_i and fix a prime QiQ_i with Qi2≥UiQ_i^2\ge U_i and Qi2=O(Ui)Q_i^2=O(U_i), using Bertrand’s postulate. We use the common sample budget

S=1+83∑i=1h−1Qi2γi,t∗=⌈4Sε⌉.S=1+\frac{8}{3}\sum_{i=1}^{h-1}Q_i^2\gamma^i,\qquad t_*=\left\lceil\frac{4\sqrt{S}}{\varepsilon}\right\rceil.

Set ti=min⁡{Qi,t∗}t_i=\min\{Q_i,t_*\} and qi=(ti/Qi)2q_i=(t_i/Q_i)^2. Independently at each level i<ℓi<\ell, draw Ai,BiA_i,B_i from Lemma 3.1 with parameters Mi,Qi,tiM_i,Q_i,t_i. Set

Z=H1+∑i=1ℓ−1qi−1∑b∈Ai: (s+b) mod Mi∈Bigi,b.Z=H_1+\sum_{i=1}^{\ell-1}q_i^{-1}\sum_{b\in A_i:\ (s+b)\bmod M_i\in B_i}g_{i,b}.

Conditional on the moduli, its mean is HℓH_\ell. A fully sampled level has qi=1q_i=1; otherwise qi−1=Qi2/t∗2q_i^{-1}=Q_i^2/t_*^2. The sampling lemma and independence between levels therefore give

E[(Z−Hℓ)2]≤83d(d−1)∑i<ℓ(qi−1−1)γi≤Sd(d−1)t∗2≤ε2d(d−1)16.(7)\mathbb{E}[(Z-H_\ell)^2]\leq\frac{8}{3}d(d-1)\sum_{i<\ell}(q_i^{-1}-1)\gamma^i \leq\frac{Sd(d-1)}{t_*^2}\leq\frac{\varepsilon^2d(d-1)}{16}. \tag*{(7)}

Consequently, Cauchy–Schwarz and the deficit bound give

E∣Z−d∣≤E[(Z−Hℓ)2]+E[d−Hℓ]≤εd4+εd12=εd3.(8)\mathbb{E}|Z-d|\leq\sqrt{\mathbb{E}[(Z-H_\ell)^2]}+\mathbb{E}[d-H_\ell]\leq\frac{\varepsilon d}{4}+\frac{\varepsilon d}{12}=\frac{\varepsilon d}{3}. \tag*{(8)}

Markov’s inequality gives relative-ε\varepsilon accuracy with probability at least 2/32/3 when d>0d>0. At d=0d=0 or d=1d=1, the ideal answer is exact.

Streaming implementation. Use the equal-length multi-stream dictionary matcher of Golan, Kopelowitz, and Porat [5 Theorem 1]. For DD patterns and vv streams, it uses O~(D+v)\widetilde{O}(D+v) words, including the shared dictionary, and polylogarithmic worst-case time per stream update. It reports the matching pattern identifier at the current suffix, with high probability; duplicate patterns share an identifier.

At level ii, for every b∈Aib\in A_i put all its nonempty fine pattern residues into the dictionary: for a=b+Mija=b+M_{i}j, 0≤j<pi+10\leq j<p_{i+1}, the string is

P[a]∘P[a+Mi+1]∘P[a+2Mi+1]∘⋯ ,P[a]\circ P[a+M_{i+1}]\circ P[a+2M_{i+1}]\circ\cdots,

stopping before position mm. Their lengths are ⌊m/Mi+1⌋\lfloor m/M_{i+1}\rfloor or ⌈m/Mi+1⌉\lceil m/M_{i+1}\rceil, so two equal-length dictionaries suffice. For each v∈Biv\in B_i, maintain its pi+1p_{i+1} fine text residue streams, with state for both dictionary lengths. An arrival at position tt updates stream t mod Mi+1t\bmod M_{i+1} if t mod Mi∈Bit\bmod M_i\in B_i. Cache each stream’s latest matching identifier for each length.

At alignment ss, enumerate the selected parent pairs using Lemma 3.1. For each reported parent bb, compare every nonempty fine pattern residue a=b+Mija=b+M_i j against the current suffix of stream (s+a) mod Mi+1(s+a)\bmod M_{i+1}, using its length. This suffix consists exactly of the corresponding characters in T[s:s+m]T[s:s+m]. The number of failed equalities is the number of occupied children, and hence determines gi,bg_{i,b}. Maintain H1H_1 in the same way, using all M1M_1 pattern and text residues. All streams start at time zero, so every answer is immediate. Sorted residue lists support all lookups in logarithmic time.

Resources and amplification. Each level retains at most QitiQ_it_i pattern parents and as many text parents, each with fewer than 2R2R children. Thus space is O~(R+Rt∗∑i<ℓQi)\widetilde{O}(R+Rt_*\sum_{i<\ell}Q_i). At most two dictionary states are updated per level per arrival. The sampling lemma enumerates all active parents in O(ti)O(t_i) time; their child queries and the root scan give worst-case arrival time O~(R+Rht∗2)\widetilde{O}(R+Rht_*^2). Since Rγ=O(log⁡m)R\gamma=O(\log m) and h=O(log⁡m/log⁡log⁡m)h=O(\sqrt{\log m/\log\log m}),

S=O(1+∑i<h(2Rγi))=exp⁡(O(hlog⁡log⁡m)).S=O\left(1+\sum_{i<h}(2R\gamma^i)\right)=\exp(O(h\log\log m)).

Thus t∗=ε−1exp⁡(O(hlog⁡log⁡m))t_\ast= \varepsilon^{-1}\exp(O(h\log\log m)). For the space bound,

∑i<ℓQi=O(h(2R)(ℓ−1)/2)≤γ−(ℓ−1)/2exp⁡(O(hlog⁡log⁡m)),\sum_{i<\ell} Q_i = O\left(h(2R)^{(\ell-1)/2}\right) \le\gamma^{-(\ell-1)/2}\exp(O(h\log\log m)),

using 2Rγ=O(log⁡m)2R\gamma= O(\log m). Substitution gives arrival time ε−2mo(1)\varepsilon^{-2}m^{o(1)} and space

O~(R+Rt∗∑i<ℓQi)≤ε−1γ−(ℓ−1)/2mo(1).(9)\widetilde{O}\left(R+Rt_\ast\sum_{i<\ell}Q_i\right)\le\varepsilon^{-1}\gamma^{-(\ell-1)/2}m^{o(1)}. \tag*{(9)}

Both subpolynomial factors are at most exp⁡(O(log⁡mlog⁡log⁡m))\exp(O(\sqrt{\log m\log\log m})), since log⁡R+hlog⁡log⁡m=O(log⁡mlog⁡log⁡m)\log R+h\log\log m=O(\sqrt{\log m\log\log m}). Finally, γ≥1/R\gamma\ge1/R and Rh−1<mR^{h-1}<m give the first bound below; minimality of ℓ\ell gives the second, including ℓ=1\ell=1 and ℓ=h\ell=h:

γ−(ℓ−1)/2<m,γ−(ℓ−1)/2<6H/ε.\gamma^{-(\ell-1)/2}<\sqrt{m},\qquad\gamma^{-(\ell-1)/2}<\sqrt{6H/\varepsilon}.

This gives the stated space bound. When H=mH=m, every dsd_s is at most HH and the bound becomes ε−1m1/2+o(1)\varepsilon^{-1}m^{1/2+o(1)}.

Every weight is either one or Qi2/t∗2Q_i^2/t_\ast^2, so t∗2t_\ast^2 is a common integer denominator. Since (2R)h=m1+o(1)(2R)^h=m^{1+o(1)} and t∗=ε−1mo(1)t_\ast=\varepsilon^{-1}m^{o(1)}, all scaled weights and accumulated answers are polynomially bounded integers and fit logarithmic words. Preprocessing enumerates the candidate primes in polynomial time. All uniform finite choices, including invertible matrices, can use rejection sampling with constant acceptance probability. Capping each draw at O(log⁡n)O(\log n) trials adds an inverse-polynomial failure probability. Every retained representation is charged, and the original pattern is discarded before text streaming.

Take the median of O(log⁡n)O(\log n) independent complete copies, including independent primes and samples, and union bound over alignments. The repetitions preserve both resource bounds. The moment calculation assumes exact dictionary answers. Give dictionary failures a separate inverse-polynomial budget, with seeds independent of the hierarchy and sampling. On simultaneous dictionary success the implementation agrees with the ideal process; its moments are not conditioned on this event.

Combining the residue and Fourier matchers

We prove Theorem 1.3 by combining the residue matcher at a smaller threshold with Fourier estimates for large distances.

Proof of Theorem 1.3. Fix 1≤K≤m1\le K\le m. Run the Fourier matcher of Theorem 1.1 at accuracy ε/3\varepsilon/3 and the residue matcher of Theorem 1.2 at threshold H=min⁡{m,2K}H=\min\{m,2K\}. Output the Fourier estimate EsE_s if Es≥KE_s\ge K and the threshold answer otherwise. On simultaneous success, the Fourier guarantee gives

Es≥K ⟹ ds≥K/2,Es<K ⟹ ds<2K.E_s\ge K\ \Longrightarrow\ d_s\ge K/2,\qquad E_s<K\ \Longrightarrow\ d_s<2K.

Indeed, ds<K/2d_s<K/2 implies Es<K/2+εK/2<KE_s<K/2+\varepsilon K/2<K, whereas ds≥2Kd_s\ge2K implies Es≥2K−εK>KE_s\ge2K-\varepsilon K>K. In the first branch, ∣Es−ds∣≤ε(ds+K)/3≤εds\lvert E_s-d_s\rvert\le\varepsilon(d_s+K)/3\le\varepsilon d_s; in the second, the threshold guarantee applies, including at zero. The failure budgets add, as do all retained states and arrival costs. The space is at most

ε−3/2K mo(1)+O~(ε−2(m/K)2).\varepsilon^{-3/2}\sqrt{K}\,m^{o(1)}+\widetilde{O}\left(\varepsilon^{-2}(m/K)^2\right).

For ε≥1/m\varepsilon\ge1/m, choose K=⌊m4/5ε−1/5⌋≤mK=\left\lfloor m^{4/5}\varepsilon^{-1/5}\right\rfloor\le m. Both terms are then bounded by ε−8/5m2/5+o(1)\varepsilon^{-8/5}m^{2/5+o(1)}. Since

mεK2≤(mε)−3/5≤1,\frac{m}{\varepsilon K^2}\le(m\varepsilon)^{-3/5}\le1,

Theorem 1.1 gives Fourier arrival time O~(ε−1+ε−3m/K2)=O~(ε−2)\widetilde{O}(\varepsilon^{-1}+\varepsilon^{-3}m/K^2)=\widetilde{O}(\varepsilon^{-2}); the threshold matcher takes ε−2mo(1)\varepsilon^{-2}m^{o(1)} time. For ε<1/m\varepsilon<1/m, explicit storage and direct comparison satisfy both claimed bounds.

The Fourier balance with an approximate threshold matcher. The same selection rule works with the threshold matcher of Chan et al. [2 Theorem B.5], which uses O~(ε−2K)\widetilde{O}(\varepsilon^{-2}\sqrt{K}) words. At accuracy η=min⁡{ε,1/3}\eta=\min\{\varepsilon,1/3\} its guarantee at scale k′=dsk'=d_s gives relative accuracy for 1≤ds≤H1\le d_s\le H, and its guarantee at k′=1k'=1 identifies zero exactly by an answer below 1−η1-\eta. Report zero in that case. Taking K=⌊m4/5⌋K=\left\lfloor m^{4/5}\right\rfloor balances this space with O~(ε−2(m/K)2)\widetilde{O}(\varepsilon^{-2}(m/K)^2) from Proposition 2.2, giving O~(m2/5ε−2)\widetilde{O}(m^{2/5}\varepsilon^{-2}) space.

AI disclosure

The results of this paper were obtained in cooperation with GPT 6.1. Model assisted in preparing this write-up. I take full responsibility for the contents of this paper.

Sampling and faster Fourier matching

We prove the faster Fourier implementation of Theorem 1.1, then prove the static sampling tool from § 3. Following the block scheduling used by Starikovskaya, Svagerka, and Uznański [SSU20, Section 4], we prepare contributions from older text before they are needed. We omit a short suffix of recent text, charging its contribution to the additive error allowance. Hashing to a small alphabet and using one-hot encoding lets us share one alphabet map among all Fourier samples in a repetition and batch both updates and queries.

Short Fourier evaluations

We use short Fourier evaluations at nonuniform frequencies. The following construction uses the Taylor expansion around an FFT grid of Anderson and Dahleh [1 Section 3.1]. We include the argument for both the evaluation map and its transpose.

Lemma A.1. Let B,LB,L be positive integers and z1,…,zLz_1,\ldots,z_L be N0N_0th roots of unity specified by their exponents. Suppose B,L,N0B,L,N_0 are polynomially bounded in mm. For polynomially bounded complex inputs, either of the maps

Fℓ=∑v=0B−1xvzℓv(1≤ℓ≤L),Hv=∑ℓ=1Lcℓzℓv(0≤v<B)F_\ell=\sum_{v=0}^{B-1}x_vz_\ell^v\quad(1\leq\ell\leq L),\qquad H_v=\sum_{\ell=1}^{L}c_\ell z_\ell^v\quad(0\leq v<B)

can be evaluated to any prescribed inverse-polynomial absolute error in O~(B+L)\widetilde{O}(B+L) time and space, using O(log⁡(mn))O(\log(mn))-bit words.

Proof. Choose a power of two NN with 4B≤N<8B4B\leq N<8B. Write zℓ=exp⁡(iθℓ)z_\ell=\exp(i\theta_\ell) and choose the nearest grid angle:

θℓ=2πjℓN+δℓ(mod2π),∣δℓ∣≤πN,βℓ=Bδℓ.\theta_\ell=\frac{2\pi j_\ell}{N}+\delta_\ell\pmod{2\pi},\qquad|\delta_\ell|\leq\frac{\pi}{N},\qquad\beta_\ell=B\delta_\ell.

The indices jℓj_\ell are computed by integer arithmetic on the exponents. Since ∣βℓ∣≤π/4|\beta_\ell|\leq\pi/4, for 0≤v<B0\leq v<B we have

zℓv=e2πijℓv/N(∑r=0p−1(iβℓ)rr!(v/B)r+ρℓ,v),∣ρℓ,v∣≤eπ/4(π/4)pp!.z_\ell^v=e^{2\pi i j_\ell v/N}\left(\sum_{r=0}^{p-1}\frac{(i\beta_\ell)^r}{r!}(v/B)^r+\rho_{\ell,v}\right),\qquad|\rho_{\ell,v}|\leq e^{\pi/4}\frac{(\pi/4)^p}{p!}.

For FF, compute the positive-exponent NN-point Fourier sums of xv(v/B)rx_v(v/B)^r, padded with zeros, and read coordinate jℓj_\ell. Multiply it by (iβℓ)r/r!(i\beta_\ell)^r/r! and sum over rr. Transposing gives HH: coordinate reads become bucket additions, diagonal scalings are unchanged, and the Fourier matrix is symmetric. Each Taylor term costs O(Nlog⁡N+L)O(N\log N+L) operations.

The truncation error is bounded by the displayed remainder times ∑v∣xv∣\sum_v|x_v| or ∑ℓ∣cℓ∣\sum_\ell|c_\ell|. Thus p=O(log⁡(mn))p=O(\log(mn)) suffices. Compute Taylor weights recursively; their absolute sum is bounded, and the normalized powers are at most one. Each FFT has logarithmic depth and polynomial error amplification. Consequently inverse-polynomial rounding precision suffices throughout. Repeated nodes are allowed, and no matrix inversion is used.

Batched Fourier matching

Proof of Theorem 1.1. If εK<8\varepsilon K < 8, Proposition 2.2 suffices, since ε−2m/K<8ε−3m/K2\varepsilon^{-2}m/K < 8\varepsilon^{-3}m/K^2. Otherwise let GG be the smallest power of two at least 12/ε12/\varepsilon, and put

L=⌊96mε2K⌋,B=min⁡{⌊L/G⌋,⌊εK/8⌋}.L = \left\lfloor\frac{96m}{\varepsilon^2 K} \right\rfloor,\qquad B = \min\left\{\left\lfloor L/G \right\rfloor,\left\lfloor\varepsilon K/8 \right\rfloor\right\}.

Since G<24/εG < 24/\varepsilon, we have L/G>m/(εK)≥2L/G > m/(\varepsilon K) \ge2, so B≥1B \ge1.

Omitting recent input. Partition time into working blocks Ij=[jB,(j+1)B)I_j = [jB,(j+1)B) and storage blocks of length CC, where

C=B⌊K/(2B)⌋,δ=(1−m) mod B.C = B\left\lfloor K/(2B) \right\rfloor,\qquad\delta= (1-m)\bmod B.

For an output at t∈Ijt \in I_j, t≥m−1t \ge m-1, put s=t−m+1s=t-m+1, v=(j−1)Bv=(j-1)B, and

s0(t)=max⁡{0,C⌊(s−δ)/C⌋},ℓ=s−s0(t),r=t−v+1.s_0(t)=\max\left\{0,C\left\lfloor(s-\delta)/C\right\rfloor\right\},\qquad\ell=s-s_0(t),\qquad r=t-v+1.

We have K/4≤C≤K/2K/4 \le C \le K/2 and B≤K/16B \le K/16. Since both CC and m−1+δm-1+\delta are multiples of BB, each input block belongs to one storage block and s0(t)s_0(t) is constant throughout each output block. Moreover,

0≤ℓ<C+B,r≤2B≤εK/4,ℓ+r<C+3B<K.0 \le\ell< C+B,\qquad r \le2B \le\varepsilon K/4,\qquad\ell+r < C+3B < K.

Thus s0(t)≤s≤vs_0(t) \le s \le v. We omit the rr most recent symbols; this changes the Hamming distance by at most rr.

One hash and one average. Choose a uniform pairwise-independent map h:Σ→[0,G)h:\Sigma\to[0,G). Independent affine Boolean maps for its output bits give a polylogarithmic seed and evaluation time. Fix the alignment, write d=dsd=d_s, and let dhd_h be its full hashed distance. The small-alphabet argument of Kopelowitz and Porat [6 Section 2] gives E[d−dh]=d/G\mathbb{E}[d-d_h]=d/G. Hence Markov’s inequality gives

Pr⁡[d−dh>εd/2]≤1/6;\Pr[d-d_h>\varepsilon d/2]\le1/6;

when d=0d=0, the loss is zero. Use the packed vectors of § 2 with V=T[s0(t):s]V=T[s_0(t):s], the omitted suffix of length rr, and this map hh. Write DD for the retained-prefix hashed distance. Conditional on hh, let UU be the average of LL independent copies of Y−rY-r. By (2), E[U∣h]=D\mathbb{E}[U\mid h]=D and

Var⁡(U∣h)≤4m(2D+ℓ+r)L≤ε2K(2d+K)24≤ε2(d+K)224.(10)\operatorname{Var}(U\mid h)\le\frac{4m(2D+\ell+r)}{L}\le\frac{\varepsilon^2K(2d+K)}{24}\le\frac{\varepsilon^2(d+K)^2}{24}. \tag*{(10)}

Chebyshev’s inequality gives ∣U−D∣≤ε(d+K)/2|U-D|\le\varepsilon(d+K)/2 except with probability 1/61/6. Also 0≤d−D≤d−dh+r0\le d-D\le d-d_h+r. Reserving εK/4\varepsilon K/4 for numerical error, both good events give

∣computed U−d∣≤ε(d+K)/2+εd/2+r+εK/4≤ε(d+K).|\text{computed }U-d|\le\varepsilon(d+K)/2+\varepsilon d/2+r+\varepsilon K/4\le\varepsilon(d+K).

Their joint failure probability is at most 1/31/3. A median of O(log⁡n)O(\log n) independent copies, each with a fresh hash and frequency list, gives the guarantee simultaneously at every alignment with high probability.

Preparing output tables. For one copy with frequencies k1,…,kLk_1,\ldots,k_L, put N=2mGN=2mG, η=ωN\eta=\omega_N, and precompute

A=1L∑a=1L∣x^ka∣2Npka,ca=x^kanGka(m−1)LNpka,za=η−Gka.A=\frac{1}{L}\sum_{a=1}^{L}\frac{|\widehat{x}_{k_a}|^2}{Np_{k_a}},\qquad c_a=\frac{\widehat{x}_{k_a}n^{Gk_a(m-1)}}{LNp_{k_a}},\qquad z_a=\eta^{-Gk_a}.

For the retained text let Qa=∑u=s0(t)v−1ηnka(Gu+h(T[u]))Q_a=\sum_{u=s_0(t)}^{v-1}\eta^{n^{k_a}(Gu+h(T[u]))}. Since w^ka=η−GkasQa\widehat{w}_{k_a}=\eta^{-Gk_a s}Q_a and s=t−m+1s=t-m+1, the average at time tt is

Ut=A−r−Re⁡∑a=1LcaQazat(11)U_t=A-r-\operatorname{Re}\sum_{a=1}^{L}c_aQ_az_a^t \tag*{(11)}

The QaQ_a are constant on IjI_j, and all their input is known at the start of Ij−1I_{j-1}. Store one moment vector per retained storage block and their total. At that time the completed block Ij−2I_{j-2} is available. Expand it into BGBG one-hot coordinates and apply one forward transform at the nodes ηka\eta^{k_a}, multiplied by its global starting phase. Add these increments to its single storage block and to the total. Delete the at most one block preceding the new cutoff s0s_0. One transposed evaluation with nodes zaz_a and weights caQazajBc_aQ_az_a^{jB} then gives the entire table in (11).

Since BG≤LBG\le L, Lemma A.1 bounds the job’s time and workspace by O~(L+BG)=O~(L)\widetilde{O}(L+BG)=\widetilde{O}(L). Only a working block is expanded during streaming. Spread the job over the BB arrivals of Ij−1I_{j-1}; current outputs read the previously completed table. Cutoffs only increase, so deleted moments are never needed again. The first two blocks require no output because m−1≥2Bm-1\ge2B; initialize their history as empty.

Resources and precision. There are O(m/C+1)=O(m/K)O(m/C+1)=O(m/K) retained storage blocks, each with LL moments. The hash seed, sampled coefficients, two raw buffers, two output tables, and in-progress transforms use O~(L)\widetilde{O}(L) further words. Including all copies, space is O~(Lm/K)=O~(ε−2(m/K)2)\widetilde{O}(Lm/K)=\widetilde{O}(\varepsilon^{-2}(m/K)^2) and worst-case arrival time is

O~(1+L/B)=O~(G+L/(εK))=O~(ε−1+ε−3m/K2).\widetilde{O}(1+L/B)=\widetilde{O}(G+L/(\varepsilon K))=\widetilde{O}(\varepsilon^{-1}+\varepsilon^{-3}m/K^2).

The spectra are computed during preprocessing and discarded after sampling. Appendix § 7 gives logarithmic-word arithmetic with error at most εK/4\varepsilon K/4 per copy, completing the error budget.

Sampling with an affine grid

Proof of Lemma 3.1. Identify z∈[0,Q2)z\in[0,Q^2) with X(z)=(z mod Q,⌊z/Q⌋)⊤∈FQ2X(z)=(z\bmod Q,\lfloor z/Q\rfloor)^\top\in\mathbb{F}_Q^2. Choose a uniform invertible matrix L∈FQ2×2L\in\mathbb{F}_Q^{2\times2} and an independent uniform c∈FQ2c\in\mathbb{F}_Q^2. Put F(X)=LX+cF(X)=LX+c and I={0,…,t−1}I=\{0,\ldots,t-1\}, and set

A={z<M:F(X(z))1∈I},B={z<M:F(X(z))2∈I}.A=\{z<M:F(X(z))_1\in I\},\qquad B=\{z<M:F(X(z))_2\in I\}.

The inverse images of I×FQI\times\mathbb{F}_Q and FQ×I\mathbb{F}_Q\times I each have QtQt points. Enumerate these images, restrict to z<Mz<M, and retain the lists, LL, cc, L−1L^{-1} in O(Qt)O(Qt) words.

Moments. First draw the two rows of LL independently and uniformly from FQ2\mathbb{F}_Q^2, before conditioning on invertibility. For any fixed LL, the two independent offsets give each zz paired inclusion probability qq, hence E[Y∣L]=μ:=∑zwz\mathbb{E}[Y\mid L]=\mu:=\sum_z w_z. For distinct z,wz,w, a uniform affine form takes independent uniform values on X(z),X(w)X(z),X(w) because their difference is uniform and the offset makes the first value independently uniform. The second form independently has the same property for the two distinct shifted points. Thus the paired indicators are pairwise independent before conditioning, giving E[(Y−μ)2]=(q−1−1)∑zwz2\mathbb{E}[(Y-\mu)^2]=(q^{-1}-1)\sum_z w_z^2. The probability of invertibility is (1−Q−2)(1−Q−1)≥3/8(1-Q^{-2})(1-Q^{-1})\ge3/8. Conditioning preserves the mean and increases this second moment by at most 8/38/3, proving the lemma’s variance bound.

Enumeration. Reduce ss modulo MM. For j∈{0,1}j \in\{0,1\} write s−jM=d0+Qd1s-jM=d_0+Qd_1, with 0≤d0<Q0 \le d_0<Q. Partition [0,M)[0,M) according to the wrap j=1{z+s≥M}j=1_{\{z+s\ge M\}} and carry e=1{(z mod Q)+d0≥Q}e=1_{\{(z\bmod Q)+d_0\ge Q\}}. On region (j,e)(j,e), writing z′=(z+s) mod Mz'=(z+s)\bmod M, we have

X(z′)=X(z)+δj,eover FQ,δj,e=(d0,d1+e)T.X(z')=X(z)+\delta_{j,e}\quad\text{over }\mathbb{F}_Q,\qquad\delta_{j,e}=(d_0,d_1+e)^{\mathsf T}.

Thus paired inclusion on this region is equivalent to

LX(z)+cj,e∈I2,cj,e=c+(0,(Lδj,e)2)T.LX(z)+c_{j,e}\in I^2,\qquad c_{j,e}=c+(0,(L\delta_{j,e})_2)^{\mathsf T}.

The regions depend only on M,Q,sM,Q,s. For each region (j,e)(j,e) and each (u,v)∈I2(u,v)\in I^2, compute X=L−1((u,v)T−cj,e)X=L^{-1}((u,v)^{\mathsf T}-c_{j,e}). Using integer coordinates 0≤x,y<Q0\le x,y<Q, recover z=x+Qyz=x+Qy and retain it exactly when z<Mz<M and its actual wrap and carry equal (j,e)(j,e). The region identity then proves that z∈C(s)z\in C(s). Conversely, every active point has a unique region and pair (u,v)(u,v), so it is reported exactly once. The 4t24t^2 candidates take constant time each using the stored inverse.

Logarithmic-word implementation

For either Fourier implementation, let a=x^a=\hat{x} and N=2mGN=2mG. During preprocessing compute dyadic upper bounds ∣ak∣2≤uk≤∣ak∣2+1/2|a_k|^2\le u_k\le|a_k|^2+1/2 and put vk=1+⌊uk⌋v_k=1+\lfloor u_k\rfloor. These bounds can be obtained by evaluating the DFT to sufficiently fine inverse-polynomial precision, since ∣ak∣≤m|a_k|\le m. The Parseval identity gives ∑k∣ak∣2=Nm\sum_k|a_k|^2=Nm. Thus

vk≥max⁡{1,∣ak∣2},V=∑kvk≤N(m+3/2).v_k\ge\max\{1,|a_k|^2\},\qquad V=\sum_k v_k\le N(m+3/2).

Let MM be the least power of two at least VV. Add M−VM-V to the first bin and divide the resulting masses by MM to obtain pp. Drawing log⁡2M\log_2 M random bits selects a position in the cumulative integer masses exactly. Since M<2V≤4NmM<2V\le4Nm for m≥2m\ge2, every bin has pk≥1/Mp_k\ge1/M and ∣ak∣2/(Npk)≤M/N≤4m|a_k|^2/(Np_k)\le M/N\le4m, as required by Lemma 2.1.

All stored sample coefficients are polynomially bounded, since 1/pk≤M1/p_k\le M and NN, mm, 1/ε1/\varepsilon are polynomial in mm. Round these coefficients and the phases to a common dyadic precision, reducing phase exponents modulo NN before evaluation. Each block sum receives only additions and subtractions, so errors over polynomially many updates accumulate additively. In the batched algorithm, Lemma A.1 gives inverse-polynomial absolute error in each forward transform. The output transform multiplies moment errors by polynomially bounded coefficients, and its results are used only for output. Thus a sufficiently fine inverse-polynomial mesh gives absolute error at most εK/2\varepsilon K/2 per coarse mean and εK/4\varepsilon K/4 per batched mean. Medians preserve these error bounds. Each scalar uses O(log⁡(mn))O(\log(mn)) bits, and the full pattern spectrum and sampling tables are discarded before the text arrives.

Reduction from L1L_1 distance

Let U≥1U\ge1 be an integer. For symbols in {0,…,U−1}\{0,\ldots,U-1\}, define Ds=∑j=0m−1∣P[j]−T[s+j]∣D_s=\sum_{j=0}^{m-1}|P[j]-T[s+j]|. Exact reductions from L1L_1 to Hamming distance are given by Labib, Uznański, and Wolleb-Graf [7 Section 5]. Signed reconstruction requires an additional stability argument for relative approximation. We give a symmetric halving identity and use a common random translation to bound its absolute coefficient mass.

Corollary C.1. In the model of § 1, let U=mO(1)U=m^{O(1)}, w=1+⌈log⁡U⌉w=1+\lceil\log U\rceil, J=w(w+1)J=w(w+1), and η=ε/(12J)\eta=\varepsilon/(12J). Suppose a streaming Hamming matcher on an alphabet of size 2w2^w returns a

relative-η\eta estimate with probability at least 2/3 at each fixed alignment. Then streaming L1L_1 matching on {0,…,U−1}\{0,\ldots,U-1\} gives relative-ϵ\epsilon estimates at all alignments simultaneously with high probability, using O(Jlog⁡Jlog⁡n)O(J\log J\log n) times the matcher’s space and worst-case arrival time at the same pattern and text lengths.

Since J=O(log⁡2(2U))J=O(\log^2(2U)), applying the corollary to Theorem 1.3 and to Theorem 1.2 with H=mH=m gives L1L_1 space ϵ−8/5m2/5+o(1)\epsilon^{-8/5}m^{2/5+o(1)} and ϵ−1m1/2+o(1)\epsilon^{-1}m^{1/2+o(1)}, respectively, with ϵ−2mo(1)\epsilon^{-2}m^{o(1)} worst-case arrival time in either case. The Fourier balance in § 4 gives O~(m2/5ϵ−2)\widetilde{O}(m^{2/5}\epsilon^{-2}) space.

Lemma C.2. Let U≥2U\ge2 be an integer and put w=1+⌈log⁡2U⌉w=1+\lceil\log_2 U\rceil. There are J=w(w+1)J=w(w+1) maps fℓ:{0,…,2w−1}→{0,…,2w−1}f_\ell:\{0,\ldots,2^w-1\}\to\{0,\ldots,2^w-1\}, computable in constant word time, and integer coefficients cℓc_\ell of magnitude O(U)O(U) such that

∣X−Y∣=∑ℓ=1Jcℓ1{fℓ(X)≠fℓ(Y)}\lvert X-Y\rvert=\sum_{\ell=1}^{J}c_\ell\mathbf{1}_{\{f_\ell(X)\ne f_\ell(Y)\}}

for all integers X,Y∈[0,2w)X,Y\in[0,2^w). If Δ\Delta is uniform in [0,2w−1)∩Z[0,2^{w-1})\cap\mathbb{Z}, then, for every fixed x,y∈[0,U)∩Zx,y\in[0,U)\cap\mathbb{Z},

EΔ∑ℓ=1J∣cℓ∣1{fℓ(x+Δ)≠fℓ(y+Δ)}≤w(w+1)∣x−y∣.(12)\mathbb{E}_{\Delta}\sum_{\ell=1}^{J}\lvert c_\ell\rvert\mathbf{1}_{\{f_\ell(x+\Delta)\ne f_\ell(y+\Delta)\}}\le w(w+1)\lvert x-y\rvert. \tag*{(12)}

Proof. Write qi(z)=⌊z/2i⌋q_i(z)=\lfloor z/2^i\rfloor, bi(z)=qi(z) mod 2b_i(z)=q_i(z)\bmod2, and Hf=1{f(X)≠f(Y)}H_f=\mathbf{1}_{\{f(X)\ne f(Y)\}}. Define two maps on bit pairs by

(a,b)00011011f+(a,b)0221f−(a,b)2012\begin{array}{c|cccc} (a,b)&00&01&10&11\\ \hline f_+(a,b)&0&2&2&1\\ f_-(a,b)&2&0&1&2 \end{array}

Their Hamming distances satisfy

1{f+(a,b)≠f+(a′,b′)}−1{f−(a,b)≠f−(a′,b′)}=(a−a′)(b−b′).\mathbf{1}_{\{f_+(a,b)\ne f_+(a',b')\}}-\mathbf{1}_{\{f_-(a,b)\ne f_-(a',b')\}}=(a-a')(b-b').

For 0≤i<k<w0\le i<k<w, put

gi,k±(z)=3qk+1(z)+f±(bk(z),bi(z)).g_{i,k}^{\pm}(z)=3q_{k+1}(z)+f_{\pm}(b_k(z),b_i(z)).

The required identity is

∣X−Y∣=∑i=0w−12i(Hqi−Hqi+1+∑k=i+1w−1(Hgi,k+−Hgi,k−)).(13)\lvert X-Y\rvert=\sum_{i=0}^{w-1}2^i\left(H_{q_i}-H_{q_{i+1}}+\sum_{k=i+1}^{w-1}\left(H_{g_{i,k}^{+}}-H_{g_{i,k}^{-}}\right)\right). \tag*{(13)}

For X≠YX\ne Y, let jj be their highest differing bit and put σ=bj(X)−bj(Y)=sgn⁡(X−Y)\sigma=b_j(X)-b_j(Y)=\operatorname{sgn}(X-Y). The parenthesis at bit ii equals σ(bi(X)−bi(Y))\sigma(b_i(X)-b_i(Y)). Indeed, for k<jk<j the prefixes above kk differ, so both maps disagree and their contributions cancel. For k>jk>j the kkth bits agree, so the bit-pair identity gives zero. Thus if i<ji<j, only k=jk=j contributes and gives the claimed product. At i=ji=j the prefix-indicator difference is one, and for i>ji>j all terms vanish. Summing with weights 2i2^i gives σ(X−Y)=∣X−Y∣\sigma(X-Y)=\lvert X-Y\rvert. For X=YX=Y all summands are zero.

There are 2w+2(w2)=w(w+1)2w+2\binom{w}{2}=w(w+1) terms, each using the same map on both inputs. Their values lie in [0,2w)[0,2^w), since k≥1k\ge1 gives gi,k±(z)<3⋅2w−2<2wg_{i,k}^{\pm}(z)<3\cdot2^{w-2}<2^w.

Keep these terms separately when taking absolute coefficients. Every map at scale ii depends only on bits ii and above, and their total absolute coefficient is 2i+1(w−i)2^{i+1}(w-i). Thus the mass is at most

∑i=0w−12i+1(w−i)1{qi(x+Δ)≠qi(y+Δ)}.\sum_{i=0}^{w-1}2^{i+1}(w-i)\mathbf{1}_{\{q_i(x+\Delta)\ne q_i(y+\Delta)\}}.

Since 2i2^i divides 2w−12^{w-1}, the probability of the displayed indicator is min⁡{1,∣x−y∣/2i}\min\{1,\lvert x-y\rvert/2^i\}. Taking expectations gives 2∑i(w−i)∣x−y∣=w(w+1)∣x−y∣2\sum_i(w-i)\lvert x-y\rvert=w(w+1)\lvert x-y\rvert.

Proof of Corollary C.1. For U=1U=1 every answer is zero. Otherwise draw the shift Δ\Delta of Lemma C.2 before pattern preprocessing. For each ℓ\ell, map every pattern and text symbol xx to fℓ(x+Δ)f_\ell(x+\Delta) and run the given Hamming matcher at accuracy η\eta on the mapped stream. At each alignment ss, estimate the mapped distance Hℓ(s)H_\ell(s) by the median H^ℓ(s)\widehat{H}_\ell(s) of O(log⁡J)O(\log J) independent copies. Conditional on the shift, the mapped stream is fixed, so the median fails with probability at most 1/(6J)1/(6J) for each fixed ss. The mapped windows all end at the same arrival. Form the signed estimate D^s=∑ℓcℓH^ℓ(s)\widehat{D}_s=\sum_\ell c_\ell\widehat{H}_\ell(s) there.

By Lemma C.2, Ds=∑ℓcℓHℓ(s)D_s=\sum_\ell c_\ell H_\ell(s) and the mass Ms=∑ℓ∣cℓ∣Hℓ(s)M_s=\sum_\ell|c_\ell|H_\ell(s) satisfies EMs≤JDs\mathbb{E}M_s\le JD_s. For fixed ss with Ds>0D_s>0, Markov’s inequality gives Ms≤6JDsM_s\le6JD_s except with probability 1/61/6. A union bound over the JJ medians gives failure probability at most 1/61/6 for any shift. When both events hold,

∣D^s−Ds∣≤ηMs≤εDs/2.|\widehat{D}_s-D_s|\le\eta M_s\le\varepsilon D_s/2.

For Ds=0D_s=0, every mapped distance and every successful Hamming estimate is exactly zero. No cancellation assumption is needed.

For word arithmetic, clamp Hamming estimates to [0,m][0,m] and round them down to a common dyadic grid of mesh at most ε/(2∑ℓ∣cℓ∣)\varepsilon/(2\sum_\ell|c_\ell|). The signed sum then has rounding error at most ε/2\varepsilon/2 and uses O(log⁡(mU/ε))=O(log⁡(mn))O(\log(mU/\varepsilon))=O(\log(mn)) bits. Zero is preserved, and every positive DsD_s is an integer, so this error fits the remaining budget.

Run R=O(log⁡n)R=O(\log n) independent repetitions, each with its own shift, and report their median at each alignment. Each repetition fails at a fixed alignment with probability at most 1/31/3, so median amplification and a union bound give simultaneous success with probability at least 1−n−c1-n^{-c}. There are O(RJlog⁡J)O(RJ\log J) Hamming instances, and all their retained states count toward space. Each map takes constant word time. Computing each median by linear-time selection, the reduction uses O(RJlog⁡J)O(RJ\log J) additional words and O(RJlog⁡J)O(RJ\log J) additional worst-case time per arrival.

References

  1. [1]Chris Anderson and Marie Dillon Dahleh. Rapid computation of the discrete Fourier transform. SIAM Journal on Scientific Computing, 17(4):913–919, 1996. https://users.math.msu.edu/users/iwenmark/Teaching/MTH995/Papers/NDFT_Taylor.pdf.DOI
  2. [2]Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat. Approximating text-to-pattern Hamming distances, 2020. https://arxiv.org/html/2001.00211v1.
  3. [3]Raphaël Clifford, Tomasz Kociumaka, and Ely Porat. The streaming k-mismatch problem, 2018. https://arxiv.org/abs/1708.05223.
  4. [4]Michael S. Crouch and Andrew McGregor. Periodicity and cyclic shifts via linear sketches. In APPROX/RANDOM, 2011. https://people.cs.umass.edu/~mcgregor/papers/11-approx.pdf.DOI
  5. [5]Shay Golan, Tsvi Kopelowitz, and Ely Porat. Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams. In ICALP, volume 107 of LIPIcs, pages 65:1–65:16, 2018. https://doi.org/10.4230/LIPIcs.ICALP.2018.65.
  6. [6]Tsvi Kopelowitz and Ely Porat. A simple algorithm for approximating the text-to-pattern Hamming distance. In SOSA, volume 61 of OASIcs, pages 10:1–10:5, 2018. https://doi.org/10.4230/OASIcs.SOSA.2018.10.
  7. [7]Karim Labib, Przemysław Uznański, and Daniel Wolleb-Graf. Hamming distance completeness. In CPM, volume 128 of LIPIcs, pages 14:1–14:17, 2019. https://doi.org/10.4230/LIPIcs.CPM.2019.14.

Paper details

vlnc:W_ugapemc7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT 6.1

View statement
Looking for related papers…
Contents