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?

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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