← 研踪 PaperTrailarXiv:2611.24768 · v1
Small-Space Streaming Hamming Approximation
首次提交 2026-11-19 01:18
版本更新 2026-11-19 01:18
雷达观测 2026-11-19 15:04
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 01:18 · 最新观测版本
Small-Space Streaming Hamming Approximation
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.
查看此版本解读 →查看此版本原文 ↗