<p>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 <a href="http://dl.acm.org/citation.cfm?id=1242528" rel="nofollow">this paper</a></p>

CC BY-SA 3.0
2012-09-16T03:51:11.810Z
2012-09-16T03:51:11.810Z
redplum
<p>I'm finding is there any range summable hash function.</p>

<p>ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to <a href="http://dl.acm.org/citation.cfm?id=237823" rel="nofollow">The space complexity of approximating the frequency moments</a>.</p>

<p><a href="http://dl.acm.org/citation.cfm?id=776779" rel="nofollow">Improved range-summable random variable construction algorithms</a> gives one for any k-wise independence, 
but its author <a href="http://web.eecs.umich.edu/~martinjs/" rel="nofollow">Martin J. Strauss</a> shows it is <a href="http://web.eecs.umich.edu/~martinjs/papers/ll-2005.pdf" rel="nofollow">incorrect</a> from his homepage.</p>

<p>The only one I can find is from <a href="http://dl.acm.org/citation.cfm?id=1070550" rel="nofollow">One-Pass Wavelet Decompositions of Data Streams</a>, where a 4-wise one is given. It used second-order Reed-Muller hash functions.</p>

<p>Are there any other range summable hash functions with 4 or more independence?</p>

CC BY-SA 3.0
2012-09-12T08:58:07.887Z
the first paper you reference has quite a few other references on page 3.
Sasho Nikolov
CC BY-SA 3.0
2012-09-12T18:28:50.897Z
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.
Kaveh
CC BY-SA 3.0
2012-09-13T00:44:56.500Z
thanks for you help. I have modified a little to make it clear. The "Improved" one is incorrect, not "one-pass" one.
redplum
<ds.algorithms><coding-theory><hash-function>
fast range summable hash functions
redplum
# fast range summable hash functions

(Asked by: username_0 on 2012-09-12)

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](http://dl.acm.org/citation.cfm?id=237823).

[Improved range-summable random variable construction algorithms](http://dl.acm.org/citation.cfm?id=776779) gives one for any k-wise independence,
but its author [Martin J. Strauss](http://web.eecs.umich.edu/~martinjs/) shows it is [incorrect](http://web.eecs.umich.edu/~martinjs/papers/ll-2005.pdf) from his homepage.

The only one I can find is from [One-Pass Wavelet Decompositions of Data Streams](http://dl.acm.org/citation.cfm?id=1070550), 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?

**Tags:** ds.algorithms, coding-theory, hash-function

> **Comments:**
> **username_1**: the first paper you reference has quite a few other references on page 3.  
> **username_2**: 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.  
> **username_0**: thanks for you help. I have modified a little to make it clear. The "Improved" one is incorrect, not "one-pass" one.  

---

## 1 answers

### Answer by username_0 on 2012-09-16. Score: 1 | Accepted answer

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](http://dl.acm.org/citation.cfm?id=1242528)


---

