文章基本信息

标题：The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time
本地全文：下载
作者：Shay Golan ; Tomasz Kociumaka ; Tsvi Kopelowitz 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：161
页码：15:1-15:15
DOI：10.4230/LIPIcs.CPM.2020.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We revisit the k-mismatch problem in the streaming model on a pattern of length m and a streaming text of length n, both over a size-Ïf alphabet. The current state-of-the-art algorithm for the streaming k-mismatch problem, by Clifford et al. [SODA 2019], uses OÌf(k) space and OÌf(â^Sk) worst-case time per character. The space complexity is known to be (unconditionally) optimal, and the worst-case time per character matches a conditional lower bound. However, there is a gap between the total time cost of the algorithm, which is OÌf(nâ^Sk), and the fastest known offline algorithm, which costs OÌf(n + min(nk/â^Sm, Ïfn)) time. Moreover, it is not known whether improvements over the OÌf(nâ^Sk) total time are possible when using more than O(k) space. We address these gaps by designing a randomized streaming algorithm for the k-mismatch problem that, given an integer parameter kâ¤sâ¤m, uses Ã.(s) space and costs Ã.(n+min(nkÂ²/m, nk/â^Ss, Ïfnm/s)) total time. For s=m, the total runtime becomes OÌf(n + min(nk/â^Sm, Ïfn)), which matches the time cost of the fastest offline algorithm. Moreover, the worst-case time cost per character is still Ã.(â^Sk).
关键词：Streaming pattern matching; Hamming distance; k-mismatch