Name
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. We show the following:- If Alice and Bob both share the pattern and Alice has the first half of the stream and Bob the second half, then there is an O(epsilon^{-4}*log^2(n)) bit randomised one-way communication protocol.- If Alice has the pattern, Bob the first half of the stream and Charlie the second half, then there is an O(epsilon^{-2}*sqrt(n)*log(n)) 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.- For binary input alphabets there is an O(epsilon^{-3}*sqrt(n)*log^2(n)) space and O(epsilon^{-2}*log(n)) time streaming(1 + epsilon)-approximate Hamming distance algorithm.- For general input alphabets there is an O(epsilon^{-5}*sqrt(n)*log^4(n)) space and O(epsilon^{-4}*log^3(n)) time streaming(1 + epsilon)-approximate Hamming distance algorithm. |
Year | Venue | DocType |
|---|---|---|
2016 | ICALP | Conference |
Volume | Citations | PageRank |
abs/1602.07241 | 5 | 0.45 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Tatiana A. Starikovskaya | 2 | 71 | 14.95 |