We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical @math streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it. As an application, we give an @math streaming algorithm for the problem. Given a data stream of length @math over alphabet of size @math , the algorithm uses @math space and a proof of size @math , for every @math such that @math (where @math hides a @math factor). We also prove a lower bound, showing that every @math streaming algorithm for the problem that uses @math bits of space and a proof of size @math , satisfies @math . As a part of the proof of the lower bound for the problem, we show a new lower bound of @math on the @math communication complexity of the problem, and prove its tightness.
The data stream model has gained a great deal of attention after the publication of the seminal paper by Alon, Matias and Szegedy @cite_9 . In the scope of that work, the authors have shown a lower bound of @math (where @math is the size of the alphabet) on the streaming complexity of (i.e., the computation of the number of distinct elements in a data stream) where the length of the input is at least proportional to @math .
@cite_9
2165753192 2002576896 2132588842 2963274201
We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. In this model, the input graph, G = (V, E), is presented as a stream of edges (in adversarial order), and the storage space of an algorithm is bounded by O(n ċ polylog n), where n = |V|. We are particularly interested in algorithms that use only one pass over the input, but, for problems where this is provably insufficient, we also look at algorithms using constant or, in some cases, logarithmically many passes. In the course of this general study, we give semi-streaming constant approximation algorithms for the unweighted and weighted matching problems, along with a further algorithmic improvement for the bipartite case. We also exhibit log n log log n semi-streaming approximations to the diameter and the problem of computing the distance between specified vertices in a weighted graph. These are complemented by Ω(log(1-e) n) lower bounds. We introduce reductions in the streaming model as a tool in the design of streaming algorithms. We develop the concept of list-efficient streaming algorithms that are essential to the design of efficient streaming algorithms through reductions.Our results include a suite of list-efficient streaming algorithms for basic statistical primitives. Using the reduction paradigm along with these tools, we design streaming algorithms for approximately counting the number of triangles in a graph presented as a stream.A specific highlight of our work is the first algorithm for the number of distinct elements in a data stream that achieves arbitrary approximation factors. (Independently, Trevisan [Tre01] has solved this problem via a different approach; our algorithm has the advantage of being list-efficient.) The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage of such algorithms be further reduced by enlisting a more powerful "helper" who can annotate the stream as it is read. We do not wish to blindly trust the helper, so we require that the algorithm be convinced of having computed a correct answer. We show upper bounds that achieve a non-trivial tradeoff between the amount of annotation used and the space required to verify it. We also prove lower bounds on such tradeoffs, often nearly matching the upper bounds, via notions related to Merlin-Arthur communication complexity. Our results cover the classic data stream problems of selection, frequency moments, and fundamental graph problems such as triangle-freeness and connectivity. Our work is also part of a growing trend -- including recent studies of multi-pass streaming, read write streams and randomly ordered streams -- of asking more complexity-theoretic questions about data stream processing. It is a recognition that, in addition to practical relevance, the data stream model raises many interesting theoretical questions in its own right. This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An e approximate quantile sketch receives a stream of items x1,·,xn and allows one to approximate the rank of any query item up to additive error e n with probability at least 1-δ.The rank of a query x is the number of stream items such that xi ≤ x. The minimal sketch size required for this task is trivially at least 1 e.Felber and Ostrovsky obtain a O((1 e)log(1 e)) space sketch for a fixed δ.Without restrictions on the nature of the stream or the ratio between e and n, no better upper or lower bounds were known to date. This paper obtains an O((1 e)log log (1 δ)) space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching for which an Ω((1 e)log(1 e)) lower bound is known. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This modification allows for an analysis which is both tight and extremely simple. The same technique was reported, in private communications, to be useful for improving other sketching objectives and geometric coreset constructions.