Robust iterative quantization for efficient l_p-norm similarity search

Iterative Quantization (ITQ) is one of the most successful hashing based nearest-neighbor search methods for large-scale information retrieval in the past a few years due to its simplicity and superior performance. However, the performance of this algorithm degrades significantly when dealing with noisy data. Additionally, it can barely facilitate a wide range of applications as the distortion measurement only limits to l ₂ norm . In this paper, we propose an ITQ+ algorithm, aiming to enhance both robustness and generalization of the original ITQ algorithm. Specifically, a l _p,q -norm loss function is proposed to conduct the l _p -norm similarity search, rather than a l ₂ norm search. Despite the fact that changing the loss function to l _p,q -norm makes our algorithm more robust and generic, it brings us a challenge that minimizes the obtained orthogonality constrained l _p,q -norm function , which is non-smooth and non-convex. To solve this problem, we propose a novel and efficient optimization scheme. Extensive experiments on benchmark datasets demonstrate that ITQ+ is overwhelmingly better than the original ITQ algorithm, especially when searching similarity in noisy data.