Ghosh, Prantar
New Verification Schemes for FrequencyBased Functions on Data Streams
Abstract
We study the general problem of computing frequencybased functions, i.e., the sum of any given function of data stream frequencies. Special cases include fundamental data stream problems such as computing the number of distinct elements (F₀), frequency moments (F_k), and heavyhitters. It can also be applied to calculate the maximum frequency of an element (F_{∞}).
Given that exact computation of most of these special cases provably do not admit any sublinear space algorithm, a natural approach is to consider them in an enhanced data streaming model, where we have a computationally unbounded but untrusted prover that can send proofs or help messages to ease the computation. Think of a memoryrestricted client delegating the computation to a powerful cloud service. The client does not blindly trust the cloud, and with its limited memory, it wants to verify the proof that the cloud sends. Chakrabarti et al. (ICALP '09) introduced this model as the annotated data streaming model and showed that multiple problems including exact computation of frequencybased functions  that have no sublinear algorithms in basic streaming  do have algorithms, also called schemes, in the annotated streaming model with both space and prooflength sublinear in the input size.
We give a general scheme for computing any frequencybased function with both space usage and proofsize of O(n^{2/3}log n) bits, where n is the size of the universe. This improves upon the best known bound of O(n^{2/3}log^{4/3} n) given by the seminal paper of Chakrabarti et al. and as a result, also improves upon the best known bounds for the important special cases of computing F₀ and F_{∞}. We emphasize that while being quantitatively better, our scheme is also qualitatively better in the sense that it is simpler than the previously best scheme that uses intricate data structures and elaborate subroutines. Our scheme uses a simple technique tailored for this model: the verifier solves the problem partially by running an algorithm known to be helpful for it in the basic (sans prover) streaming model and then takes the prover’s help to solve the remaining part.
BibTeX  Entry
@InProceedings{ghosh:LIPIcs:2020:13263,
author = {Prantar Ghosh},
title = {{New Verification Schemes for FrequencyBased Functions on Data Streams}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {22:122:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771740},
ISSN = {18688969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13263},
URN = {urn:nbn:de:0030drops132631},
doi = {10.4230/LIPIcs.FSTTCS.2020.22},
annote = {Keywords: data streams, interactive proofs, ArthurMerlin}
}
04.12.2020
Keywords: 

data streams, interactive proofs, ArthurMerlin 
Seminar: 

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 