Approximating Longest Common Substring with k mismatches: Theory and Practice

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

doi:10.4230/LIPIcs.CPM.2020.16

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: https://drops.dagstuhl.de/opus/volltexte/2020/12141/

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}
}

09.06.2020

Keywords: approximation algorithms, string similarity, LSH, conditional lower bounds

Seminar: 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.

Keywords:		approximation algorithms, string similarity, LSH, conditional lower bounds
Seminar:		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.