Unidirectional input/output streaming complexity of reversal and sorting

DOI10.4230/LIPICS.APPROX-RANDOM.2014.654MaRDI QIDQ2969653zbMATH OpenOpenAlexFDO

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

Publication date 22 March 2017

Full work available at URL https://arxiv.org/abs/1309.0647

zbMATH Keywords

sortingstreaming algorithmsreversalmultiple streams

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

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(logn)$ 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(logn)$ passes and $O(logn)$ memory.

Recommendations

• Sorting streamed multisets
• scientific article; zbMATH DE number 1424324
• scientific article; zbMATH DE number 2079346
• The streaming complexity of cycle counting, sorting by reversals, and other problems
• Streaming Algorithms Measured in Terms of the Computed Quantity

Cited in

(1)

• A one pass streaming algorithm for finding Euler tours

This page was built for publication: Unidirectional input/output streaming complexity of reversal and sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969653)