License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.454
URN: urn:nbn:de:0030-drops-39561
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3956/
Go to the corresponding LIPIcs Volume Portal

Francois, Nathanael ; Magniez, Frédéric

Streaming Complexity of Checking Priority Queues

pdf-format:
44.pdf (0.7 MB)

Abstract

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure.
In a context of massive data, one would like to minimize both the amount of reliable memory of the checker and the number of passes on the sequence of operations.

Chu, Kannan and McGregor (M. Chu, S. Kannan, and A. McGregor, 2007) initiated the study of checking priority queues in this setting. They showed that the use of timestamps allows to check a priority queue with a single pass and memory space \tilde{\Order}(\sqrt{N}). Later, Chakrabarti, Cormode, Kondapally and McGregor (A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor, 2010) removed the use of timestamps, and proved that more passes do not help.

We show that, even in the presence of timestamps, more passes do not help, solving an open problem
of (M. Chu, S. Kannan, and A. McGregor, 2007; A. Chakrabarti, G. Cormode, R. Kondapally, and A. McGregor). On the other hand, we show that a second pass, but in reverse direction shrinks the memory space to \tilde{\Order}((\log N)^2), extending a phenomenon the first time observed by Magniez, Mathieu and Nayak (F. Magniez, C. Mathieu, and A. Nayak, 2010) for checking well-parenthesized expressions.

BibTeX - Entry

@InProceedings{francois_et_al:LIPIcs:2013:3956,
  author =	{Nathanael Francois and Fr{\'e}d{\'e}ric Magniez},
  title =	{{Streaming Complexity of Checking Priority Queues}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{454--465},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3956},
  URN =		{urn:nbn:de:0030-drops-39561},
  doi =		{10.4230/LIPIcs.STACS.2013.454},
  annote =	{Keywords: Streaming Algorithms, Communication Complexity, Priority Queue}
}

Keywords: Streaming Algorithms, Communication Complexity, Priority Queue
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

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