Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-128 | 7th October 2012 17:46

Streaming Complexity of Checking Priority Queues

RSS-Feed




Revision #1
Authors: Nathanaël François, Frederic Magniez
Accepted on: 7th October 2012 17:46
Downloads: 694
Keywords: 


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 initiated the study of checking priority queues in this setting. They showed that use of timestamps allows to check a priority queue with a single pass and memory space $O(\sqrt{N})$, up to a polylogarithmic factor. Later, Chakrabarti, Cormode, Kondapally and McGregor 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 a previously open problem. On the other hand, we show that a second pass, but in reverse direction, shrinks the memory space to $O((\log N )^2 )$, extending a phenomenon the first time observed by Magniez, Mathieu and Nayak for checking well-parenthesized expressions.



Changes to previous version:

Minor corrections


Paper:

TR12-128 | 21st September 2012 15:43

Streaming Complexity of Checking Priority Queues





TR12-128
Authors: Nathanaël François, Frederic Magniez
Publication: 5th October 2012 16:40
Downloads: 840
Keywords: 


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 initiated the study of checking priority queues in this setting. They showed that use of timestamps allows to check a priority queue with a single pass and memory space $O(\sqrt{N})$, up to a polylogarithmic factor. Later, Chakrabarti, Cormode, Kondapally and McGregor 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 a previously open problem. On the other hand, we show that a second pass, but in reverse direction, shrinks the memory space to $O((\log N )^2 )$, extending a phenomenon the first time observed by Magniez, Mathieu and Nayak for checking well-parenthesized expressions.



ISSN 1433-8092 | Imprint