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.APPROX-RANDOM.2014.654
URN: urn:nbn:de:0030-drops-47298
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4729/
Go to the corresponding LIPIcs Volume Portal

François, Nathanaël ; Jain, Rahul ; Magniez, Frédéric

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting

pdf-format:
46.pdf (0.5 MB)

Abstract

We consider unidirectional data streams with restricted access, such as read-only and write-only streams. For read-write streams, we also
introduce a new complexity measure called expansion, the ratio between
the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length n in several of the possible models. In the read-only and write-only model, we show that p-pass algorithms need memory space Theta(n/p). But if either the output stream or the input stream is read-write, then the complexity falls to Theta(n/p^2). It becomes polylog(n) if p = O(log n) and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has O(1) expansion, O(log n) passes and O(log n) memory.

BibTeX - Entry

@InProceedings{franois_et_al:LIPIcs:2014:4729,
  author =	{Nathana{\"e}l Fran{\c{c}}ois and Rahul Jain and Fr{\'e}d{\'e}ric Magniez},
  title =	{{Unidirectional Input/Output Streaming Complexity of Reversal and Sorting}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{654--668},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4729},
  URN =		{urn:nbn:de:0030-drops-47298},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.654},
  annote =	{Keywords: Streaming Algorithms, Multiple Streams, Reversal, Sorting}
}

Keywords: Streaming Algorithms, Multiple Streams, Reversal, Sorting
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI