Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams
Vladimir Braverman, Rafail Ostrovsky
Abstract:
In their ground-breaking paper, Indyk and Woodruff (STOC 05) showed how to compute the k-th frequency moment Fk(for k > 2) in space Ο( poly-log(n,m). n 1-2/K), giving the first optimal result up to poly-logarithmic factors in n and m ( here m is the length of the stream and n is the size of the domain.) The method of Indyk and Woodruff reduces the problem of Fk to the problem of computing heavy hitters in the streaming manner. Their reduction only requires polylogarithmic overhead in term of the space complexity and is based on the fundamental idea of “layering.” Since 2005 The method of Indyk and Woodruff been used in numerous applications and has become a standard tool for streaming computations.
We propose a new recursive sketch that generalizes and improves the reduction of Indyk and Woodruff. Our method works for any non-negative frequency-based function in several models including the insertion-only model, the turnstile model and sliding window model. for frequency-based functions with sublinear polynomial space complexity our reduction only required log(c)(n) overhead , where log(c)(n) is the iterative log function. Thus, we improve the reduction of Indyk and Woodruff by polylogarithmic factor. We illustrate the generality of our method by several applications:frequency moments, frequency based functions, spatial data streams and measuring independence of data sets.
comment: APPROX-RANDOM 2013: 58-70
Fetch PDF file of the paper
| Back to Publications List |