Approximate Hamming distance in a stream

Raphael Clifford, Tatiana Starikovskaia

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

14 Citations (Scopus)
137 Downloads (Pure)

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-2log 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 languageEnglish
Title of host publication43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)
EditorsIoannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages20:1-20:14
Number of pages14
ISBN (Print)9783959770132
DOIs
Publication statusPublished - 1 Aug 2016
EventICALP ICALP 2016 Track A - Sapienza University of Rome, Rome, Italy
Duration: 12 Jul 201615 Jul 2016

Publication series

NameLiebniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Liebniz-Zentrum für Informatik
Volume55
ISSN (Print)1868-8969

Conference

ConferenceICALP ICALP 2016 Track A
CountryItaly
CityRome
Period12/07/1615/07/16

Fingerprint Dive into the research topics of 'Approximate Hamming distance in a stream'. Together they form a unique fingerprint.

Cite this