Optimal space lower bounds for all frequency moments
David P. Woodruff · 2004
Abstract We prove that any one-pass streaming algorithm which (ffl, ffi)-approximates the kth frequency moment Fk, for any real k 6 = 1 and any ffl = \\Omega i 1pm j, must use \\Omega \\Gamma 1ffl2 \\Delta bits of space, where m is the size of the universe. This is optimal in terms of ffl, resolves the open questions of BarYossef et al in [3, 4], and extends the \\Omega \\Gamma 1ffl2 \\Delta lower bound for F0 in [11] to much smaller ffl by applying novel techniques. Along the way we lower bound the one-way communication complexity of approximating the Hamming distance and the number of bipartite graphs with minimum/maximum degree constraints. 1 Introduction Computing statistics on massive data sets is increasinglyimportant these days. Advances in communication and storage technology enable large bodies of raw datato be generated daily, and consequently, there is a rising demand to process this data efficiently. Sinceit is impractical for an algorithm to store even a small fraction of the data stream, its performance istypically measured by the amount of space it uses. In many scenarios, such as internet routing, once a streamelement is examined it is lost forever unless explicitly saved by the processing algorithm. This, along with thesheer size of the data, makes multiple passes over the data infeasible. In this paper we restrict our attention toone-pass streaming algorithms and we investigate their space complexity.Let a =