## A. Chakrabarti, G. Cormode, N. Goyal, and J. Thaler.
Annotations for sparse data streams.
In *ACM-SIAM Symposium on Discrete Algorithms (SODA)*,
2014.

Motivated by the surging popularity of commercial cloud computing services, a
number of recent works have studied *annotated data streams* and variants
thereof.
In this setting, a computationally weak *verifier* (cloud user), lacking
the resources to store and manipulate his massive input locally, accesses a
powerful but untrusted *prover* (cloud service). The verifier must work
within the restrictive data streaming paradigm. The prover, who can
*annotate* the data stream as it is read, must not just supply the final
answer but also convince the verifier of its correctness. Ideally, both the amount
of annotation from the prover and the space used by the verifier should be
sublinear in the relevant input size parameters.
A rich theory of such algorithms-which we call *schemes*-has started
to emerge. Prior work has shown how to leverage the prover's power to
efficiently solve problems that have no non-trivial standard data stream
algorithms. However, even though optimal schemes are now known for several
basic problems, such optimality holds only for streams whose length is commensurate with the
size of the *data universe*. In contrast, many real-world data sets are
relatively *sparse*, including graphs that contain only *o*(*n*^{2}) edges, and IP
traffic streams that contain much fewer than the total number of possible IP
addresses, 2^{128} in IPv6.
Here we design the first annotation schemes that allow both the annotation and
the space usage to be sublinear in the total number of stream *updates*
rather than the size of the data universe. We solve significant problems,
including variations of INDEX, set-disjointness, and
frequency-moments, plus several natural problems on graphs. On the
other hand, we give a new lower bound that, for the first time, rules out
smooth tradeoffs between annotation and space usage for a specific problem.
Our technique brings out new nuances in Merlin-Arthur communication
complexity models, and provides a separation between online versions of the MA
and AMA models.

[ bib |
Alternate Version |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*