Sketches for aggregate estimations over data streams
Alin Dobra, Florin Rusu · 2009
In this work, we present methods to speed-up the sketch computation. Sketches are randomized algorithms that use small amount of memory and that can be computed in one pass over the data. Frequency moments represent important distributional characteristics of the data that are required in any statistical modeling method. This work focuses on AGMS-sketches used for the estimation of the second frequency moment. Fast-AGMS sketches use hash functions to speed-up the computation by reducing the number of basic estimators that need to be updated. We show that hashing also changes the distribution of the estimator, thus improving the accuracy by orders of magnitude. The second method to speed-up the sketch computation is related to the degree of randomization used to build the estimator. We show that by using 3-wise independent random variables instead of the proposed 4-wise, significant improvements are obtained both in computation time and memory usage while the accuracy of the estimator stays the same. The last speed-up method we discuss is combining sketches and sampling. Instead of sketching the entire data, the sketch is built only over a sample of the data. We show that the accuracy of the estimator is not drastically affected even when the sample contains a small amount of the original data. When the three speed-up methods are put together, it is possible to sketch streams having input rates of millions of tuples per second in small memory while providing similar accuracy as the original AGMS sketches.