I'm finding is there any range summable hash function.

ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to The space complexity of approximating the frequency moments.

Improved range-summable random variable construction algorithms gives one for any k-wise independence, but its author Martin J. Strauss shows it is incorrect from his homepage.

The only one I can find is from One-Pass Wavelet Decompositions of Data Streams, where a 4-wise one is given. It used second-order Reed-Muller hash functions.

Are there any other range summable hash functions with 4 or more independence?

  • 1
    $\begingroup$ the first paper you reference has quite a few other references on page 3. $\endgroup$ Commented Sep 12, 2012 at 8:58
  • $\begingroup$ Please note that csthoery is a Q&A, not a discussion forum. ps: I think it would be helpful if you clarify what you exactly mean by a hash function since it is used to refer to various kind of objects. $\endgroup$
    – Kaveh
    Commented Sep 12, 2012 at 18:28
  • $\begingroup$ thanks for you help. I have modified a little to make it clear. The "Improved" one is incorrect, not "one-pass" one. $\endgroup$
    – redplum
    Commented Sep 13, 2012 at 0:44

1 Answer 1


I have found the newest one that gives 7-wise independence using MR code, also two others based on BCH and EH code with 3-wise independence. They are tested to be good enough for AMS sketch in this paper


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.