Lp Pattern Matching in a Stream
dc.contributor.author
Starikovskaya, Tatiana
dc.contributor.author
Svagerka, Michal
dc.contributor.author
Uznanski, Przemyslaw
dc.contributor.editor
Byrka, Jaroslaw
dc.contributor.editor
Meka, Raghu
dc.date.accessioned
2020-10-13T07:30:54Z
dc.date.available
2020-09-28T02:46:12Z
dc.date.available
2020-10-06T07:27:42Z
dc.date.available
2020-10-13T07:17:50Z
dc.date.available
2020-10-13T07:19:07Z
dc.date.available
2020-10-13T07:30:54Z
dc.date.issued
2020
dc.identifier.isbn
978-3-95977-164-1
en_US
dc.identifier.other
10.4230/LIPIcs.APPROX/RANDOM.2020.35
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/442917
dc.identifier.doi
10.3929/ethz-b-000442917
dc.description.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 (L0) 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 Oe(ε−5 √n). In this work, we show a suite of new streaming algorithms for computing the Hamming, L1, L2 and general Lp (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 Lp distance when 0 < p ≤ 1 we show a streaming algorithm that uses Oe(ε−2 √n) space for polynomial-size alphabets.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
streaming algorithms
en_US
dc.subject
approximate pattern matching
en_US
dc.title
Lp Pattern Matching in a Stream
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
dc.date.published
2020-08-11
ethz.book.title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
en_US
ethz.journal.volume
176
en_US
ethz.pages.start
APPROX35
en_US
ethz.size
23 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) (virtual)
en_US
ethz.event.date
August 17-19, 2020
en_US
ethz.notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2020-09-28T02:46:17Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2020-10-06T07:28:01Z
ethz.rosetta.lastUpdated
2024-02-02T12:17:51Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Lp%20Pattern%20Matching%20in%20a%20Stream&rft.date=2020&rft.volume=176&rft.spage=APPROX35&rft.au=Starikovskaya,%20Tatiana&Svagerka,%20Michal&Uznanski,%20Przemyslaw&rft.isbn=978-3-95977-164-1&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.APPROX/RANDOM.2020.35&rft.btitle=Approximation,%20Randomization,%20and%20Combinatorial%20Optimization.%20Algorithms%20and%20Techniques%20(APPROX/RANDOM%202020)
Files in this item
Publication type
-
Conference Paper [34930]