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 oneway 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} log^{2}n) bit randomised oneway communication protocol.
 If only Alice has the pattern then there is an O(ε^{2}√n log n) bit randomised oneway 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 log^{2} n) space and O(ε^{2} log n) time streaming (1+ε)approximate Hamming distance algorithm.
 For general input alphabets there is an O(ε^{5}√ n log^{4} n) space and O(ε^{4} log^{3} 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 oneway 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} log^{2}n) bit randomised oneway communication protocol.
 If only Alice has the pattern then there is an O(ε^{2}√n log n) bit randomised oneway 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 log^{2} n) space and O(ε^{2} log n) time streaming (1+ε)approximate Hamming distance algorithm.
 For general input alphabets there is an O(ε^{5}√ n log^{4} n) space and O(ε^{4} log^{3} 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  LeibnizZentrum fuer Informatik, Germany 
Pages  20:120: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  LiebnizZentrum für Informatik 
Volume  55 
ISSN (Print)  18688969 
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
 School of Computer Science  Reader in Algorithm Design
 Intelligent Systems Laboratory
 Algorithms and Complexity
Person: Academic , Member, Group lead