3210ddbeaa16948a702b6049b8d9a202-Reviews.html

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. The paper studies the collision probability of the following hashing scheme for points in R^D: the hash function picks a random vector of D i.i.d. The same scheme for 2-stable distribution has been studied before (known as sim-hash). The main result shows that the collision probability for alpha=1 on binary data can be approximated by a function of the chi-square similarity. The bound for general data is pointed out by the authors themselves to be far from the true collision probability so it is not clear what it means, especially regarding the comparison between that bound and the chi square similarity. The paper provides some experiments to show that the collision probability is approximately equal to some functions of the chi square similarity, and thus one can approximate chi square similarity from the collision probability and these functions. However, in this process, I think we are no longer able to use linear SVM or efficient near neighbor search (advantages 2 and 3 in the introduction) and have to use kernel SVM and exhaustive search instead. When using linear SVM, we use the kernel implicitly defined by the LSH and there is inadequate explanation of how useful it is (chi square is useful but it does not mean any function of it is also useful).