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 dnearpalindrome} is a string of Hamming distance at most d from its reverse.
We study the natural problem of identifying the longest dnearpalindrome 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 dnearpalindrome problem that returns a dnearpalindrome whose length is within a multiplicative (1+\eps)factor of the longest dnearpalindrome.
Our algorithm also returns the set of mismatched indices in the dnearpalindrome, 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 11/n requires \Omega(d\log n) space.
We further obtain a streaming algorithm that returns a dnearpalindrome whose length is within an additive Eerror of the longest dnearpalindrome.
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 dnearpalindrome 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 twopass algorithm that solves the longest dnearpalindrome 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:131:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770552},
ISSN = {18688969},
year = {2018},
volume = {93},
editor = {Satya Lokam and R. Ramanujam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8405},
URN = {urn:nbn:de:0030drops84053},
doi = {10.4230/LIPIcs.FSTTCS.2017.31},
annote = {Keywords: Longest palindrome with mismatches, Streaming algorithms, Hamming distance}
}
12.02.2018
Keywords: 

Longest palindrome with mismatches, Streaming algorithms, Hamming distance 
Seminar: 

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Issue date: 

2018 
Date of publication: 

12.02.2018 