License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2019.21
URN: urn:nbn:de:0030-drops-104925
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10492/
Go to the corresponding LIPIcs Volume Portal

Gawrychowski, Pawel ; Starikovskaya, Tatiana

Streaming Dictionary Matching with Mismatches

pdf-format:
LIPIcs-CPM-2019-21.pdf (0.4 MB)

Abstract

In the k-mismatch problem we are given a pattern of length m and a text and must find all locations where the Hamming distance between the pattern and the text is at most k. A series of recent breakthroughs have resulted in an ultra-efficient streaming algorithm for this problem that requires only O(k log m/k) space [Clifford, Kociumaka, Porat, SODA 2019]. In this work, we consider a strictly harder problem called dictionary matching with k mismatches, where we are given a dictionary of d patterns of lengths at most m and must find all their k-mismatch occurrences in the text, and show the first streaming algorithm for it. The algorithm uses O(k d log^k d polylog m) space and processes each position of the text in O(k log^k d polylog m + occ) time, where occ is the number of k-mismatch occurrences of the patterns that end at this position. The algorithm is randomised and outputs correct answers with high probability.

BibTeX - Entry

@InProceedings{gawrychowski_et_al:LIPIcs:2019:10492,
  author =	{Pawel Gawrychowski and Tatiana Starikovskaya},
  title =	{{Streaming Dictionary Matching with Mismatches}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Nadia Pisanti and Solon P. Pissis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10492},
  URN =		{urn:nbn:de:0030-drops-104925},
  doi =		{10.4230/LIPIcs.CPM.2019.21},
  annote =	{Keywords: Streaming, multiple pattern matching, Hamming distance}
}

Keywords: Streaming, multiple pattern matching, Hamming distance
Collection: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Issue Date: 2019
Date of publication: 06.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI