【招待ショートサーベイ】 直積量子化を用いた近似最近傍探索 2016/9/5, PRMU研究会@富山 松井勇佑 国立情報学研究所 1 近似最近傍探索 Query 0.34 0.22 0.68 Nearest? 1.02 0.03 0.71 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … 13 2 近似最近傍探索 Query 0.34 0.22 0.68 Nearest? 1.02 0.03 0.71 ∗ 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … 𝑛 = arg min 𝒒 − 𝒙𝑛 13 2 1≤𝑛≤𝑁 3 近似最近傍探索 Query 0.34 0.22 0.68 Nearest? 1.02 0.03 128 0.71 ∗ 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … 𝑛 = arg min 𝒒 − 𝒙𝑛 13 2 1≤𝑛≤𝑁 4 近似最近傍探索 Query 0.34 0.22 0.68 Nearest? 1.02 0.03 128 0.71 ∗ 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … 𝑛 = arg min 𝒒 − 𝒙𝑛 9 10 13 2 1≤𝑛≤𝑁 5 近似最近傍探索 Query 0.34 0.22 0.68 Nearest? 1.02 0.03 128 0.71 ∗ 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … 𝑛 = arg min 𝒒 − 𝒙𝑛 9 10 13 2 1≤𝑛≤𝑁 10 ms 6 近似最近傍探索 Query 0.34 0.22 0.68 Nearest? 1.02 0.03 128 0.71 ∗ 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … 9 10 𝑛 = arg min 𝒒 − 𝒙𝑛 13 2 1≤𝑛≤𝑁 10 ms 32GB RAM 7 近似最近傍探索 Locality Sensitive Hashing (LSH)系 Tree系 etc. (e.g., FLANN [Muja, PAMI 14]) ショートコード系 バイナリハッシュ 0.34 0.22 0.68 1.02 0.03 0.71 0 1 0 1 0 0 直積量子化 (PQ) 0.34 0.22 0.68 1.02 0.03 0.71 ID: 2 ID: 123 ID: 87 8 近似最近傍探索 メモリ消費大 Locality Sensitive Hashing (LSH)系 Tree系 (e.g., FLANN) etc. ショートコード系 バイナリハッシュ 0.34 0.22 0.68 1.02 0.03 0.71 0 1 0 1 0 0 直積量子化 (PQ) 0.34 0.22 0.68 1.02 0.03 0.71 ID: 2 ID: 123 ID: 87 9 近似最近傍探索 メモリ消費大 Locality Sensitive Hashing (LSH)系 Tree系 (e.g., FLANN) etc. ショートコード系 シンプル バイナリハッシュ 探索が高速 0.34 0.22 0.68 1.02 0.03 0.71 0 1 0 1 精度劣る 0 0 直積量子化 (PQ) 0.34 0.22 0.68 1.02 0.03 0.71 ID: 2 ID: 123 ID: 87 10 近似最近傍探索 メモリ消費大 Locality Sensitive Hashing (LSH)系 Tree系 (e.g., FLANN) etc. ショートコード系 シンプル バイナリハッシュ 探索が高速 0.34 0.22 0.68 1.02 0.03 0.71 0 1 0 1 精度劣る 0 0 直積量子化 (PQ) 0.34 0.22 0.68 1.02 0.03 0.71 ID: 2 ID: 123 ID: 87 11 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 12 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 13 Product Quantization [Jégou, TPAMI 2011] ベクトルを分割してk-meansする k-means assign Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 Compressed code 𝑀 1.03 0.08 14 Product Quantization [Jégou, TPAMI 2011] ベクトルを分割してk-meansする k-means assign Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 Compressed code 𝑀 1.03 0.08 15 Product Quantization [Jégou, TPAMI 2011] ベクトルを分割してk-meansする k-means assign Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 Compressed code ID: 2 𝑀 1.03 0.08 16 Product Quantization [Jégou, TPAMI 2011] ベクトルを分割してk-meansする k-means assign Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 Compressed code ID: 2 ID: 123 𝑀 1.03 0.08 17 Product Quantization [Jégou, TPAMI 2011] ベクトルを分割してk-meansする k-means assign Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 Compressed code ID: 2 ID: 123 ID: 87 𝑀 1.03 0.08 18 Product Quantization [Jégou, TPAMI 2011] ベクトルを分割してk-meansする k-means assign Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 Compressed code ID: 2 ID: 123 ID: 87 𝑀 1.03 0.08 単純 メモリ効率良い 距離 𝑑 𝑖𝑛𝑝𝑢𝑡, 𝑐𝑜𝑑𝑒 2 を近似計算可能 19 Product Quantization: メモリ効率良 Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 k-means assign Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 Compressed code ID: 2 ID: 123 ID: 87 𝑀 20 Product Quantization: メモリ効率良 Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 k-means assign Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 Compressed code ID: 2 ID: 123 ID: 87 𝑀 float: 32bit e.g., 𝐷 = 128 128 × 32 = 4096 [bit] 21 Product Quantization: メモリ効率良 Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 k-means assign Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 Compressed code ID: 2 ID: 123 ID: 87 𝑀 uchar: 8bit float: 32bit e.g., 𝐷 = 128 128 × 32 = 4096 [bit] e.g., 𝑀 = 8 8 × 8 = 64 [bit] 22 Product Quantization: メモリ効率良 Input vector 𝐷 0.34 0.22 0.68 1.02 0.03 0.71 k-means assign Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 Compressed code ID: 2 ID: 123 ID: 87 𝑀 uchar: 8bit float: 32bit e.g., 𝐷 = 128 128 × 32 = 4096 [bit] e.g., 𝑀 = 8 8 × 8 = 64 [bit] 1/64に圧縮 23 Product Quantization: 距離近似 Query 0.34 0.22 0.68Nearest? 1.02 0.03 0.71 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … 24 Product Quantization: 距離近似 Query 0.34 0.22 0.68Nearest? 1.02 0.03 0.71 1 2 N 0.54 2.35 0.82 0.42 0.14 0.32 0.62 0.31 0.34 1.63 1.43 0.74 3.34 0.83 0.62 1.45 0.12 2.32 … Product quantization 25 Product Quantization: 距離近似 Query 0.34 0.22 0.68 1.02 0.03 0.71 1 ID: 42 ID: 67 ID: 92 2 N ID: 221 ID: 143 ID: 34 ID: 99 ID: 234 ID: 3 … 26 Product Quantization: 距離近似 Query 0.34 0.22 0.68 1.02 0.03 0.71 1 線形 探索 ID: 42 ID: 67 ID: 92 2 N ID: 221 ID: 143 ID: 34 ID: 99 ID: 234 ID: 3 … (近似的距離で)線形探索が出来る 27 Product Quantization: 距離近似 Query vector 𝐷 0.22 0.31 1.33 1.87 0.57 0.01 k-means assign Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ 28 Product Quantization: 距離近似 Query vector 𝐷 0.22 0.31 1.33 1.87 0.57 0.01 k-means assign Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ 29 Product Quantization: 距離近似 k-means assign Codebooks Query vector 𝐷 ID: 1 0.22 0.31 1.33 1.87 0.57 0.01 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ Distance table 1 1 2 3 2 8.2 0.04 3.4 11.2 0.31 1.1 ⋯ 256 2.1 5.5 2.4 30 Product Quantization: 距離近似 k-means assign Codebooks Query vector 𝐷 ID: 1 0.22 0.31 1.33 1.87 0.57 0.01 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 Distance table 1 1 2 3 2 8.2 0.04 3.4 11.2 0.31 1.1 ⋯ 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ Distance: 0.04 256 2.1 5.5 2.4 31 Product Quantization: 距離近似 k-means assign Codebooks Query vector 𝐷 ID: 1 0.22 0.31 1.33 1.87 0.57 0.01 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 Distance table 1 1 2 3 2 8.2 0.04 3.4 11.2 0.31 1.1 ⋯ 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ Distance: 0.04 + 0.23 256 2.1 5.5 2.4 32 Product Quantization: 距離近似 k-means assign Codebooks Query vector 𝐷 ID: 1 0.22 0.31 1.33 1.87 0.57 0.01 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 Distance table 1 1 2 3 2 8.2 0.04 3.4 11.2 0.31 1.1 ⋯ 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ Distance: 0.04 + 0.23 + 1.02 256 2.1 5.5 2.4 33 Product Quantization: 距離近似 k-means assign Codebooks Query vector 𝐷 ID: 1 0.22 0.31 1.33 1.87 0.57 0.01 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 Distance table 1 1 2 3 2 8.2 0.04 3.4 11.2 0.31 1.1 ⋯ 256 2.1 5.5 2.4 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ Distance: 0.04 + 0.23 + 1.02 = 1.29 34 Product Quantization: 距離近似 k-means assign Codebooks Query vector 𝐷 ID: 1 0.22 0.31 1.33 1.87 0.57 0.01 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 Distance table 1 1 2 3 2 8.2 0.04 3.4 11.2 0.31 1.1 ⋯ 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 Distance: 1.29 0.03 ⋯ 7.34 256 2.1 5.5 2.4 35 Product Quantization: 距離近似 k-means assign Codebooks Query vector 𝐷 ID: 1 0.22 0.31 1.33 1.87 0.57 0.01 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 Distance table 1 1 2 3 2 8.2 0.04 3.4 11.2 0.31 1.1 ⋯ 256 2.1 5.5 2.4 1.03 0.08 0.99 1.13 1.03 0.08 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ Distance: 1.29 0.03 7.34 早い: - Table lookup 計算量: 𝑂(𝐷𝐾 + 𝑀𝑁) 正確に近似: 𝑀 8 - 空間を 2 に分割 36 Product Quantization Query vector 𝐷 0.22 0.31 1.33 1.87 0.57 0.01 k-means assign Codebooks ID: 1 ID: 2 0.13 0.98 0.32 0.27 ID: 1 ID: 2 0.3 1.28 0.35 0.12 ID: 1 ID: 2 0.13 0.98 0.72 1.34 … ID: 256 … ID: 256 … ID: 256 1.03 0.08 0.99 1.13 1.03 0.08 単純 メモリ効率良い 距離 𝑑 𝑖𝑛𝑝𝑢𝑡, 𝑐𝑜𝑑𝑒 2 Compressed database codes 1 ID: 2 ID: 12 ID: 87 2 N ID: 45 ID: 8 ID: 42 ID: 65 ID: 7 ID: 72 ⋯ を近似計算可能 37 Product Quantization 非常に単純 38 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 39 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] PQそのもの の発展 新しい問題設定 高速符号化 [Zhang, CVPR 15] 教師付き [Wang, CVPR16] 「ベクトルの分割」が単純すぎないか? 疎量子化の工夫 その他トピック 事前にベクトルを“回転”させ, 分割したときのエラーを最小にする マルチモーダル [Zhang, CVPR16] 疎量子化: k-means リランキング: 残差PQコード 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] ジャーナル版 1) 𝒙 ← 𝑅𝒙 2) 𝒙にPQ 列挙の高速化 [Iwamura, ICCV 13] 残差量子化 [Babenko, CVPR 16] 余分ビット [Heo, CVPR 14] OPQ+local codebook [Babenko, TPAMI 15] このときの誤差が GPU [Wieschollek, CVPR 16] 最小となるように リランキングの工夫 二段階 [Jégou, ICASSP 11] local codebook [Kalantidis, CVPR 14] リランキング側残差考慮 [Heo, CVPR 16] ハッシュテーブル [Matsui, ICCV 15] キャッシュ [André, VLDB 15] 回転行列𝑅を求める PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 40 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 41 元論文 事前変換 各次元を複数 コードブックで表す Cartesian k-means PQは𝒙をM個のD/M次元 [Norouzi CVPR 13] PQそのもの 同じ コードワードで表した [Jégou, TPAMI 11] PQを使った 0.22 探索システム 0.31 1.33 1.87 0.57 0.01 ∼ 疎量子化: k-means 0.32 0.27 𝟎 Optimized Cartesian kmeans [Wang, TKDE 14] Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] 𝟎 + 1.19 1.66 + 𝟎 𝟎 一般化 Additive quantization [Babenko, CVPR 14 ] 0.32 1.10 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化の工夫 リランキング: AQ・CQはM個のD次元 複数k-means [Xia, ICCV 13] 残差PQコード ジャーナル版 コードワードで表す PQ [Babenko, CVPR 12] 0.22 0.31 1.33 1.87 0.57 0.01 Tree quantization [Babenko, CVPR 15] 新しい問題設定 高速符号化 [Zhang, CVPR 15] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] その他トピック 余分ビット [Heo, CVPR 14] OPQ+local codebook [Babenko, TPAMI 15] 0.02 0.02 0.19 0.13 0.02 CVPR 0.20 残差量子化 [Babenko, 16] 0.31 0.56 0.42 + + 0.01 リランキングの工夫 1.02 0.33 0.23 二段階 [Jégou, ICASSP 11] 0.66 0.12 0.01 0.10 0.00 local codebook [Kalantidis, CVPR 14] PQを使った PQの一般化.表現能力高い 列挙の高速化 [Iwamura, ICCV 13] ∼ リランキング側残差考慮 [Heo, CVPR 16] PQそのもの の発展 探索システムの発展 ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] キャッシュ [André, VLDB 15] 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 42 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 43 元論文 CQ: [Jégou, TPAMI 11] PQそのもの 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Given トレーニングデータ, Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] PQを使った 探索システム min コードブック CQコード CQの コスト項 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] CQ+別の問題: 疎量子化: k-means Tree quantization [Babenko, CVPR 15] 疎量子化の工夫 Given トレーニングデータ, リランキング: min CQの コスト項 別の コスト項 列挙の高速化 [Iwamura, ICCV 13] PQ [Babenko, CVPR 12] コードブック CQコード その他変数 + ジャーナル版 新しい問題設定 高速符号化 [Zhang, CVPR 15] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] その他トピック 複数k-means [Xia, ICCV 13] 残差PQコード PQそのもの の発展 余分ビット [Heo, CVPR 14] OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] 交互最適化 リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] 辞書を疎ベクトルに→量子化を高速化 local codebook [Kalantidis, CVPR 14] ラベルを当てる線形分離変換→教師付き探索 PQを使った 画像と文章を同じ空間に変換→マルチモーダル リランキング側残差考慮 [Heo, CVPR 16] 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 44 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 45 元論文 事前変換 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 各次元を複数 コードブックで表す 転置インデクスとPQを組合わせた探索システム Optimized Cartesian kCartesian k-means PQそのもの means [Wang, TKDE 14] [Norouzi CVPR 13] 疎量子化でざっくりバケットに分け, 同じ Tree quantization の発展 [Babenko, CVPR 15] PQコードにリランキング Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] 高速高精度省メモリ一般化 新しい問題設定 245 12 Additive quantization [Babenko, CVPR 14 ] ID: 42 立式が同じ ID: 37 疎量子化: k-means リランキング: 残差PQコード 0.22 0.31 疎量子化の工夫 1.33 疎量子化 複数k-means 1.87[Xia, ICCV 13] ジャーナル版 0.57 CVPR 12] PQ [Babenko, 0.01 列挙の高速化 [Iwamura, ICCV 13] ID: 38 ID: 16 ID: 47 ID: 49 ID: 72 教師付き [Wang, CVPR16] Composite quantization ID: 9 ID: 32 マルチモーダル ID: 72 ID: 95 CVPR16] [Zhang, [Zhang, ICML 14] 1721 3721 ID: 24 ID: 18 OPQ+local codebook ID: 87 [Babenko, TPAMI 15] ID: 49 ID: 4 ID: 96 オリジナル論文では 8621 疎量子化:k-means 二段階 [Jégou, ICASSP 11] リランキング: ID: 24 local codebook [Kalantidis, CVPR 14] バケット中心ベクトル PQを使った ID: 54 リランキング側残差考慮 [Heo, CVPR 16] ID: 23 との残差をPQ 探索システムの発展 リランキングの工夫 1721 ID: 25 … 残差量子化 [Babenko, CVPR 16] 1932 高速符号化 [Zhang, CVPR 15] 145 その他トピック 余分ビット [Heo, CVPR 14] リランキング ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] 1721キャッシュ [André, VLDB 15] ID: 77 ID: 32 ID: 21 ID: 11 [Jégou, PAMI 12] ID: 5 画像検索システム [Spyromitros-Xioufis, TMM 14] ID: 85 46 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 47 元論文 事前変換 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 0.22Cartesian k-means 0.31[Norouzi CVPR 13] 1.33 同じ 疎量子化 1.87 Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] 0.57 0.01 各次元を複数 コードブックで表す Optimized Cartesian kmeans [Wang, TKDE 14] 1721 3721 ID: 24 ID: 18 ID: 87 一般化 ID: 4 ID: 49 Additive quantization [Babenko, CVPR 14 ] ID: 96 Tree quantization [Babenko, CVPR 15] 疎量子化でもPQを使う 立式が同じ 近いバケットを「列挙」する Composite quantization [Zhang, ICML 14] 速度・精度のバランスが良い 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] リランキング 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 48 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 49 元論文 事前変換 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 0.22Cartesian k-means 0.31[Norouzi CVPR 13] 1.33 同じ 疎量子化 1.87 Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] 0.57 0.01 各次元を複数 コードブックで表す Optimized Cartesian kmeans [Wang, TKDE 14] 1721 3721 ID: 24 ID: 18 ID: 87 一般化 ID: 4 ID: 49 Additive quantization [Babenko, CVPR 14 ] ID: 96 Tree quantization [Babenko, CVPR 15] PQそのもの の発展 リランキング 新しい問題設定 高速符号化 [Zhang, CVPR 15] 教師付き [Wang, CVPR16] 立式が同じ 全てのバケットで同じコードワードを使う Composite quantization マルチモーダル [Zhang, CVPR16] のではなく,バケットごとに学習する [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] ジャーナル版 余分ビット [Heo, CVPR 14] OPQ+local codebook [Babenko, TPAMI 15] 列挙の高速化 [Iwamura, ICCV 13] 残差量子化 [Babenko, CVPR 16] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] local codebook [Kalantidis, CVPR 14] リランキング側残差考慮 [Heo, CVPR 16] ハッシュテーブル [Matsui, ICCV 15] PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 50 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 新しい問題設定 Additive quantization [Babenko, CVPR 14 ] 高速符号化 [Zhang, CVPR 15] 立式が同じ 教師付き [Wang, CVPR16] Composite quantization [Zhang, ICML 14] 疎量子化: k-means PQそのもの の発展 マルチモーダル [Zhang, CVPR16] 疎量子化の工夫 リランキング: 残差PQコード その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] ジャーナル版 余分ビット [Heo, CVPR 14] OPQ+local codebook [Babenko, TPAMI 15] ハッシュテーブル [Matsui, ICCV 15] 列挙の高速化 [Iwamura, ICCV 13] 残差量子化 [Babenko, CVPR 16] GPU [Wieschollek, CVPR 16] リランキングの工夫 二段階 [Jégou, ICASSP 11] local codebook [Kalantidis, CVPR 14] リランキング側残差考慮 [Heo, CVPR 16] 0.22 0.31 1.33 1.87 0.57 0.01 1721 疎量子化 PQを使った ID: 87 探索システムの発展 OPQ ID: 49 ID: 24 3721 キャッシュ [André, VLDB 15] 画像検索システム ID: 18 [Jégou, PAMI リランキング 12] [Spyromitros-Xioufis, TMM 14] ID: 4 ID: 96 OPQ local 51 codebook 元論文 [Jégou, TPAMI 11] PQそのもの PQを使った 探索システム 事前変換 各次元を複数 コードブックで表す Cartesian k-means [Norouzi CVPR 13] Optimized Cartesian kmeans [Wang, TKDE 14] 同じ Optimized PQ [Ge, CVPR13][Ge, TPAMI 14] Tree quantization [Babenko, CVPR 15] 一般化 Additive quantization [Babenko, CVPR 14 ] 立式が同じ Composite quantization [Zhang, ICML 14] 疎量子化: k-means 疎量子化の工夫 リランキング: 残差PQコード ジャーナル版 OPQ+local codebook [Babenko, TPAMI 15] 残差量子化 [Babenko, CVPR 16] 教師付き [Wang, CVPR16] マルチモーダル [Zhang, CVPR16] ハッシュテーブル [Matsui, ICCV 15] GPU [Wieschollek, CVPR 16] リランキングの工夫 キャッシュ [André, VLDB 15] 二段階 [Jégou, ICASSP 11] リランキング側残差考慮 [Heo, CVPR 16] 高速符号化 [Zhang, CVPR 15] 余分ビット [Heo, CVPR 14] 列挙の高速化 [Iwamura, ICCV 13] local codebook [Kalantidis, CVPR 14] 新しい問題設定 その他トピック 複数k-means [Xia, ICCV 13] PQ [Babenko, CVPR 12] PQそのもの の発展 PQを使った 探索システムの発展 画像検索システム [Jégou, PAMI 12] [Spyromitros-Xioufis, TMM 14] 52 参考文献 [Muja, TPAMI 14] M. Muja and D. G. Lowe: “Scalable nearest neighbour algorithms for high dimensional data”, IEEE TPAMI (2014). [Jégou, TPAMI 11] H. Jégou, M. Douze and C. Schmid: “Product quantization for nearest neighbor search”, IEEE TPAMI (2011). [Norouzi, CVPR 13] M. Norouzi and D. J. Fleet: “Cartesian k-means”, CVPR (2013). [Ge, CVPR 13] T. Ge, K. He, Q. Ke and J. Sun: “Optimized product quantization for approximate nearest neighbor search”, CVPR (2013). [Ge, TPAMI 14] T. Ge, K. He, Q. Ke and J. Sun: “Optimized product quantization”, IEEE TPAMI, (2014). [Wang, TKDE 14] J. Wang, J. Wang, J. Song, X.-S. Xu, H. T. Shen and S. Li: “Optimized cartesian k-means”, IEEE TKDE (2014). [Babenko, CVPR 15] A. Babenko and V. Lempitsky: “Tree quantization for large-scale similarity search and classification”, CVPR (2015). [Babenko, CVPR 14] A. Babenko and V. Lempitsky: “Additive quantization for extreme vector compression”, CVPR (2014). [Zhang, ICML 14] T. Zhang, C. Du and J. Wang: “Composite quantization for approximate nearest neighbor search”, ICML (2014). [Zhang, CVPR 15] T. Zhang, G.-J. Qi, J. Tang and J. Wang: “Sparse composite quantization”, CVPR (2015). [Wang, CVPR16] X. Wang, T. Zhang, G.-J. Qi, J. Tang and J. Wang: “Supervised quantization for similarity search”, CVPR (2016). [Zhang, CVPR 16] T. Zhang and J. Wang: “Collaborative quantization for cross-modal similarity search”, CVPR (2016). [Xia, ICCV 13] Y. Xia, K. He, F. Wen and J. Sun: “Joint inverted indexing”, ICCV (2013). [Babenko, CVPR 12] A. Babenko and V. Lempitsky: “The inverted multi-index”, CVPR (2012). [Iwamura, ICCV 13] M. Iwamura, T. Sato and K. Kise: “What is the most efficient way to select nearest neighbor candidates for fast approximate nearest neighbor search?”, ICCV (2013). [Babenko, CVPR 16] A. Babenko and V. Lempitsky: “Efficient indexing of billion-scale datasets of deep descriptors”, CVPR (2016). [Babenko, TPAMI 15] A. Babenko and V. Lempitsky: “The inverted multi-index”, IEEE TPAMI, (2015). [Jégou, ICASSP 11] H. Jégou, R. Tavenard, M. Douze and L. Amsaleg: “Searching in one billion vectors: Re-rank with souce coding”, ICASSP (2011). [Kalantidis, CVPR 14] Y. Kalantidis and Y. Avrithis: “Locally optimized product quantization for approximate nearest neighbor search”, CVPR (2014). [Heo, CVPR 16] J.-P. Heo, Z. Lin, X. Shen, J. Brandt and S. eui Yoon: “Shortlist selection with residual aware distance estimator for k-nearest neighbor search”, CVPR (2016). [Heo, CVPR 14] J.-P. Heo, Z. Lin and S.-E. Yoon: “Distance encoded product quantization”, CVPR (2014). [Matsui, ICCV 15] Y. Matsui, T. Yamasaki and K. Aizawa: “Pqtable: Fast exact asymmetric distance neighbor search for product quantization using hash tables”, ICCV (2015). [Wieschollek, CVPR 16] P. Wieschollek, O. Wang, A. Sorkine-Hornung and H. P. A. Lensch: “Efficient large-scale approximate nearest neighbor search on the gpu”, CVPR (2016). [André, VLDB 15] F. André, A.-M. Kermarrec and N. L. Scouarnec: “Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan”, VLDB (2015). [Jégou, PAMI 12] H. Jégou, F. Perronnin, M. Douze, J. Sánchez, P. Pérez and C. Schmid: “Aggregating local image descriptors into compact codes”, IEEE TPAMI, (2012). [Spyromitros-Xioufis, TMM 14] E. Spyromitros-Xioufis, S. Papadopoulos, I. Y. Kompatsiaris, G. Tsoumakas and I. Vlahavas: “A comprehensive study over vlad and product quantization in large-scale image retrieval”, IEEE TMM, (2014). 53
© Copyright 2025 ExpyDoc