In the communication problem @math (universal relation) [KRW95], Alice and Bob respectively receive @math with the promise that @math . The last player to receive a message must output an index @math such that @math . We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly @math for failure probability @math . Our lower bound holds even if promised @math . As a corollary, we obtain optimal lower bounds for @math -sampling in strict turnstile streams for @math , as well as for the problem of finding duplicates in a stream. Our lower bounds do not need to use large weights, and hold even if promised @math at all points in the stream. We give two different proofs of our main result. The first proof demonstrates that any algorithm @math solving sampling problems in turnstile streams in low memory can be used to encode subsets of @math of certain sizes into a number of bits below the information theoretic minimum. Our encoder makes adaptive queries to @math throughout its execution, but done carefully so as to not violate correctness. This is accomplished by injecting random noise into the encoder's interactions with @math , which is loosely motivated by techniques in differential privacy. Our second proof is via a novel randomized reduction from Augmented Indexing [MNSW98] which needs to interact with @math adaptively. To handle the adaptivity we identify certain likely interaction patterns and union bound over them to guarantee correct interaction on all of them. To guarantee correctness, it is important that the interaction hides some of its randomness from @math in the reduction.
@cite_0: Emerging data stream management systems approach the challenge of massive data distributions which arrive at high speeds while there is only small storage by summarizing and mining the distributions using samples or sketches. However, data distributions can be "viewed" in different ways. A data stream of integer values can be viewed either as the forward distribution f (x), ie., the number of occurrences of x in the stream, or as its inverse, f-1 (i), which is the number of items that appear i times. While both such "views" are equivalent in stored data systems, over data streams that entail approximations, they may be significantly different. In other words, samples and sketches developed for the forward distribution may be ineffective for summarizing or mining the inverse distribution. Yet, many applications such as IP traffic monitoring naturally rely on mining inverse distributions.We formalize the problems of managing and mining inverse distributions and show provable differences between summarizing the forward distribution vs the inverse distribution. We present methods for summarizing and mining inverse distributions of data streams: they rely on a novel technique to maintain a dynamic sample over the stream with provable guarantees which can be used for variety of summarization tasks (building quantiles or equidepth histograms) and mining (anomaly detection: finding heavy hitters, and measuring the number of rare items), all with provable guarantees on quality of approximations and time space used by our streaming methods.We also complement our analytical and algorithmic results by presenting an experimental study of the methods over network data streams.
@cite_31: 
@cite_22: 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.
@cite_8: A dynamic geometric data stream is a sequence of m ADD REMOVE operations of points from a discrete geometric space 1,…, Δ d ?. ADD (p) inserts a point p from 1,…, Δ d into the current point set P, REMOVE(p) deletes p from P. We develop low-storage data structures to (i) maintain e-nets and e-approximations of range spaces of P with small VC-dimension and (ii) maintain a (1 + e)-approximation of the weight of the Euclidean minimum spanning tree of P. Our data structure for e-nets uses bits of memory and returns with probability 1 – δ a set of points that is an e-net for an arbitrary fixed finite range space with VC-dimension . Our data structure for e-approximations uses bits of memory and returns with probability 1 – δ a set of points that is an e-approximation for an arbitrary fixed finite range space with VC-dimension . The data structure for the approximation of the weight of a Euclidean minimum spanning tree uses O(log(1 δ)(log Δ e)O(d)) space and is correct with probability at least 1 – δ. Our results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P.
The question of whether @math -sampling is possible in low memory in turnstile streams was first asked in @cite_0 @cite_8 . The work @cite_8 applied @math -sampling as a subroutine in approximating the cost of the Euclidean minimum spanning tree of a subset @math of a discrete geometric space subject to insertions and deletions. The algorithm given there used space @math bits to achieve failure probability @math (though it is likely that the space could be improved to @math with a worse failure probability, by replacing a subroutine used there with a more recent @math -estimation algorithm of @cite_22 ). As mentioned, the currently best known upper bound solves @math -sampling @math using @math bits @cite_31 , which Theorem shows is tight.