Name
Abstract | ||
|---|---|---|
This paper studies the compact coding approach to approximate nearest neighbor search. We introduce a composite quantization framework. It uses the composition of several () elements, each of which is selected from a different dictionary, to accurately approximate a -dimensional vector, thus yielding accurate search, and represents the data vector by a short code composed of the indices of the selected elements in the corresponding dictionaries. Our key contribution lies in introducing a near-orthogonality constraint, which makes the search efficiency is guaranteed as the cost of the distance computation is reduced to from through a distance table lookup scheme. The resulting approach is called near-orthogonal composite quantization. We theoretically justify the equivalence between near-orthogonal composite quantization and minimizing an upper bound of a function formed by jointly considering the quantization error and the search cost according to a generalized triangle inequality. We empirically show the efficacy of the proposed approach over several benchmark datasets. In addition, we demonstrate the superior performances in other three applications: combination with inverted multi-index, inner-product similarity search, and query compression for mobile search. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/TPAMI.2018.2835468 | IEEE transactions on pattern analysis and machine intelligence |
Keywords | DocType | Volume |
Approximate nearest neighbor search,quantization,composite quantization,near-orthogonality | Journal | abs/1712.00955 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jingdong Wang | 1 | 4198 | 156.76 |
| Ting Zhang | 2 | 266 | 10.10 |