论文标题
用于数据流的基于频率功能的新验证方案
New Verification Schemes for Frequency-Based Functions on Data Streams
论文作者
论文摘要
我们研究基于计算频率函数的一般问题，即数据流频率的任何给定功能的总和。特殊案例包括基本数据流问题，例如计算不同元素（$ f_0 $），频率矩（$ f_k $）和重型企业的数量。它也可以应用于计算元素（$ f _ {\ infty} $）的最大频率。 鉴于大多数这些特殊情况的精确计算证明不承认任何均方根空间算法，因此一种自然的方法是在增强的数据流模型中考虑它们，在该模型中，我们有一个计算上没有绑定但不受欢迎的供体发送证明或帮助消息来减轻计算的信息。想想一个由内存限制的客户端将计算委派给了不想盲目信任的更强大的云服务。使用其有限的内存，它希望验证云发送的证据。 Chakrabarti et al.~(ICALP '09) introduced this setting as the "annotated data streaming model" and showed that multiple problems including exact computation of frequency-based functions---that have no sublinear algorithms in basic streaming---do have annotated streaming algorithms, also called "schemes", with both space and proof-length sublinear in the input size. 我们提供了一个通用方案，用于计算任何基于频率的功能，并具有$ o（n^{2/3} \ log n）$位的空间用法和证明大小，其中$ n $是宇宙的大小。这在Chakrabarti等人的开创性论文中给出的$ O（N^{2/3} \ log^{4/3} n）$的最著名界限有所改善，结果，也可以根据计算$ f_0 $和$ f _ {\ infty的重要特殊案例的最佳特殊案例。我们强调的是，虽然量化更好，但我们的方案在质量上也更好，因为它比使用复杂的数据结构和精心制作的子例程的先前最佳方案更简单。
We study the general problem of computing frequency-based 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_0$), frequency moments ($F_k$), and heavy-hitters. It can also be applied to calculate the maximum frequency of an element ($F_{\infty}$). 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 sending proofs or help messages to ease the computation. Think of a memory-restricted client delegating the computation to a stronger cloud service whom it doesn't want to trust blindly. Using its limited memory, it wants to verify the proof that the cloud sends. Chakrabarti et al.~(ICALP '09) introduced this setting as the "annotated data streaming model" and showed that multiple problems including exact computation of frequency-based functions---that have no sublinear algorithms in basic streaming---do have annotated streaming algorithms, also called "schemes", with both space and proof-length sublinear in the input size. We give a general scheme for computing any frequency-based function with both space usage and proof-size 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_0$ and $F_{\infty}$. 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.
