License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.9
URN: urn:nbn:de:0030-drops-73379
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7337/
Go to the corresponding LIPIcs Volume Portal


Grossi, Roberto ; Iliopoulos, Costas S. ; Liu, Chang ; Pisanti, Nadia ; Pissis, Solon P. ; Retha, Ahmad ; Rosone, Giovanna ; Vayani, Fatima ; Versari, Luca

On-Line Pattern Matching on Similar Texts

pdf-format:
LIPIcs-CPM-2017-9.pdf (0.8 MB)


Abstract

Pattern matching on a set of similar texts has received much attention, especially recently, mainly due to its application in cataloguing human genetic variation. In particular, many different algorithms have been proposed for the off-line version of this problem; that is, constructing a compressed index for a set of similar texts in order to answer pattern matching queries efficiently. However, the on-line, more fundamental, version of this problem is a rather undeveloped topic. Solutions to the on-line version can be beneficial for a number of reasons; for instance, efficient on-line solutions can be used in combination with partial indexes as practical trade-offs. We make here an attempt to close this gap via proposing two efficient algorithms for this problem. Notably, one of the algorithms requires time linear in the size of the texts' representation, for short patterns. Furthermore, experimental results confirm our theoretical findings in practical terms.

BibTeX - Entry

@InProceedings{grossi_et_al:LIPIcs:2017:7337,
  author =	{Roberto Grossi and Costas S. Iliopoulos and Chang Liu and Nadia Pisanti and Solon P. Pissis and Ahmad Retha and Giovanna Rosone and Fatima Vayani and Luca Versari},
  title =	{{On-Line Pattern Matching on Similar Texts}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{9:1--9:14},
  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/7337},
  URN =		{urn:nbn:de:0030-drops-73379},
  doi =		{10.4230/LIPIcs.CPM.2017.9},
  annote =	{Keywords: string algorithms, pattern matching, degenerate strings, elastic-degenerate strings, on-line algorithms}
}

Keywords: string algorithms, pattern matching, degenerate strings, elastic-degenerate strings, on-line algorithms
Seminar: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 28.06.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI