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.FSTTCS.2017.31
URN: urn:nbn:de:0030-drops-84053
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8405/
Grigorescu, Elena ;
Sadeqi Azer, Erfan ;
Zhou, Samson
Streaming for Aibohphobes: Longest Palindrome with Mismatches
Abstract
A palindrome is a string that reads the same as its reverse, such as "aibohphobia" (fear of palindromes).
Given a metric and an integer d>0, a d-near-palindrome} is a string of Hamming distance at most d from its reverse.
We study the natural problem of identifying the longest d-near-palindrome in data streams. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON.
We present the first streaming algorithm for the longest d-near-palindrome problem that returns a d-near-palindrome whose length is within a multiplicative (1+\eps)-factor of the longest d-near-palindrome.
Our algorithm also returns the set of mismatched indices in the d-near-palindrome, and uses O{\frac{d\log^7 n}{\eps\log(1+\eps)}} bits of space, and O{\frac{d\log^6 n}{\eps\log(1+\eps)}} update time per arrival symbol.
We show that for d=o(\sqrt{n}), any randomized algorithm with multiplicative approximation (1+\eps) that succeeds with probability at least 1-1/n requires \Omega(d\log n) space.
We further obtain a streaming algorithm that returns a d-near-palindrome whose length is within an additive E-error of the longest d-near-palindrome.
The algorithm uses O{\frac{dn\log^6 n}{E}} bits of space and O{\frac{dn\log^5 n}{E}} update time. As before, we show that any randomized streaming algorithm that solves the longest d-near-palindrome problem for additive error E with probability at least 1-\frac{1}{n}, uses \Omega\left(\frac{dn}{E}\right) space.
Finally, we give an exact two-pass algorithm that solves the longest d-near-palindrome problem using O{d^2\sqrt{n}\log^6 n} bits of space.
BibTeX - Entry
@InProceedings{grigorescu_et_al:LIPIcs:2018:8405,
author = {Elena Grigorescu and Erfan Sadeqi Azer and Samson Zhou},
title = {{Streaming for Aibohphobes: Longest Palindrome with Mismatches}},
booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
pages = {31:1--31:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-055-2},
ISSN = {1868-8969},
year = {2018},
volume = {93},
editor = {Satya Lokam and R. Ramanujam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8405},
URN = {urn:nbn:de:0030-drops-84053},
doi = {10.4230/LIPIcs.FSTTCS.2017.31},
annote = {Keywords: Longest palindrome with mismatches, Streaming algorithms, Hamming distance}
}
|
Keywords: |
|
Longest palindrome with mismatches, Streaming algorithms, Hamming distance |
|
Collection: |
|
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
12.02.2018 |
