Approximate Hamming distance in a stream

DOI10.4230/LIPICS.ICALP.2016.20MaRDI QIDQ4598153zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Tatiana Starikovskaya

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1602.07241

zbMATH Keywords

Hamming distancecommunication complexitydata stream model

Mathematics Subject Classification ID

Randomized algorithms (68W20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Algorithms on strings (68W32)

Abstract: We consider the problem of computing a $(1+epsilon)$-approximation of the Hamming distance between a pattern of length $n$ and successive substrings of a stream. We first look at the one-way randomised communication complexity of this problem, giving Alice the first half of the stream and Bob the second half. We show the following: (1) If Alice and Bob both share the pattern then there is an $O(epsilo{n}^{-4}lo{g}^{2}n)$ bit randomised one-way communication protocol. (2) If only Alice has the pattern then there is an $O(epsilo{n}^{-2}sqrtnlogn)$ bit randomised one-way communication protocol. We then go on to develop small space streaming algorithms for $(1+epsilon)$-approximate Hamming distance which give worst case running time guarantees per arriving symbol. (1) For binary input alphabets there is an $O(epsilo{n}^{-3}sqrtnlo{g}^{2}n)$ space and $O(epsilo{n}^{-2}logn)$ time streaming $(1+epsilon)$-approximate Hamming distance algorithm. (2) For general input alphabets there is an $O(epsilo{n}^{-5}sqrtnlo{g}^{4}n)$ space and $O(epsilo{n}^{-4}lo{g}^{3}n)$ time streaming $(1+epsilon)$-approximate Hamming distance algorithm.

Recommendations

• Communication and Streaming Complexity of Approximate Pattern Matching
• A simple algorithm for approximating the text-to-pattern Hamming distance
• The streaming \(k\)-mismatch problem
• The one-way communication complexity of Hamming distance
• Tight Cell-Probe Bounds for Online Hamming Distance Computation

Cited in

(16)

• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Recent advances in text-to-pattern distance algorithms
• Time bounds for streaming problems
• scientific article; zbMATH DE number 7559138 (Why is no real title available?)
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Streaming \(k\)-mismatch with error correcting and applications
• The one-way communication complexity of Hamming distance
• Improved Sketching of Hamming Distance with Error Correcting
• Exploiting pseudo-locality of interchange distance
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Searching Long Repeats in Streams
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• A simple algorithm for approximating the text-to-pattern Hamming distance
• Automata theory on sliding windows
• Time-homogeneous top-\(K\) ranking using tensor decompositions

This page was built for publication: Approximate Hamming distance in a stream

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598153)