Revisiting Kernelized Locality-Sensitive Hashing for Improved Large-Scale Image Retrieval
This work addresses a bottleneck in efficient image retrieval for computer vision applications, offering incremental improvements to an existing method.
The paper tackles the problem of improving approximate nearest-neighbor searches in kernel spaces for large-scale image retrieval by reinterpreting kernelized locality-sensitive hashing (KLSH), resulting in at least 12% improved recall performance on benchmark datasets.
We present a simple but powerful reinterpretation of kernelized locality-sensitive hashing (KLSH), a general and popular method developed in the vision community for performing approximate nearest-neighbor searches in an arbitrary reproducing kernel Hilbert space (RKHS). Our new perspective is based on viewing the steps of the KLSH algorithm in an appropriately projected space, and has several key theoretical and practical benefits. First, it eliminates the problematic conceptual difficulties that are present in the existing motivation of KLSH. Second, it yields the first formal retrieval performance bounds for KLSH. Third, our analysis reveals two techniques for boosting the empirical performance of KLSH. We evaluate these extensions on several large-scale benchmark image retrieval data sets, and show that our analysis leads to improved recall performance of at least 12%, and sometimes much higher, over the standard KLSH method.