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

Uznański, Przemysław

Approximating Text-To-Pattern Distance via Dimensionality Reduction

pdf-format:
LIPIcs-CPM-2020-29.pdf (0.5 MB)

Abstract

Text-to-pattern distance is a fundamental problem in string matching, where given a pattern of length m and a text of length n, over an integer alphabet, we are asked to compute the distance between pattern and the text at every location. The distance function can be e.g. Hamming distance or ?_p distance for some parameter p > 0. Almost all state-of-the-art exact and approximate algorithms developed in the past ∼ 40 years were using FFT as a black-box. In this work we present ?~(n/ε²) time algorithms for (1±ε)-approximation of ?₂ distances, and ?~(n/ε³) algorithm for approximation of Hamming and ?₁ distances, all without use of FFT. This is independent to the very recent development by Chan et al. [STOC 2020], where ?(n/ε²) algorithm for Hamming distances not using FFT was presented - although their algorithm is much more "combinatorial", our techniques apply to other norms than Hamming.

BibTeX - Entry

@InProceedings{uznaski:LIPIcs:2020:12154,
  author =	{Przemysław Uznański},
  title =	{{Approximating Text-To-Pattern Distance via Dimensionality Reduction}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{29:1--29:11},
  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/12154},
  URN =		{urn:nbn:de:0030-drops-121542},
  doi =		{10.4230/LIPIcs.CPM.2020.29},
  annote =	{Keywords: Approximate Pattern Matching, ?₂ Distance, ?₁ Distance, Hamming Distance, Approximation Algorithms, Combinatorial Algorithms}
}

Keywords: Approximate Pattern Matching, ?₂ Distance, ?₁ Distance, Hamming Distance, Approximation Algorithms, Combinatorial Algorithms
Collection: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Issue Date: 2020
Date of publication: 09.06.2020

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