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?

  • $\begingroup$ Have you searched for things like "bottom-$k$ sampling"? E.g., read the introduction of this paper which discusses it. $\endgroup$ – Clement C. Nov 25 '18 at 21:15
  • $\begingroup$ 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 center. $\endgroup$ – D.W. Nov 25 '18 at 21:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Amir Nov 25 '18 at 21:36

Your Answer

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

Browse other questions tagged or ask your own question.