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.APPROX/RANDOM.2020.35
URN: urn:nbn:de:0030-drops-126381
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12638/
Starikovskaya, Tatiana ;
Svagerka, Michal ;
Uznański, Przemysław
L_p Pattern Matching in a Stream
Abstract
We consider the problem of computing distance between a pattern of length n and all n-length subwords of a text in the streaming model.
In the streaming setting, only the Hamming distance (L₀) has been studied. It is known that computing the exact Hamming distance between a pattern and a streaming text requires Ω(n) space (folklore). Therefore, to develop sublinear-space solutions, one must relax their requirements. One possibility to do so is to compute only the distances bounded by a threshold k, see [SODA'19, Clifford, Kociumaka, Porat] and references therein. The motivation for this variant of this problem is that we are interested in subwords of the text that are similar to the pattern, i.e. in subwords such that the distance between them and the pattern is relatively small.
On the other hand, the main application of the streaming setting is processing large-scale data, such as biological data. Recent advances in hardware technology allow generating such data at a very high speed, but unfortunately, the produced data may contain about 10% of noise [Biol. Direct.'07, Klebanov and Yakovlev]. To analyse such data, it is not sufficient to consider small distances only. A possible workaround for this issue is the (1±ε)-approximation. This line of research was initiated in [ICALP'16, Clifford and Starikovskaya] who gave a (1±ε)-approximation algorithm with space ?~(ε^{-5}√n).
In this work, we show a suite of new streaming algorithms for computing the Hamming, L₁, L₂ and general L_p (0 < p < 2) distances between the pattern and the text. Our results significantly extend over the previous result in this setting. In particular, for the Hamming distance and for the L_p distance when 0 < p ≤ 1 we show a streaming algorithm that uses ?~(ε^{-2}√n) space for polynomial-size alphabets.
BibTeX - Entry
@InProceedings{starikovskaya_et_al:LIPIcs:2020:12638,
author = {Tatiana Starikovskaya and Michal Svagerka and Przemys{\l}aw Uznański},
title = {{L_p Pattern Matching in a Stream}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {35:1--35:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12638},
URN = {urn:nbn:de:0030-drops-126381},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.35},
annote = {Keywords: streaming algorithms, approximate pattern matching}
}
|
Keywords: |
|
streaming algorithms, approximate pattern matching |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.08.2020 |
