Search Results

Documents authored by Sadeqi Azer, Erfan

Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.31
Streaming for Aibohphobes: Longest Palindrome with Mismatches

Authors: Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

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.
Cite as

Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou. Streaming for Aibohphobes: Longest Palindrome with Mismatches. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grigorescu_et_al:LIPIcs.FSTTCS.2017.31,
  author =	{Grigorescu, Elena and Sadeqi Azer, Erfan and Zhou, Samson},
  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 =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.31},
  URN =		{urn:nbn:de:0030-drops-84053},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.31},
  annote =	{Keywords: Longest palindrome with mismatches, Streaming algorithms, Hamming distance}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.42
Streaming Periodicity with Mismatches

Authors: Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We study the problem of finding all k-periods of a length-n string S, presented as a data stream. S is said to have k-period p if its prefix of length n-p differs from its suffix of length n-p in at most k locations. We give a one-pass streaming algorithm that computes the k-periods of a string S using poly(k, log n) bits of space, for k-periods of length at most n/2. We also present a two-pass streaming algorithm that computes k-periods of S using poly(k, log n) bits of space, regardless of period length. We complement these results with comparable lower bounds.
Cite as

Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou. Streaming Periodicity with Mismatches. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 42:1-42:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ergun_et_al:LIPIcs.APPROX-RANDOM.2017.42,
  author =	{Erg\"{u}n, Funda and Grigorescu, Elena and Sadeqi Azer, Erfan and Zhou, Samson},
  title =	{{Streaming Periodicity with Mismatches}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{42:1--42:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.42},
  URN =		{urn:nbn:de:0030-drops-75911},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.42},
  annote =	{Keywords: String algorithms, Streaming algorithms, Pattern matching, Randomized algorithms, Sublinear algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.149
Palindrome Recognition In The Streaming Model

Authors: Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, and Erfan Sadeqi Azer

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
A palindrome is defined as a string which reads forwards the same as backwards, like, for example, the string "racecar". In the Palindrome Problem, one tries to find all palindromes in a given string. In contrast, in the case of the Longest Palindromic Substring Problem, the goal is to find an arbitrary one of the longest palindromes in the string. In this paper we present three algorithms in the streaming model for the the above problems, where at any point in time we are only allowed to use sublinear space. We first present a one-pass randomized algorithm that solves the Palindrome Problem. It has an additive error and uses square root of n space. We also give two variants of the algorithm which solve related and practical problems. The second algorithm determines the exact locations of all longest palindromes using two passes and square root of n space. The third algorithm is a one-pass randomized algorithm, which solves the Longest Palindromic Substring Problem. It has a multiplicative error using only O(log(n)) space.
Cite as

Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, and Erfan Sadeqi Azer. Palindrome Recognition In The Streaming Model. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 149-161, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:LIPIcs.STACS.2014.149,
  author =	{Berenbrink, Petra and Erg\"{u}n, Funda and Mallmann-Trenn, Frederik and Sadeqi Azer, Erfan},
  title =	{{Palindrome Recognition In The Streaming Model}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{149--161},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.149},
  URN =		{urn:nbn:de:0030-drops-44544},
  doi =		{10.4230/LIPIcs.STACS.2014.149},
  annote =	{Keywords: Palindromes, Streaming Model, Complementary Palindrome}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact