Coding for Random Projections and Approximate Near Neighbor Search
By Ping Li, Michael M. Mitzenmacher, Anshumali Shrivastava. 2014
10 citations recorded by the source corpus.
This technical note compares two coding (quantization) schemes for random projections in the context of sub-linear time approximate near neighbor search. The first scheme is based on uniform quantization while the second scheme utilizes a uniform quantization plus a uniformly random offset (which has been popular in practice). The prior work compared the two schemes in the context of similarity estimation and training linear classifiers, with the conclusion that the step of random offset is not necessary and may hurt the performance (depending on the similarity level). The task of near neighbor search is related to similarity estimation with importance distinctions and requires own study. In this paper, we demonstrate that in the context of near neighbor search, the step of random offset is not needed either and may hurt the performance (sometimes significantly so, depending on the similarity and other parameters).
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Anshumali Shrivastava
- Ping Li
- Behnam Neyshabur
- Nati Srebro
- Sanjiv Kumar
- Yoshua Bengio
- Minjoon Seo
- Carlos Guestrin
In Computer Vision and Pattern Recognition
- Anshumali Shrivastava
- Ping Li
- Behnam Neyshabur
- Nati Srebro
- Sanjiv Kumar
- Yoshua Bengio
- Minjoon Seo
- Pascal Vincent
In Information Retrieval & Search
- Anshumali Shrivastava
- Ping Li
- Behnam Neyshabur
- Nati Srebro
- Sanjiv Kumar
- Minjoon Seo
- Ruiqi Guo
- Vidhisha Balachandran
Citations in the corpus
- Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, background): “The recent work on coding for random projections [16] showed that L2LSH can be improved when the data are normalized for building large-scale linear classifiers as well as near neighbor search [17].”
- Asymmetric Minwise Hashing (2014, background): “The recent work on coding for random projections [26, 27] has shown the advantage of SRP (and 2-bit random projections) over L2LSH for both similarity estimation and near neighbor search.”
- Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) (2014, background): “Recently in [17, 18], it was observed that the quantization of random projections used by traditional L2-LSH scheme is not desirable when the data is normalized and in fact the shift b in Eq.”