Sharing Hash Codes for Multiple Purposes

Wikor Pronobis Danny Panknin Johannes Kirschnick Vignesh Srinivasan Wojciech Samek Volker Markl Manohar Kaul Klaus-Robert Müller Shinichi Nakajima
Abstract: Locality sensitive hashing (LSH) is a powerful tool for sublinear-time approximate nearest neighbor search, and a variety of hashing schemes have been proposed for different similarity measures. However, hash codes significantly depend on the similarity, which prohibits users from adjusting the similarity at query time. In this paper, we propose multiple purpose LSH (mp-LSH) which shares the hash codes for different similarities. By using vector/code augmentation and cover tree techniques, our mp-LSH supports L2, ...