Practical Hash Functions for Similarity Estimation and Dimensionality Reduction
Hashing is a basic tool for dimensionality reduction employed in several aspects of machine learning. However, the perfomance analysis is often carried out under the abstract assumption that a truly random unit cost hash function is used, without concern for which concrete hash function is employed. The concrete hash function may work fine on sufficiently random input. The question is if they can be trusted in the real world where they may be faced with more structured input. In this paper we focus on two prominent applications of hashing, namely similarity estimation with the one permutation hashing (OPH) scheme of Li et al. [NIPS'12]   and feature hashing (FH) of Weinberger et al. [ICML'09], both of which have found numerous applications, i.e. in approximate near-neighbour search with LSH and large-scale classification with SVM. We consider the recent mixed tabulation hash function of Dahlgaard et al. [FOCS'15]  which was proved theoretically to perform like a truly random hash function in many applications, including the above OPH. Here we first show improved concentration bounds for FH with truly random hashing and then argue that mixed tabulation performs similar when the input vectors are not too dense. Our main contribution, however, is an experimental comparison of different hashing schemes when used inside FH, OPH, and LSH. We find that mixed tabulation hashing is almost as fast as the classic multiply-modprime scheme (ax + b) mod p. Mutiply-mod-prime is guaranteed to work well on sufficiently random data, but here we demonstrate that in the above applications, it can lead to bias and poor concentration on both real-world and synthetic data. We also compare with the very popular MurmurHash3, which has no proven guarantees. Mixed tabulation and MurmurHash3 both perform similar to truly random hashing in our experiments. However, mixed tabulation was 40% faster than MurmurHash3, and it has the proven guarantee of good performance (like fully random) on all possible input making it more reliable.
The main contribution of the paper is the set of empirical comparisons of various hashing functions, mutiply, 2-universal (2U), Murmur, and mixed tabulation, for (1) similarity estimation and (2) LSH. This type of empical evaluations is very important and will benefit practioners. Overall, this is a good paper. For improving the paper, I would suggest the authors to take into consideration of the following comments (some of which might be crucial):
---1. There is already a study of using 2U and 4U hashing for similarity estimation and classification tasks. See
[1] b-Bit Minwise Hashing in Practice. Proceedings of the 5th Asia-Pacific Symposium on Internetware, 2013. 
[2] https://arxiv.org/abs/1205.2958, which is a more detailed version of [1], as far as I can tell. 
[1,2] used 2U and 4U for evalating both b-bit minwise hashing and FH　(although they used VW to refer to FH). For example, [1,2] showed that for dense sets, 2U and 4U had an obvious bias and larger MSE. 
I would suggest the authors to cite one of [1,2] and comment on the additional contributions beyond [1,2]. 
---2. [1,2] already showed that for classification tasks, 2U and 4U seems to be sufficiently accurate compared to using fully random hash functions. This paper ommited classification experiments. It is not at all surprising that mixed tabulation will work as well as fully random hash for classification, which the NIPS community would probably care more (than LSH). 
---3. This paper used 2U instead of 4U. It would be more coninvincing to present the results using 4U (or both 2U and 4U) as it is well-understood that in some cases 4U is indeed better. 
---4. The LSH experiments can have been presented more convincingly. 
a) In practice, we typically must guaranttee a good recall, even at the cost of retrieving more points. therefore, while the presentation of using the ratio # retrieved / recall is useful, it may cover important details. 
b) only mulply hash and mix tabulation results are presented. It is important to also present fully random results and 2U/4U hashing results. 
c) If the results from different hash functions as shown  in Figure 5 really differ that much, then it is not that appropriate to compare the results at a fixed K and L, because each hash function may work better with a particular parameter. 
d) The LSH parameters are probably chosen not so appropriately. The paper says it followed [30] for the parameters K,L by using K ={8,10,12} and L={8,10,12}. However, [30] actually used  for K = {6, 8, 10, 12} and L = {4, 8, 16, 32, 64, 128}
e)  LSH-OPH with K = {8,10,12} is likely too large. L =[8,10,12} is likely too small, according to prior experience. If the parameters are not (close to) optimal, then it is difficult to judge usefulness of the experiment results. 
-----------
In Summary, overall, the topic of this paper is very important. The limitation of the current submission includes i) a lack of citation of the prior work [1,2] and explanation on the additional contribution beyond [1,2]. ii) the classification experiments are missing. It is very possible that no essential difference will be observed for any hash function, as concluded in the prior work [1,2]. iii) the LSH experiments may have issues and the conclusions drawn from the LSH experiments are hard to judge.