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.2017.13
URN: urn:nbn:de:0030-drops-73206
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7320/
Go to the corresponding LIPIcs Volume Portal

Starikovskaya, Tatiana

Communication and Streaming Complexity of Approximate Pattern Matching

pdf-format:
LIPIcs-CPM-2017-13.pdf (0.4 MB)

Abstract

We consider the approximate pattern matching problem. Given a text T of length 2n and a pattern P of length n, the task is to decide for each prefix T[1, j] of T if it ends with a string that is at the edit distance at most k from P. If this is the case, we must output the edit distance and the corresponding edit operations. We first show the communication complexity of the problem for the case when Alice and Bob both share the pattern and Alice holds the first half of the text and Bob the second half, and for the case when Alice holds the first half of the text, Bob the second half of the text, and Charlie the pattern. We then develop the first sublinear-space streaming algorithm for the problem. The algorithm is randomised with error probability at most 1/poly(n).

BibTeX - Entry

@InProceedings{starikovskaya:LIPIcs:2017:7320,
  author =	{Tatiana Starikovskaya},
  title =	{{Communication and Streaming Complexity of Approximate Pattern Matching}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{13:1--13:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7320},
  URN =		{urn:nbn:de:0030-drops-73206},
  doi =		{10.4230/LIPIcs.CPM.2017.13},
  annote =	{Keywords: approximate pattern matching, edit distance, randomised algorithms, streaming algorithms, communication complexity}
}

Keywords: approximate pattern matching, edit distance, randomised algorithms, streaming algorithms, communication complexity
Collection: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 30.06.2017

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