Simple and Efficient Weighted Minwise Hashing
Weighted minwise hashing (WMH) is one of the fundamental subroutine, required by many celebrated approximation algorithms, commonly adopted in industrial practice for large -scale search and learning. The resource bottleneck with WMH is the computation of multiple (typically a few hundreds to thousands) independent hashes of the data. We propose a simple rejection type sampling scheme based on a carefully designed red-green map, where we show that the number of rejected sample has exactly the same distribution as weighted minwise sampling. The running time of our method, for many practical datasets, is an order of magnitude smaller than existing methods. Experimental evaluations, on real datasets, show that for computing 500 WMH, our proposal can be 60000x faster than the Ioffe's method without losing any accuracy. Our method is also around 100x faster than approximate heuristics capitalizing on the efficient "densified" one permutation hashing schemes [26,27]. Given the simplicity of our approach and its significant advantages, we hope that it will replace existing implementations in practice.
The paper comes up with a novel method to find the Jacaard similarity by viewing elements of vectors x,y as probabilities instead of positive integers, and uses a simple (if almost obvious in retrospect) rejection sampling / hashing method to derive these probabilities. Experimental figures are shown, and discussion about the hashing method is given.
The authors achieve two things in their paper: One, improving weighted minwise hashing to compute the Jacaard similarity in time an order of magnitude less than Ioffe's method. Two, which I feel is more important, a simple yet novel method which is easily understandable and implementable.  To give a comparison, Ioffe's paper took a few days to read and absorb (which is understandable, since was then "the best" method so far), and one could imagine a new paper having more complex arguments / algorithm to beat Ioffe's results (in terms of accuracy and running time). This paper was remarkably easy to read and understand, and is obvious in retrospect.  Thus, this paper gets high scores in technical quality, novelty, and impact.  Experimental results are well presented.  Some small details: Surprisingly, I found the proof in the supplementary material for Theorem 1 harder to understand (notation is a bit confusing); an easier argument would be to argue that for the number of steps (hash function output) for two pairwise vectors to be the same ; this is simply adding up the probability that : the hashes are both zero, both one, both two , both three, both four, .....   This is an infinite geometric sum, but it factors out nicely into the result required using some high school algebra.   One note: seeds may be different across different languages / version of programming languages - so storing these seeds would not necessarily work all the time - although it would be easy to re-generate these hashes.   Furthermore, Algorithm 3 and 4, Figure 1 are a bit dense / confusing. For example, the red green map in Figure 1 could have dotted lines extending down for each M_is for easier intuition, and better spacing of x_is, y_is.   This is not to say the algorithms / figures should not be given. Rather, reading the paper gave the general idea, and it was writing out sample code / simulations in Matlab that understood what Algorithm 3 / Algorithm 4 does. Perhaps put the steps of these algorithms on the last page or in the supplementary material since the steps make the method seem much harder than it really is.