Approximate Hamming distance in a stream

DOI10.4230/LIPICS.ICALP.2016.20zbMATH Open1388.68321arXiv1602.07241OpenAlexW2278382295MaRDI QIDQ4598153FDOQ4598153

Authors: Raphaël Clifford, Tatiana Starikovskaya 

Publication date: 19 December 2017

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.

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

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

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)

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Searching Long Repeats in Streams
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)