2026-07-23T18:55:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6299 2024-03-06T10:37:39Z ddc:004 open_access

Approximate Hamming Distance in a Stream Clifford, Raphaël Starikovskaya, Tatiana Hamming distance communication complexity data stream model 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raphaël Clifford and Tatiana Starikovskaya 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.20 urn:nbn:de:0030-drops-62992 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.20 eng https://creativecommons.org/licenses/by/3.0/legalcode