The @math 'th frequency moment of a sequence of integers is defined as @math , where @math is the number of times that @math occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate @math up to relative error @math . We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate @math . We describe quantum algorithms for @math , @math and @math in this model which outperform the best possible classical algorithms almost quadratically.
( @math ) Flajolet and Martin gave a single-pass streaming algorithm which uses @math bits of space and computes @math up to a constant factor @cite_15 . Alon, Matias and Szegedy improved this by replacing the randomness used in the Flajolet-Martin algorithm with a family of simple hash functions @cite_35 . Bar- gave several different algorithms for approximating @math up to a @math factor, using as little as @math space @cite_42 . Kane, Nelson and Woodruff have now completed this line of research by giving a single-pass streaming algorithm which approximates @math using @math space @cite_17 . This is optimal for single-pass streaming algorithms; a space lower bound of @math was shown by Alon, Matias and Szegedy @cite_35 , and a lower bound of @math was shown by Woodruff @cite_37 . This was generalised to an @math lower bound for @math -pass streaming algorithms by Chakrabarti and Regev @cite_39 .
@cite_35 @cite_37 @cite_42 @cite_39 @cite_15 @cite_17
2064379477 2160681854 1785933978 1985526537 2025051251 2103126020
The frequency moments of a sequence containing mi elements of type i, for 1 i n, are the numbers Fk = P n=1 m k . We consider the space complexity of randomized algorithms that approximate the numbers Fk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0;F1 and F2 can be approximated in logarithmic space, whereas the approximation of Fk for k 6 requires n (1) space. Applications to data bases are mentioned as well. We prove that any one-pass streaming algorithm which (e, Δ)-approximates the kth frequency moment F k , for any real k ≠ 1 and any e = Ω(1 √m), must use Ω(1 e²) bits of space, where m is the size of the universe. This is optimal in terms of e, resolves the open questions of Bar- in [3, 4], and extends the Ω(1 e²) lower bound for F 0 in [11] to much smaller e 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. We present three algorithms to count the number of distinct elements in a data stream to within a factor of 1 ± ?. Our algorithms improve upon known algorithms for this problem, and offer a spectrum of time space tradeoffs. We prove an optimal @math lower bound on the randomized communication complexity of the much-studied gap-hamming-distance problem. As a consequence, we obtain essentially optimal multipass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments. The gap-hamming-distance problem is a communication problem, wherein Alice and Bob receive @math -bit strings @math and @math , respectively. They are promised that the Hamming distance between @math and @math is either at least @math or at most @math , and their goal is to decide which of these is the case. Since the formal presentation of the problem by Indyk and Woodruff [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 283--289], it had been conjectured that the naive protocol, which uses @math bits of communication, is asymptotically optimal. The conjecture was shown to be true in several special cases, e.g., when the communication is de... This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operations per element scanned. The algorithms are based on statistical observations made on bits of hashed values of records. They are by construction totally insensitive to the replicative structure of elements in the file; they can be used in the context of distributed systems without any degradation of performances and prove especially useful in the context of data bases query optimisation. We give the first optimal algorithm for estimating the number of distinct elements in a data stream, closing a long line of theoretical research on this problem begun by Flajolet and Martin in their seminal paper in FOCS 1983. This problem has applications to query optimization, Internet routing, network topology, and data mining. For a stream of indices in 1,...,n , our algorithm computes a (1 ± e)-approximation using an optimal O(1 e-2 + log(n)) bits of space with 2 3 success probability, where 0 We also give an algorithm to estimate the Hamming norm of a stream, a generalization of the number of distinct elements, which is useful in data cleaning, packet tracing, and database auditing. Our algorithm uses nearly optimal space, and has optimal O(1) update and reporting times.