IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014
Example of our method
Comparison between our method and the state-of-the-art methods
Abstract
Many binary code embedding techniques have been proposed
for large-scale approximate nearest neighbor search
in computer vision. Recently, product quantization that encodes
the cluster index in each subspace has been shown to
provide impressive accuracy for nearest neighbor search.
In this paper, we explore a simple question: is it best to
use all the bit budget for encoding a cluster index in each
subspace? We have found that as data points are located
farther away from the centers of their clusters, the error
of estimated distances among those points becomes larger.
To address this issue, we propose a novel encoding scheme
that distributes the available bit budget to encoding both the
cluster index and the quantized distance between a point
and its cluster center. We also propose two different distance
metrics tailored to our encoding scheme. We have
tested our method against the-state-of-the-art techniques on
several well-known benchmarks, and found that our method
consistently improves the accuracy over other tested methods.
This result is achieved mainly because our method accurately
estimates distances between two data points with
the new binary codes and distance metric.
