Abstract
We consider the problem of computing a (1+ε)-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:
- If Alice and Bob both share the pattern then there is an O(ε-4 log2n) bit randomised one-way communication protocol.
- If only Alice has the pattern then there is an O(ε-2√n log n) bit randomised one-way communication protocol.
We then go on to develop small space streaming algorithms for (1 + ε)- approximate Hamming distance which give worst case running time guarantees per arriving symbol.
- For binary input alphabets there is an O(ε-3√ n log2 n) space and O(ε-2 log n) time streaming (1+ε)-approximate Hamming distance algorithm.
- For general input alphabets there is an O(ε-5√ n log4 n) space and O(ε-4 log3 n) time streaming (1+ε)-approximate Hamming distance algorithm.
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:
- If Alice and Bob both share the pattern then there is an O(ε-4 log2n) bit randomised one-way communication protocol.
- If only Alice has the pattern then there is an O(ε-2√n log n) bit randomised one-way communication protocol.
We then go on to develop small space streaming algorithms for (1 + ε)- approximate Hamming distance which give worst case running time guarantees per arriving symbol.
- For binary input alphabets there is an O(ε-3√ n log2 n) space and O(ε-2 log n) time streaming (1+ε)-approximate Hamming distance algorithm.
- For general input alphabets there is an O(ε-5√ n log4 n) space and O(ε-4 log3 n) time streaming (1+ε)-approximate Hamming distance algorithm.
| Original language | English |
|---|---|
| Title of host publication | 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016) |
| Editors | Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany |
| Pages | 20:1-20:14 |
| Number of pages | 14 |
| ISBN (Print) | 9783959770132 |
| DOIs | |
| Publication status | Published - 1 Aug 2016 |
| Event | ICALP ICALP 2016 Track A - Sapienza University of Rome, Rome, Italy Duration: 12 Jul 2016 → 15 Jul 2016 |
Publication series
| Name | Liebniz International Proceedings in Informatics (LIPIcs) |
|---|---|
| Publisher | Schloss Dagstuhl - Liebniz-Zentrum für Informatik |
| Volume | 55 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | ICALP ICALP 2016 Track A |
|---|---|
| Country/Territory | Italy |
| City | Rome |
| Period | 12/07/16 → 15/07/16 |
Fingerprint
Dive into the research topics of 'Approximate Hamming distance in a stream'. Together they form a unique fingerprint.Profiles
-
Dr Raphael Clifford
- Department of Computer Science - Reader in Algorithm Design
- Intelligent Systems Laboratory
- Theory and Algorithms
Person: Academic , Member, Group lead