Math @ Duke

Publications [#235848] of Robert Calderbank
Papers Published
 Calderbank, AR; Gilbert, A; Levchenko, K; Muthukrishnan, S; Strauss, M, Improved rangesummable random variable construction algorithms,
Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
(July, 2005),
pp. 840849
(last updated on 2019/01/16)
Abstract: Rangesummable universal hash functions, also known as rangesummable random variables, are binaryvalued 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  smallspace summaries of the input sequence. We present two new constructions of rangesummable universal hash functions on nbit strings, one based on ReedMuller codes which gives kuniversal 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 secondorder ReedMuller code, which gives 5universal 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

