Pseudo-random number generation for sketch-based estimations

ABSTRACT

The exact computation of aggregate queries, like the size of join of two relations, usually requires large amounts of memory (constrained in data-streaming) or communication (constrained in distributed computation) and large processing times. In this situation, approximation techniques with provable guarantees, like sketches, are one possible solution. The performance of sketches depends crucially on the ability to generate particular pseudo-random numbers. In this article we investigate both theoretically and empirically the problem of generating k-wise independent pseudo-random numbers and, in particular, that of generating 3- and 4-wise independent pseudo-random numbers that are fast range-summable (i.e., they can be summed in sublinear time). Our specific contributions are: (a) we provide a thorough comparison of the various pseudo-random number generating schemes; (b) we study both theoretically and empirically the fast range-summation property of 3- and 4-wise independent generating schemes; (c) we provide algorithms for the fast range-summation of two 3-wise independent schemes, BCH and extended Hamming; and (d) we show convincing theoretical and empirical evidence that the extended Hamming scheme performs as well as any 4-wise independent scheme for estimating the size of join of two relations using AMS sketches, even though it is only 3-wise independent. We use this scheme to generate estimators that significantly outperform state-of-the-art solutions for two problems, namely, size of spatial joins and selectivity estimation.

REFERENCES

• 1: A. Pavan , Srikanta Tirthapura, Range-Efficient Computation of F" over Massive Data Streams, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.32-43, April 05-08, 2005 [doi>10.1109/ICDE.2005.118]
• 2: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 3: Alon, N., Gibbons, P. B., Matias, Y., and Szegedy, M. 2002. Tracking join and self-join sizes in limited storage. J. Comput. Syst. Sci. 64, 3, 719--747.
• 4: 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]
• 5: Ziv Bar-Yosseff , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 6: A. R. Calderbank , A. Gilbert , K. Levchenko , S. Muthukrishnan , M. Strauss, Improved range-summable random variable construction algorithms, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 7: Carter, L. and Wegman, M. N. 1979. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 2, 143--154.
• 8: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004 [doi>10.1016/S0304-3975(03)00400-6]
• 9: 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]
• 10: Deskins, W. E. 1996. Abstract Algebra. Dover, New York.
• 11: Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Processing complex aggregate queries over data streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564699]
• 12: Ehrenfeucht, A. and Karpinski, M. 1990. The computational complexity of (xor-and) counting problems. Tech. Rep. TR-90-033, ICSI, Berkeley, California.
• 13: Joan Feigenbaum , Sampath Kannan , Martin J. Strauss , Mahesh Viswanathan, An Approximate L¹-Difference Algorithm for Massive Data Streams, SIAM Journal on Computing, v.32 n.1, p.131-151, 2003 [doi>10.1137/S0097539799361701]
• 14: Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Processing set expressions over continuous update streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872790]
• 15: Ganguly, S., Garofalakis, M., and Rastogi, R. 2004. Processing data-stream join aggregates using skimmed sketches. In Proceedings of the 9th International Conference on Extending Database Technology. Springer, 569--586.
• 16: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, One-Pass Wavelet Decompositions of Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.541-554, March 2003 [doi>10.1109/TKDE.2003.1198389]
• 17: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Domain-Driven Data Synopses for Dynamic Quantiles, IEEE Transactions on Knowledge and Data Engineering, v.17 n.7, p.927-938, July 2005 [doi>10.1109/TKDE.2005.108]
• 18: Goldreich, O. 1997. A sample of samplers: A computational perspective on sampling. Electron. Colloq. Comput. Complex. 4, 20.
• 19: Hedayat, A. S., Sloane, N. J. A., and Stufken, J. 1999. Orthogonal Arrays: Theory and Applications. Springer, New York.
• 20: Marek Karpinski , Michael Luby, Approximating the number of zeroes of a GF[2] polynomial, Journal of Algorithms, v.14 n.2, p.280-287, March 1993 [doi>10.1006/jagm.1993.1014]
• 21: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 22: Balachander Krishnamurthy , Subhabrata Sen , Yin Zhang , Yan Chen, Sketch-based change detection: methods, evaluation, and applications, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948236]
• 23: Levchenko, K. 2005. http://www.cse.ucsd.edu/~klevchen/II-2005.pdf.
• 24: Michael Luby , Avi Wigderson, Pairwise Independence and Derandomization, University of California at Berkeley, Berkeley, CA, 1995
• 25: Shao, J. 1999. Mathematical Statistics. Springer, New York.
• 26: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 27: 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
• 28: Wegman, M. and Carter, J. 1981. New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 3, 22, 265--279.

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: Random number generation

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
Sketches, approximate query processing, data synopses, fast range-summation