Statistical analysis of sketch estimators

ABSTRACT

Sketching techniques can provide approximate answers to aggregate queries either for data-streaming or distributed computation. Small space summaries that have linearity properties are required for both types of applications. The prevalent method for analyzing sketches uses moment analysis and distribution independent bounds based on moments. This method produces clean, easy to interpret, theoretical bounds that are especially useful for deriving asymptotic results. However, the theoretical bounds obscure fine details of the behavior of various sketches and they are mostly not indicative of which type of sketches should be used in practice. Moreover, no significant empirical comparison between various sketching techniques has been published, which makes the choice even harder. In this paper, we take a close look at the sketching techniques proposed in the literature from a statistical point of view with the goal of determining properties that indicate the actual behavior and producing tighter confidence bounds. Interestingly, the statistical analysis reveals that two of the techniques, Fast-AGMS and Count-Min, provide results that are in some cases orders of magnitude better than the corresponding theoretical predictions. We conduct an extensive empirical study that compares the different sketching techniques in order to corroborate the statistical analysis with the conclusions we draw from it. The study indicates the expected performance of various sketches, which is crucial if the techniques are to be used by practitioners. The overall conclusion of the study is that Fast-AGMS sketches are, for the full spectrum of problems, either the best, or close to the best, sketching technique. This makes Fast-AGMS sketches the preferred choice irrespective of the situation.

REFERENCES

• 1: N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy. Tracking join and self-join sizes in limited storage. J. Comput. Syst. Sci., 64(3):719--747, 2002.
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 3: K. P. Balanda and H. L. MacGillivray. Kurtosis: A critical review. J. American Statistician, 42(2):111--119, 1988.
• 4: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding Frequent Items in Data Streams, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.693-703, July 08-13, 2002
• 5: Graham Cormode , Minos Garofalakis, Sketching streams through the net: distributed approximate query tracking, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 6: Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005 [doi>10.1016/j.jalgor.2003.12.001]
• 7: Current Population Survey (CPS). http://www.census.gov/cps.
• 8: Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximation techniques for spatial data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007646]
• 9: Cristian Estan , Jeffrey F. Naughton, End-biased Samples for Join Cardinality Estimation, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.20, April 03-07, 2006 [doi>10.1109/ICDE.2006.61]
• 10: S. Ganguly, M. Garofalakis, and R. Rastogi. Processing data-stream join aggregates using skimmed sketches. In EDBT 2004, pages 569--586.
• 11: S. Ganguly, D. Kesh, and C. Saha. Practical algorithms for tracking database join sizes. In FSTTCS 2005, pages 297--309.
• 12: P. J. Haas and J. M. Hellerstein. Ripple joins for online aggregation. In SIGMOD 1999, pages 287--298.
• 13: D. Kempe, A. Dobra, and J. Gehrke. Computing aggregate information using gossip. In FOCS 2003.
• 14: MassDAL. http://www.cs.rutgers.edu/~muthu/massdal.html.
• 15: D. J. Olive. A simple confidence interval for the median. Manuscript, 2005.
• 16: F. Pennecchi and L. Callegaro. Between the mean and the median: the L_p estimator. Metrologia, 43(3):213--219, 2006.
• 17: R. M. Price and D. G. Bonett. Estimating the variance of the sample median. J. Statistical Computation and Simulation, 68(3):295--305, 2001.
• 18: Florin Rusu , Alin Dobra, Fast range-summable random variables for efficient aggregate estimation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142496]
• 19: J. Shao. Mathematical Statistics. Springer-Verlag, 1999.
• 20: Mikkel Thorup , Yin Zhang, Tabulation based 4-universal hashing with applications to second moment estimation, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
AGMS sketches, count-min sketches, fast-AGMS sketches, fast-count sketches, size of join estimation