WorksComputer Science
Small-Space Streaming Hamming Approximation
Abstract
For a preprocessed pattern of length and a streaming text, we give two algorithms that estimate the Hamming distance at every alignment to relative error . They use and 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 , due to Chan et al. [CGK+20], and , a consequence of their results and those of Clifford, Kociumaka, and Porat [CKP18]. For , the better of our two bounds improves on both prior space exponents for every fixed . A Fourier matcher uses words to estimate each distance within , giving relative error at most for . 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 matching over polynomially bounded integer symbols.
Introduction and results
Given a pattern and a text , the text-to-pattern Hamming distances are
Indices are zero-based, and denotes a half-open substring. Intervals used as index sets contain only integers. In the streaming setting, the answer for must be reported when arrives. A relative- estimate satisfies ; 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 , , and that and are polynomial in , with . We use -bit words. All answers must be correct simultaneously with probability at least for any fixed ; this is what we mean by with high probability. Space and worst-case arrival time refer to the text-streaming phase. We allow for any fixed . The notation hides polylogarithmic factors in , , and .
Our first ingredient estimates large distances using Fourier samples.
Theorem 1.1. For every integer , the above model admits a streaming estimator using words and worst-case time per arrival. Its estimates satisfy simultaneously at all alignments with high probability.
For , this gives relative error at most . 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 , there is a streaming Hamming matcher using words and worst-case time per arrival. With high probability, it gives relative- estimates simultaneously at all alignments with . In particular, gives relative- estimates at all alignments using words.
Combining this threshold matcher with the Fourier matcher gives a second space bound for all alignments.
Theorem 1.3. Relative- Hamming matching in our model admits space and worst-case time per arriving text symbol.
Choosing between the two relative-approximation algorithms and explicit storage of the pattern and current window gives space
The term depends only on and tends to zero as . Balancing the Fourier matcher with the small-distance matcher of Chan et al. [2 Theorem B.5] gives space, as shown in § 4.
Prior bounds. Starikovskaya, Svagerka, and Uznański [SSU20] give an algorithm using space and arrival time in the stronger model where the pattern also arrives in one pass. Chan, Golan, Kociumaka, Kopelowitz, and Porat [2] use space and arrival time with pattern preprocessing. An unpublished consequence of prior work gives space.1
Our Fourier matcher recovers the same bound by balancing its space with the exact matcher’s at . When , use the exact answer when available and Theorem 1.1 with parameter otherwise, since then . For , explicit storage suffices.
Figure 1 compares (1) with the minimum of these prior bounds and linear storage. For , our leading space exponent is smaller for every fixed .

Figure 1. Space for . The dashed curve follows the published bound of Chan et al. up to and the unpublished bound in footnote 1 thereafter. The solid curve gives (1), switching at .
For Theorem 1.1, we first analyze a simpler implementation. At an integer cutoff , it uses space and arrival time, with mixed relative and additive error . It stores Fourier sums for text blocks of length ; 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 reduction.
The Fourier matcher
For a vector , write and for its unnormalized Fourier transform. We estimate by sampling a frequency. Frequencies that carry more of the pattern energy must be sampled with sufficiently high probability.
Lemma 2.1. Let with , and put , . Suppose is a distribution with and for every . Draw from and put
Then and .
Proof. In the mean, cancels the denominator, leaving by the Parseval identity. For the second moment,
Use a map and represent each symbol by the standard basis vector . Extend to strings by concatenation, denoted by , and write for numerical zeros. Let be the current window, let be the characters retained immediately before it, and suppose the most recent characters of are omitted. At length , put
Let count mismatches under 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 and . Lemma 2.1 gives
Appendix § 7 constructs an exactly sampleable dyadic distribution with the required bound from the pattern alone.
Proposition 2.2. For every integer and accuracy in the model of § 1, there is a streaming estimator using words and worst-case time per arrival that reports estimates satisfying
simultaneously for all alignments , with high probability.
Proof. Take and , so the one-hot encoding preserves every mismatch. Partition the text into blocks of length . When arrives, the blocks meeting the window also cover the preceding string , where . Thus , , and . By (2), the mean of independent samples is unbiased and has variance
Chebyshev’s inequality bounds the error by with failure probability at most . Take the median of independent means and union bound over alignments. Numerical error contributes at most by Appendix § 7, giving (3).
During preprocessing, retain for each sampled frequency the two coefficients and needed for . 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 is a single phase. For each live block keep
Maintain the sum over live blocks, starting with an empty queue. Update the current block and the total on arrival. When advances, subtract and discard the oldest block. Multiplying the total by gives , since a retained symbol at occupies coordinate in . There are live blocks per frequency and sampled frequencies. Scanning these frequencies per arrival gives the stated time and space. Only pattern preprocessing uses the full transform of length .
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 be prime and let be integers with and . There are random sets , each of size at most , represented in words, with the following properties. For each integer shift , the representation enumerates in time. For fixed nonnegative weights , put and . Then
Proof of Theorem 1.2. We handle bounded by explicit storage. For sufficiently large , put
Let be the primes in and put . The standard prime-counting bound gives . Choose independent uniform and set and . Thus . For every fixed integer ,
Indeed, conditional on , the remaining quotient has at most prime divisors in , since each is at least and . The next independent prime divides it with probability at most . This also allows repeated primes.
Choose the depth
It depends only on . Fix an alignment , its mismatch set , and . Let . For and , let be one less than the number of occupied residues modulo inside residue modulo , or zero if it is empty. Then
since . Each occupied child contains a mismatch, so is at most the number of ordered pairs of distinct mismatches in the parent. Similarly, is at most the number of unordered pairs colliding modulo . By (5),
If , the second bound is at most . If , the deficit is zero because .
The estimator. For , put and fix a prime with and , using Bertrand’s postulate. We use the common sample budget
Set and . Independently at each level , draw from Lemma 3.1 with parameters . Set
Conditional on the moduli, its mean is . A fully sampled level has ; otherwise . The sampling lemma and independence between levels therefore give
Consequently, Cauchy–Schwarz and the deficit bound give
Markov’s inequality gives relative- accuracy with probability at least when . At or , the ideal answer is exact.
Streaming implementation. Use the equal-length multi-stream dictionary matcher of Golan, Kopelowitz, and Porat [5 Theorem 1]. For patterns and streams, it uses 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 , for every put all its nonempty fine pattern residues into the dictionary: for , , the string is
stopping before position . Their lengths are or , so two equal-length dictionaries suffice. For each , maintain its fine text residue streams, with state for both dictionary lengths. An arrival at position updates stream if . Cache each stream’s latest matching identifier for each length.
At alignment , enumerate the selected parent pairs using Lemma 3.1. For each reported parent , compare every nonempty fine pattern residue against the current suffix of stream , using its length. This suffix consists exactly of the corresponding characters in . The number of failed equalities is the number of occupied children, and hence determines . Maintain in the same way, using all 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 pattern parents and as many text parents, each with fewer than children. Thus space is . At most two dictionary states are updated per level per arrival. The sampling lemma enumerates all active parents in time; their child queries and the root scan give worst-case arrival time . Since and ,
Thus . For the space bound,
using . Substitution gives arrival time and space
Both subpolynomial factors are at most , since . Finally, and give the first bound below; minimality of gives the second, including and :
This gives the stated space bound. When , every is at most and the bound becomes .
Every weight is either one or , so is a common integer denominator. Since and , 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 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 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 . Run the Fourier matcher of Theorem 1.1 at accuracy and the residue matcher of Theorem 1.2 at threshold . Output the Fourier estimate if and the threshold answer otherwise. On simultaneous success, the Fourier guarantee gives
Indeed, implies , whereas implies . In the first branch, ; 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
For , choose . Both terms are then bounded by . Since
Theorem 1.1 gives Fourier arrival time ; the threshold matcher takes time. For , 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 words. At accuracy its guarantee at scale gives relative accuracy for , and its guarantee at identifies zero exactly by an answer below . Report zero in that case. Taking balances this space with from Proposition 2.2, giving 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 be positive integers and be th roots of unity specified by their exponents. Suppose are polynomially bounded in . For polynomially bounded complex inputs, either of the maps
can be evaluated to any prescribed inverse-polynomial absolute error in time and space, using -bit words.
Proof. Choose a power of two with . Write and choose the nearest grid angle:
The indices are computed by integer arithmetic on the exponents. Since , for we have
For , compute the positive-exponent -point Fourier sums of , padded with zeros, and read coordinate . Multiply it by and sum over . Transposing gives : coordinate reads become bucket additions, diagonal scalings are unchanged, and the Fourier matrix is symmetric. Each Taylor term costs operations.
The truncation error is bounded by the displayed remainder times or . Thus 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 , Proposition 2.2 suffices, since . Otherwise let be the smallest power of two at least , and put
Since , we have , so .
Omitting recent input. Partition time into working blocks and storage blocks of length , where
For an output at , , put , , and
We have and . Since both and are multiples of , each input block belongs to one storage block and is constant throughout each output block. Moreover,
Thus . We omit the most recent symbols; this changes the Hamming distance by at most .
One hash and one average. Choose a uniform pairwise-independent map . Independent affine Boolean maps for its output bits give a polylogarithmic seed and evaluation time. Fix the alignment, write , and let be its full hashed distance. The small-alphabet argument of Kopelowitz and Porat [6 Section 2] gives . Hence Markov’s inequality gives
when , the loss is zero. Use the packed vectors of § 2 with , the omitted suffix of length , and this map . Write for the retained-prefix hashed distance. Conditional on , let be the average of independent copies of . By (2), and
Chebyshev’s inequality gives except with probability . Also . Reserving for numerical error, both good events give
Their joint failure probability is at most . A median of 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 , put , , and precompute
For the retained text let . Since and , the average at time is
The are constant on , and all their input is known at the start of . Store one moment vector per retained storage block and their total. At that time the completed block is available. Expand it into one-hot coordinates and apply one forward transform at the nodes , 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 . One transposed evaluation with nodes and weights then gives the entire table in (11).
Since , Lemma A.1 bounds the job’s time and workspace by . Only a working block is expanded during streaming. Spread the job over the arrivals of ; 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 ; initialize their history as empty.
Resources and precision. There are retained storage blocks, each with moments. The hash seed, sampled coefficients, two raw buffers, two output tables, and in-progress transforms use further words. Including all copies, space is and worst-case arrival time is
The spectra are computed during preprocessing and discarded after sampling. Appendix § 7 gives logarithmic-word arithmetic with error at most per copy, completing the error budget.
Sampling with an affine grid
Proof of Lemma 3.1. Identify with . Choose a uniform invertible matrix and an independent uniform . Put and , and set
The inverse images of and each have points. Enumerate these images, restrict to , and retain the lists, , , in words.
Moments. First draw the two rows of independently and uniformly from , before conditioning on invertibility. For any fixed , the two independent offsets give each paired inclusion probability , hence . For distinct , a uniform affine form takes independent uniform values on 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 . The probability of invertibility is . Conditioning preserves the mean and increases this second moment by at most , proving the lemma’s variance bound.
Enumeration. Reduce modulo . For write , with . Partition according to the wrap and carry . On region , writing , we have
Thus paired inclusion on this region is equivalent to
The regions depend only on . For each region and each , compute . Using integer coordinates , recover and retain it exactly when and its actual wrap and carry equal . The region identity then proves that . Conversely, every active point has a unique region and pair , so it is reported exactly once. The candidates take constant time each using the stored inverse.
Logarithmic-word implementation
For either Fourier implementation, let and . During preprocessing compute dyadic upper bounds and put . These bounds can be obtained by evaluating the DFT to sufficiently fine inverse-polynomial precision, since . The Parseval identity gives . Thus
Let be the least power of two at least . Add to the first bin and divide the resulting masses by to obtain . Drawing random bits selects a position in the cumulative integer masses exactly. Since for , every bin has and , as required by Lemma 2.1.
All stored sample coefficients are polynomially bounded, since and , , are polynomial in . Round these coefficients and the phases to a common dyadic precision, reducing phase exponents modulo 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 per coarse mean and per batched mean. Medians preserve these error bounds. Each scalar uses bits, and the full pattern spectrum and sampling tables are discarded before the text arrives.
Reduction from distance
Let be an integer. For symbols in , define . Exact reductions from 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 , , , and . Suppose a streaming Hamming matcher on an alphabet of size returns a
relative- estimate with probability at least 2/3 at each fixed alignment. Then streaming matching on gives relative- estimates at all alignments simultaneously with high probability, using times the matcher’s space and worst-case arrival time at the same pattern and text lengths.
Since , applying the corollary to Theorem 1.3 and to Theorem 1.2 with gives space and , respectively, with worst-case arrival time in either case. The Fourier balance in § 4 gives space.
Lemma C.2. Let be an integer and put . There are maps , computable in constant word time, and integer coefficients of magnitude such that
for all integers . If is uniform in , then, for every fixed ,
Proof. Write , , and . Define two maps on bit pairs by
Their Hamming distances satisfy
For , put
The required identity is
For , let be their highest differing bit and put . The parenthesis at bit equals . Indeed, for the prefixes above differ, so both maps disagree and their contributions cancel. For the th bits agree, so the bit-pair identity gives zero. Thus if , only contributes and gives the claimed product. At the prefix-indicator difference is one, and for all terms vanish. Summing with weights gives . For all summands are zero.
There are terms, each using the same map on both inputs. Their values lie in , since gives .
Keep these terms separately when taking absolute coefficients. Every map at scale depends only on bits and above, and their total absolute coefficient is . Thus the mass is at most
Since divides , the probability of the displayed indicator is . Taking expectations gives .
Proof of Corollary C.1. For every answer is zero. Otherwise draw the shift of Lemma C.2 before pattern preprocessing. For each , map every pattern and text symbol to and run the given Hamming matcher at accuracy on the mapped stream. At each alignment , estimate the mapped distance by the median of independent copies. Conditional on the shift, the mapped stream is fixed, so the median fails with probability at most for each fixed . The mapped windows all end at the same arrival. Form the signed estimate there.
By Lemma C.2, and the mass satisfies . For fixed with , Markov’s inequality gives except with probability . A union bound over the medians gives failure probability at most for any shift. When both events hold,
For , every mapped distance and every successful Hamming estimate is exactly zero. No cancellation assumption is needed.
For word arithmetic, clamp Hamming estimates to and round them down to a common dyadic grid of mesh at most . The signed sum then has rounding error at most and uses bits. Zero is preserved, and every positive is an integer, so this error fits the remaining budget.
Run 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 , so median amplification and a union bound give simultaneous success with probability at least . There are 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 additional words and additional worst-case time per arrival.
References
- [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]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]Raphaël Clifford, Tomasz Kociumaka, and Ely Porat. The streaming k-mismatch problem, 2018. https://arxiv.org/abs/1708.05223.
- [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]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]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]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.