Improved range-summable random variable construction algorithms

ABSTRACT

Range-summable universal hash functions, also known as range-summable random variables, are binary-valued hash functions which can efficiently hash single values as well as ranges of values from the domain. They have found several applications in the area of data stream processing where they are used to construct sketches---small-space summaries of the input sequence.We present two new constructions of range-summable universal hash functions on n-bit strings, one based on Reed-Muller codes which gives k-universal hashing using O(n^{log k}) space and time for point operations and O(n^{2 log k}) for range operations, and another based on a new subcode of the second-order Reed-Muller code, which gives 5-universal hashing using O(n) space, O(n log³ n) time for point operations, and O(n³) time for range operations.We also present a new sketch data structure using the new hash functions which improves several previous results.

REFERENCES

• 1: Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303978]
• 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: 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
• 4: J. L. Carter and M. N. Wegman. Universal Classes of Hash Functions. J. of Comp. and Syst. Sci. 18, 143--154 (1979).
• 5: 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
• 6: G. Cormode, S. Muthukrishnan. Estimating Dominance Norms of Multiple Data Streams. ESA 2003: 148--160.
• 7: G. Cormode and S. Muthukrishnan. Improved Data Stream Summary: The Count-Min Sketch and its Applications. DIMACS Technical Report 2003--20, June 2003. LATIN 2004. To appear in J. Algorithms.
• 8: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 9: 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]
• 10: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 11: O. Goldreich, S. Goldwasser and A. Nussboim. On the implementation of huge random objects. ECCC eport TR03-045.
• 12: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 13: Michael Luby , Avi Wigderson, Pairwise Independence and Derandomization, University of California at Berkeley, Berkeley, CA, 1995
• 14: F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977.
• 15: S. Muthukrishnan. Data stream algorithms. http://www.cs.rutgers.edu/~muthu/stream-1-1.ps
• 16: S. Muthukrishnan, M. Strauss. Maintenance of Multidimensional Histograms. FSTTCS 2003: 352--362.
• 17: S. Muthukrishnan , Martin Strauss, Rangesum histograms, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 18: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 19: Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
• 20: M. N. Wegman and J. L. Carter. New Hash Functions and Their Use in Authentication and Set Equality. J. of Comp. and Syst. Sci. 22, 265--279 (1981).
• 21: Avi Wigderson, The amazing power of pairwise independence (abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.645-647, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195420]