Norm-Ranging LSH for Maximum Inner Product Search
Neyshabur and Srebro proposed SIMPLE-LSH [2015], which is the state-of-the-art hashing based algorithm for maximum inner product search (MIPS). We found that the performance of SIMPLE-LSH, in both theory and practice, suffers from long tails in the 2-norm distribution of real datasets. We propose NORM-RANGING LSH, which addresses the excessive normalization problem caused by long tails by partitioning a dataset into sub-datasets and building a hash index for each sub-dataset independently. We prove that NORM-RANGING LSH achieves lower query time complexity than SIMPLE-LSH under mild conditions. We also show that the idea of dataset partitioning can improve another hashing based MIPS algorithm. Experiments show that NORM-RANGING LSH probes much less items than SIMPLE-LSH at the same recall, thus significantly benefiting MIPS based applications.
Authors find that the inner-product-to-cosine-reduction technique by Neyshabur and Srebro suffers from a disbalance in the L2-norm distribution. They show that this can be improved by splitting the data set (plus some additional improvements). They present a proof that such a split has theoretical guarantees. In addition, they proposed an approach to improve probing order of the buckets in their norm-split index.   They demonstrate their methods is partly applicable to A2-LSH, but it will likely improve other SOTA methods.  This is very solid work: I would vote for acceptance despite it misses comparison to some state-of-the-art and uses mostly small data sets (even ImageNet is not really large-scale as authors claim).   PROS: This is a well-written paper: I enjoyed reading it.   Authors make an interesting finding that can potentially benefit several methods for k-NN search using the maximum-inner product as the similarity function. In particular, the method of Andoni et al [2015]. Possibly, data set splitting can be useful even for graph-based retrieval methods (despite some of your tricks are applicable to random-projection LSH only).  They present several other interesting findings, some of which I briefly mention in detailed comments.  CONS: Authors do not compare against state-of-the art graph-based algorithms (Malkov and Yashunin ). Evaluation leaves somewhat to be desired, because two out of three data sets are small (Netfix is in fact tiny). ImageNet is not very big either.  Additional baseline that would be nice to run:  1) Andoni et al method for the cosine similarity search combined with the inner-product-to-cosine-reduction by Neyshabur and Srebro. One should be quite curious if Andoni et al would benefit from your data set splitting approach. Again, I understand it wouldn't be exactly straightforward to apply: yet, even a simple data set splitting with parallel searching over split may be beneficial. I think this would be a strong baseline as Andoni et all improve over simple-LSH quite a bit.  2) My feeling is that your extension to A2-LSH (Section 5) should have been implemented and tested.  SOME FURTHER COMMENTS:   61-62: Wasn't the original definition specified in terms of the distance? Does it make a difference when you reformulate it using the similarity instead? I think it would beneficial to formally introduce similarity and explain how it relates to the distance (e.g., there's an obvious connection for the cosine similarity).  68-69: the probability GIVEN THAT A RANDOM FUNCTION is drawn randomly and independently FOR EACH PAIR of vectors. This nearly always silent assumption of the LSH community was deservedly criticized by Wang et al. I think there is nothing bad about using this simplified assumption, but it is quite bad NOT TO MENTION it. Nearly nobody gets this subtlety and I have seen a machine learning professor from a top university baffled by the question what is actually assumed to be random in the theory of LSH.  103: Complexity under which assumptions? Also, missing citation to back up this. 108: It would be nice to add: i.e., the higher is the similarity, the lower is the complexity. Otherwise: nice observation also backed up by theory! 117-118: Nice observation too!  226: 2 million is not large at all! And this is your only reasonably large data set.   REFERENCES  Andoni, Alexandr, et al. "Practical and optimal LSH for angular distance." Advances in Neural Information Processing Systems. 2015. Malkov, Yu A., and D. A. Yashunin. "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs." arXiv preprint arXiv:1603.09320 (2016).  Wang, Hongya, et al. "Locality sensitive hashing revisited: filling the gap between theory and algorithm analysis.