Multiscale Quantization for Fast Similarity Search
We propose a multiscale quantization approach for fast similarity search on large, high-dimensional datasets. The key insight of the approach is that quantization methods, in particular product quantization, perform poorly when there is large variance in the norms of the data points. This is a common scenario for realworld datasets, especially when doing product quantization of residuals obtained from coarse vector quantization. To address this issue, we propose a multiscale formulation where we learn a separate scalar quantizer of the residual norm scales. All parameters are learned jointly in a stochastic gradient descent framework to minimize the overall quantization error. We provide theoretical motivation for the proposed technique and conduct comprehensive experiments on two large-scale public datasets, demonstrating substantial improvements in recall over existing state-of-the-art methods.
The paper proposes a novel approach to reduce quantization error in the scenario where the product quantization is applied to the residual values that are the result of the coarse whole-space quantization. To encode residuals the authors propose to (1) quantize the norm separately (2) apply product quantization to unit-normalized residuals. It trains everything in the end-to-end manner, which is certainly good.
Pros:
1. I very much like the approach.
2. The paper is well-written.
3. A good coverage of work related to quantization (including several relevant recent papers). However, not all work related to efficient k-NN search (see below)!
Cons:
1. The related work on non-quantization techniques doesn't mention any graph-based techniques. Compared to quantization approaches they are less SPACE-efficient (but so are LSH methods, even more so!), but they are super-fast. Empirically they often greatly outperform everything else, in particular, they outperform LSH.
One recent relevant work (but there are many others): Harwood, Ben, and Tom Drummond. "FANNG: fast approximate nearest neighbour graphs." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.
I would encourage authors to mention this line of work, space permitting.
2. The paper is a bit cryptic. See, e.g., my comment to the recall experiments section.
A few more detailed comments:
I think I can guess where formula 4:158 comes from, but it won't harm if you show a derivation.
7: 280 What do you mean by saying that VPSHUFB performs lookups? It's a shuffle instruction, not a store/gather instruction.
Recall experiments: Does the phrase "We generate ground-truth results using brute force search, and compare the
results of each method against ground-truth in fixed-bitrate settings." mean that you do not compute accuracy for the k-NN search using *ORIGINAL* vectors? Please, also clarify how do you understand ground-truth in the fixed-bitrate setting.
Figure 4: please, explain better the figures. I don't quite get what is exactly the number of neighbors on x axis. Is this the number of neighbors retrieved using an approximated distance, i.e., using the formula in 4:158?
Speed benchmarks are a bit confusing, because these are only for sequential search using a tiny subset of data likely fitting into a L3 cache. I would love to see actually full-size tests. 
Regarding the POPCNT approach: what exactly do you do? Is it a scalar code? Is it single-thread? I am asking b/c I am getting twice as longer processing times using POPCNT for the Hamming distance with the same number of bits (128).
What is your hardware: CPU, #of cores, RAM, cache size? Are your speed-benchmarks single-threaded?
Which compiler do you use?
Please, clarify if your approach to learning an orthogonal transformation (using Cayley factorization) is novel or not.