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.2020.16
URN: urn:nbn:de:0030-drops-121410
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12141/
Go to the corresponding LIPIcs Volume Portal

Gourdel, Garance ; Kociumaka, Tomasz ; Radoszewski, Jakub ; Starikovskaya, Tatiana

Approximating Longest Common Substring with k mismatches: Theory and Practice

pdf-format:
LIPIcs-CPM-2020-16.pdf (0.7 MB)

Abstract

In the problem of the longest common substring with k mismatches we are given two strings X, Y and must find the maximal length ? such that there is a length-? substring of X and a length-? substring of Y that differ in at most k positions. The length ? can be used as a robust measure of similarity between X, Y. In this work, we develop new approximation algorithms for computing ? that are significantly more efficient that previously known solutions from the theoretical point of view. Our approach is simple and practical, which we confirm via an experimental evaluation, and is probably close to optimal as we demonstrate via a conditional lower bound.

BibTeX - Entry

@InProceedings{gourdel_et_al:LIPIcs:2020:12141,
  author =	{Garance Gourdel and Tomasz Kociumaka and Jakub Radoszewski and Tatiana Starikovskaya},
  title =	{{Approximating Longest Common Substring with k mismatches: Theory and Practice}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{Inge Li G{\o}rtz and Oren Weimann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12141},
  URN =		{urn:nbn:de:0030-drops-121410},
  doi =		{10.4230/LIPIcs.CPM.2020.16},
  annote =	{Keywords: approximation algorithms, string similarity, LSH, conditional lower bounds}
}

Keywords: approximation algorithms, string similarity, LSH, conditional lower bounds
Collection: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Issue Date: 2020
Date of publication: 09.06.2020
Supplementary Material: To ensure the reproducibility of our results, our complete experimental setup, including data files, is available at https://github.com/fnareoh/LCS_Approx_k_mis.

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