<p>Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of <span class="math-container">$k$</span> permutation for comparison purposes, and then takes number_of_collisions / <span class="math-container">$k$</span> as an estimate of Jaccard similarity between target streams. (There is additional work on how to compute these k-hashes more efficiently, or use a single bit from each, etc, but let's not get into that.)</p>

<p>My question is why not find the <span class="math-container">$k$</span> minimum elements instead in a single permutation? Especially since reduces the computation cost of <span class="math-container">$k$</span> hashes to just <span class="math-container">$1$</span>. Is the required size of <span class="math-container">$k$</span> much larger, or does the analysis break?</p>

CC BY-SA 4.0
2018-11-25T21:15:15.913Z
Have you searched for things like "bottom-$k$ sampling"? E.g., read the introduction of [this paper](https://arxiv.org/abs/1303.5479) which discusses it.
Clement C.
CC BY-SA 4.0
2018-11-25T21:17:32.130Z
I suggest working through the math to figure out the performance of the scheme with arbitrary k, for a fixed amount of time/space, and then optimize to find the optimal k, and see what you find.  You should be able to work this out on your own.  This site works better for questions that you're already thinking about, and when you show your progress so far.  See the [help/on-topic].
D.W.
CC BY-SA 4.0
2018-11-25T21:36:58.180Z
I did try looking through the original min-wise paper and it's citations, the closest I found was work on Conditional Random Sampling by Li. et at. Your link is very helpful Clement! It works through the bias quite well.
Amir
<approximation-algorithms><hash-function>
Why do k min-hashes, instead of one hash where we find the k minimum elements?
Amir
# Why do k min-hashes, instead of one hash where we find the k minimum elements?

(Asked by: username_0 on 2018-11-24)

Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of $k$ permutation for comparison purposes, and then takes number\_of\_collisions / $k$ as an estimate of Jaccard similarity between target streams. (There is additional work on how to compute these k-hashes more efficiently, or use a single bit from each, etc, but let's not get into that.)

My question is why not find the $k$ minimum elements instead in a single permutation? Especially since reduces the computation cost of $k$ hashes to just $1$. Is the required size of $k$ much larger, or does the analysis break?

**Tags:** approximation-algorithms, hash-function
> **Comments:**
> **username_1**: Have you searched for things like "bottom-$k$ sampling"? E.g., read the introduction of [this paper](https://arxiv.org/abs/1303.5479) which discusses it.  
> **username_2**: I suggest working through the math to figure out the performance of the scheme with arbitrary k, for a fixed amount of time/space, and then optimize to find the optimal k, and see what you find.  You should be able to work this out on your own.  This site works better for questions that you're already thinking about, and when you show your progress so far.  See the [help/on-topic].  
> **username_0**: I did try looking through the original min-wise paper and it's citations, the closest I found was work on Conditional Random Sampling by Li. et at. Your link is very helpful Clement! It works through the bias quite well.  

---

## 0 answers

