DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2019.31

Searching Long Repeats in Streams

Authors: Oleg Merkurev and Arseny M. Shur

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract

We consider two well-known related problems: Longest Repeated Substring (LRS) and Longest Repeated Reversed Substring (LRRS). Their streaming versions cannot be solved exactly; we show that only approximate solutions by Monte Carlo algorithms are possible, and prove a lower bound on consumed memory. For both problems, we present purely linear-time Monte Carlo algorithms working in O(E + n/E) space, where E is the additive approximation error. Within the same space bounds, we then present nearly real-time solutions, which require O(log n) time per symbol and O(n + n/E log n) time overall. The working space exactly matches the lower bound whenever E=O(n^{0.5}) and the size of the alphabet is Omega(n^{0.01}).

Cite as

Oleg Merkurev and Arseny M. Shur. Searching Long Repeats in Streams. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{merkurev_et_al:LIPIcs.CPM.2019.31,
  author =	{Merkurev, Oleg and Shur, Arseny M.},
  title =	{{Searching Long Repeats in Streams}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.31},
  URN =		{urn:nbn:de:0030-drops-105029},
  doi =		{10.4230/LIPIcs.CPM.2019.31},
  annote =	{Keywords: Longest repeated substring, longest repeated reversed substring, streaming algorithm, Karp, Rabin fingerprint, suffix tree}
}

Document

DOI: 10.4230/LIPIcs.CPM.2016.18

Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams

Authors: Pawel Gawrychowski, Oleg Merkurev, Arseny Shur, and Przemyslaw Uznanski

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract

We consider computing a longest palindrome in the streaming model, where the symbols arrive one-by-one and we do not have random access to the input. While computing the answer exactly using sublinear space is not possible in such a setting, one can still hope for a good approximation guarantee. Our contribution is twofold. First, we provide lower bounds on the space requirements for randomized approximation algorithms processing inputs of length n. We rule out Las Vegas algorithms, as they cannot achieve sublinear space complexity. For Monte Carlo algorithms, we prove a lower bounds of Omega(M log min {|Sigma|, M}) bits of memory; here M=n/E for approximating the answer with additive error E, and M= log n / log (1 + epsilon) for approximating the answer with multiplicative error (1 + epsilon). Second, we design three real-time algorithms for this problem. Our Monte Carlo approximation algorithms for both additive and multiplicative versions of the problem use O(M) words of memory. Thus the obtained lower bounds are asymptotically tight up to a logarithmic factor. The third algorithm is deterministic and finds a longest palindrome exactly if it is short. This algorithm can be run in parallel with a Monte Carlo algorithm to obtain better results in practice. Overall, both the time and space complexity of finding a longest palindrome in a stream are essentially settled.

Cite as

Pawel Gawrychowski, Oleg Merkurev, Arseny Shur, and Przemyslaw Uznanski. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2016.18,
  author =	{Gawrychowski, Pawel and Merkurev, Oleg and Shur, Arseny and Uznanski, Przemyslaw},
  title =	{{Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.18},
  URN =		{urn:nbn:de:0030-drops-60765},
  doi =		{10.4230/LIPIcs.CPM.2016.18},
  annote =	{Keywords: streaming algorithms, space lower bounds, real-time algorithms, palin- dromes, Monte Carlo algorithms}
}

Search Results

Documents authored by Merkurev, Oleg

Searching Long Repeats in Streams

Abstract

Cite as

Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams

Abstract

Cite as

Thanks for your feedback!

Could not send message