Document Open Access Logo

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.654.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Nathanaël François, Rahul Jain, and Frédéric Magniez. Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 654-668, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.654

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.

Subject Classification

Keywords
  • Streaming Algorithms
  • Multiple Streams
  • Reversal
  • Sorting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alok Aggarwal and Jeffrey Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, 1988. Google Scholar
  2. Paul Beame and Trinh Huynh. The value of multiple read/write streams for approximating frequency moments. ACM Transactions on Computation Theory, 3(2):6, 2012. Google Scholar
  3. Paul Beame, T.S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms. In Proceedings of the 39th annual ACM symposium on Theory of computing, pages 689-698, 2007. Google Scholar
  4. Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor. Information cost tradeoffs for augmented index and streaming language recognition. SIAM Journal on Computing, 42(1):61-83, 2013. Google Scholar
  5. Jianer Chen and Chee-Keng Yap. Reversal complexity. SIAM Journal on Computing, 20(4):622-638, 1991. Google Scholar
  6. Nathanaël François and Frédéric Magniez. Streaming complexity of checking priority queues. In Proceeding of the 30th International Symposium on Theoretical Aspects of Computer Science, page 454. Citeseer, 2013. Google Scholar
  7. Travis Gagie. On the value of multiple read/write streams for data compression. In Information Theory, Combinatorics, and Search Theory, pages 284-297. Springer, 2013. Google Scholar
  8. Martin Grohe, André Hernich, and Nicole Schweikardt. Lower bounds for processing data with few random accesses to external memory. Journal of the ACM, 56(3):12, 2009. Google Scholar
  9. Martin Grohe, Christoph Koch, and Nicole Schweikardt. Tight lower bounds for query processing on streaming and external memory data. Theoretical Computer Science, 380(1):199-217, 2007. Google Scholar
  10. André Hernich and Nicole Schweikardt. Reversal complexity revisited. Theoretical Computer Science, 401(1):191-205, 2008. Google Scholar
  11. Rahul Jain and Ashwin Nayak. The space complexity of recognizing well-parenthesized expressions. Technical Report 71, Electronic Colloquium on Computational Complexity, 2010. Google Scholar
  12. Tiko Kameda and Roland Vollmar. Note on tape reversal complexity of languages. Information and Control, 17(2):203-215, 1970. Google Scholar
  13. Christian Konrad and Frédéric Magniez. Validating xml documents in the streaming model with external memory. ACM Transactions on Database Systems, 38(4):27, 2013. Google Scholar
  14. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. In Proceedings of the 42nd ACM symposium on Theory of computing, pages 261-270, 2010. Google Scholar
  15. James I. Munro and Mike S. Paterson. Selection and sorting with limited storage. Theoretical computer science, 12(3):315-323, 1980. Google Scholar
  16. S. Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005. Google Scholar
  17. Jan Matthias Ruhl. Efficient algorithms for new computational models. PhD thesis, Citeseer, 2003. Google Scholar
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