The streaming k-mismatch problem

DOI10.1137/1.9781611975482.68MaRDI QIDQ5236252zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Tomasz Kociumaka, Ely Porat

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.05223

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Abstract: We consider the streaming complexity of a fundamental task in approximate pattern matching: the $k$-mismatch problem. It asks to compute Hamming distances between a pattern of length $n$ and all length-$n$ substrings of a text for which the Hamming distance does not exceed a given threshold $k$. In our problem formulation, we report not only the Hamming distance but also, on demand, the full emph{mismatch information}, that is the list of mismatched pairs of symbols and their indices. The twin challenges of streaming pattern matching derive from the need both to achieve small working space and also to guarantee that every arriving input symbol is processed quickly. We present a streaming algorithm for the $k$-mismatch problem which uses $O(klognlogfracnk)$ bits of space and spends ourcomplexity time on each symbol of the input stream, which consists of the pattern followed by the text. The running time almost matches the classic offline solution and the space usage is within a logarithmic factor of optimal. Our new algorithm therefore effectively resolves and also extends an open problem first posed in FOCS'09. En route to this solution, we also give a deterministic $O(k(logfracnk+log|Sigma|))$-bit encoding of all the alignments with Hamming distance at most $k$ of a length-$n$ pattern within a text of length $O(n)$. This secondary result provides an optimal solution to a natural communication complexity problem which may be of independent interest.

Recommendations

• The \(k\)-mismatch problem revisited
• Streaming \(k\)-mismatch with error correcting and applications
• Pattern matching in multiple streams
• Streaming periodicity with mismatches
• Communication and Streaming Complexity of Approximate Pattern Matching

Cited in

(23)

• Streaming pattern matching with \(d\) wildcards
• Recent advances in text-to-pattern distance algorithms
• Streaming dictionary matching with mismatches
• Streaming \(k\)-mismatch with error correcting and applications
• Pattern matching in multiple streams
• scientific article; zbMATH DE number 6678937 (Why is no real title available?)
• Pseudo-realtime pattern matching: closing the gap
• The \(k\)-mismatch problem revisited
• Approximate Hamming distance in a stream
• Streaming periodicity with mismatches
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Streaming Dictionary Matching with Mismatches
• Searching Long Repeats in Streams
• Approximate Maximum Matching in Random Streams
• scientific article; zbMATH DE number 7651106 (Why is no real title available?)
• Circular pattern matching with \(k\) mismatches
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Locally consistent decomposition of strings with applications to edit distance sketching
• Substring complexity in sublinear space
• Small-space algorithms for the online language distance problem for palindromes and squares
• Regular languages in the sliding window model
• Streaming periodicity with mismatches, wildcards, and edits

This page was built for publication: The streaming \(k\)-mismatch problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236252)