1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ the first paper you reference has quite a few other references on page 3. $\endgroup$
    – Sasho Nikolov
    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
    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
    Sep 13, 2012 at 0:44

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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