【招待ショートサーベイ】
直積量子化を用いた近似最近傍探索
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

[IBIS2011 企画セッション プレビュー] 大規模最適化および