Skip to main content

Improved range-summable random variable construction algorithms

Publication ,  Journal Article
Calderbank, AR; Gilbert, A; Levchenko, K; Muthukrishnan, S; Strauss, M
Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
July 1, 2005

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 arid time for point operations and O(n 2 1og 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 3 n) time for point operations, and O(n 3) time for range operations. We also present a new sketch data structure using the new hash functions which improves several previous results.

Duke Scholars

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

July 1, 2005

Start / End Page

840 / 849
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Calderbank, A. R., Gilbert, A., Levchenko, K., Muthukrishnan, S., & Strauss, M. (2005). Improved range-summable random variable construction algorithms. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 840–849.
Calderbank, A. R., A. Gilbert, K. Levchenko, S. Muthukrishnan, and M. Strauss. “Improved range-summable random variable construction algorithms.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, July 1, 2005, 840–49.
Calderbank AR, Gilbert A, Levchenko K, Muthukrishnan S, Strauss M. Improved range-summable random variable construction algorithms. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2005 Jul 1;840–9.
Calderbank, A. R., et al. “Improved range-summable random variable construction algorithms.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, July 2005, pp. 840–49.
Calderbank AR, Gilbert A, Levchenko K, Muthukrishnan S, Strauss M. Improved range-summable random variable construction algorithms. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2005 Jul 1;840–849.

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

July 1, 2005

Start / End Page

840 / 849