Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
复制标题
重新审视随机顺序流中的直和定理和空间下界
DOI：
10.1007/978-3-642-02927-1_43
复制
发表时间：
2009
期刊：
影响因子：
30.8
通讯作者：
Zhiyi Huang
中科院分区：
文献类型：
--
作者：
S. Guha;Zhiyi Huang
估计频率矩和 L p 距离是对抗性数据流模型中经过深入研究的问题，并且这两个问题的紧密空间界限是已知的。人们越来越有兴趣在随机顺序流的框架中重新审视这些问题。 Andoni等人已知的用于计算随机顺序流中的第k个频率矩的最佳空间下界是*** (n 1 *** 2.5/k )，并且推测真正的下界应为*** (n 1 *** 2/k )。在本文中，我们解决了这个猜想。在我们的方法中，我们重新审视了 Bar-Yossef 等人提出的直和定理。在随机分区私人消息模型中，并为任何将随机顺序流模型中的频率矩近似为常数因子的 *** 通算法提供严格的 *** (n 1 *** 2/k /***) 空间下界。最后，我们还引入了随机顺序流中空间熵权衡的概念，作为研究对抗性和完全随机顺序流之间的中间模型的一种手段。我们展示了 L *** 距离的几乎紧密的空间熵权衡和 L p 距离的不平凡的权衡。
Estimating frequency moments and L p distances are well studied problems in the adversarial data stream model and tight space bounds are known for these two problems. There has been growing interest in revisiting these problems in the framework of random-order streams. The best space lower bound known for computing the k th frequency moment in random-order streams is *** (n 1 *** 2.5/k ) by Andoni et al., and it is conjectured that the real lower bound shall be *** (n 1 *** 2/k ). In this paper, we resolve this conjecture. In our approach, we revisit the direct sum theorem developed by Bar-Yossef et al. in a random-partition private messages model and provide a tight *** (n 1 *** 2/k /***) space lower bound for any ***-pass algorithm that approximates the frequency moment in random-order stream model to a constant factor. Finally, we also introduce the notion of space-entropy tradeoffs in random order streams, as a means of studying intermediate models between adversarial and fully random order streams. We show an almost tight space-entropy tradeoff for L *** distance and a non-trivial tradeoff for L p distances.