LSHスキームによるスキームによる最近傍探索による最近傍探索アルゴリズム
最近傍探索アルゴリズムのいくつかのアルゴリズムのいくつかの変形のいくつかの変形と変形と高性能化

小林 卓夫 清水 郁子 東京農工大学

2008.11.6{ tkobaya, ikuko } @cc.tuat.ac.jp

目的と目的とアプローチ

LSH

スキームによるスキームによるANNSアルゴリズムのアルゴリズムの基本形

H ∈ F : ハッシュ関数の族，sim : 適当な類似度関数に対して，sim( x, y ) = Pr( H ( x) = H ( y ))となるとき， max{sim(q, p )} である p が q の最近傍である．

スキームによるスキームによる近似最近傍探索による近似最近傍探索(ANNS)アルゴリズ
ムの派生形を派生形を作成し作成し，高性能な高性能なアルゴリズムをアルゴリズムを実現する実現する．
する．
性能の性能の良いハッシュ関数
ハッシュ関数の関数の選択．
選択．
高次元の高次元の球面空間における球面空間におけるANNS問題を問題を対象とする対象とする．とする．

LSH

派生アルゴリズム
派生アルゴリズムのアルゴリズムの作成

ii

探索アルゴリズム : ∑ψ ( H (q) = H ( p )) ≥ 1 である { p } に対して，max{d (q, p )} を計算する．
Lii

ここで，ψ (Q) = 1(Q is true), 0 (Q is false) とする．

ハッシュ関数
ハッシュ関数の関数の作成

P = { pi } : prototypes, q : query,x = ( x1 , K, xd )P( q, k ) : a set of k closest point(s) in P from q

Algorithm - (A1, A2)で用いるハッシ ュ関数 :から半径 r 以内の P の点の集合
A = {a } : 適当な点集合

il =1

アルゴリズムのアルゴリズムの作成
P ( q; r ) : qアルゴリズム－Ａアルゴリズム－Ａ２－Ａ２ (k =8, k =2)qのとき，qA(q, k q )A( p, k p )H ( x ) = sign( x1 ) K sign( xd ' )⇓Algorithm - (B2)で用いるハッシュ関数 :(A2) : sim( q, pi ) = Pr( A(q, k q ) I A( pi , k p ) ≠ φ )アルゴリズム－Ｂ
アルゴリズム－Ｂ２－Ｂ２ (k =2, k =8)とする．

q{}.
ただし， v ∈ R に対して，a s.t. min E[d (v, a )] とするとき
Pr (P(v,1) ∈ P(a , k ) ) ≥ α となるようにd ' を決定する．

(B1) : sim( q, pi ) = Pr( A(q; rq ) I A( pi ; rp ) ≠ φ )Rh = x h = sign( xk1 )k1 K sign( xkd ' )k d '⇓∀qhU P ( a h ; rp ) )hah ∈A ( q ; rq )⇓U P(a , k ) )pP ( ah , k p )A( q, k q )

v∈Rh

hhh

p

ah| xk1 |>| xk2 |> K >| xkd ' |> K >| xkd |⇓(B2) : sim( q, pi ) = Pr( pi ∈piA( x,1) = { ( sign( x1 ),K, sign( xd ' )) },(A1) : sim( q, pi ) = Pr( A(q,1) I A( pi ,1) ≠ φ )(B1' ) : sim( q, pi ) = Pr( pi ∈pah

A = {ah } = {−1,+1}d ' (1 ≤ d ' ≤ d )h改訂ppia h ∈ A( q , k q )評価

乱数により乱数により人工的により人工的に人工的にテストデータをテストデータを生成し生成し，実験を実験を行う．
探索精度
探索精度の精度の定義：
定義：探索プログラム
探索プログラムがプログラムが返す点集合を点集合をCANDとするとき，とするとき，探索精度 α := E[ | P(q, k ) I CAND | | P(q, k ) | ]
評価項目：
探索精度，探索時間，探索時間，メモリサイズ
評価項目： 探索精度，ファクター：ファクター：次元数，次元数，プロトタイプ数
プロトタイプ数，分布型，分布型，パラメータ (kq, kp, A)
Kd-treeによるプログラム
によるプログラム ANN Library と性能を性能を比較．
比較．

実験環境：実験環境：データのデータの生成方法：
生成方法：x :正規分布乱数，σ :標準偏差，T:ランダムな直交行列
v = T×(σ x ) , u = v/|v|
σ =1 (uniform), σ = i (skewed)(A2)はkqを増加させることにより増加させることにより探索性能させることにより探索性能が探索性能が向上する
向上する場合する場合がある
場合がある．
がある．また，また，必要メモリサイズが既存手法と比べて，べて，大きメモリサイズが大幅に大幅に減少できる減少できる．
できる．(A1),(A2)は，既存手法とい次元(d≧20)・プロトタイプ数プロトタイプ数で特に効果が効果が高い．
(B2)はANNと比べて著べて著しい性能向上効果
しい性能向上効果が性能向上効果が確認できた確認できた．
できた．しかし非常
しかし非常に非常に大きいメモリサイズをメモリサイズを必要とする必要とする欠点とする欠点がある
欠点がある．
がある．比較的小さい比較的小さい次元数さい次元数(d≦15)に適用できると思できると思われる．
われる．
ii i

Dell VOSTRO-200, Intel Pentium Dual CPU E2160 1.80GHz, 3.24GB RAM, MS
Windows XP Professional Ver.2002 SP2,
C++(MS-C/C++ v.12)

プログラム言語
プログラム言語：言語：

Algorithm-A1,A2

探索
精度と探索
時
間の関係
探索
精度とメ
モリ
サイズの関係(dim=20, #of proto=1048576, distr.=skewed)
8iti

Algorithm-A1,A2

Algorithm-B2(dim=20, #of proto=1024, distr.=uniform)(dim=10, #of proto=1024)
0.010

0.08

ANN Library (KD-Tree)

7proposed (kq=8 kp=1)

6ANN Library
proposed (kq=1 kp=1)
proposed (kq=8 kp=1)

0.07

proposed (kq=1 kp=1)

0.06

50.009)sm(e0.04
im
t

2

0.02

10.01

000.007) 0.006sm(0.005eim
t0.004

0.03

0.6

0.7

0.8

0.9

precision

1800

0.003
0.002
0.001
0.000
0.7

1.0

0.75

0.8

0.85

0.9

precision

0.95

1

0.30

1600

kq=1 kp=1
kq=8 kp=1

1400

0.5

0.6

0.7

precision

0.8

10000000eizsle1000000
bat

100000

kp=10 α=0.9
kp=20 α=0.9
kp=30 α=0.90.05

200
0
0.3

0.4

0.5

0.6

0.7

precision

0.8

0.9

1.0

1.0100000000)
B0.20
M(eiz 0.15sleba
t 0.10400

0.9kq=1 kp=1kq=8 kp=10.25)1200
B
M(
1000eizs800
lebat 600

ANN Library
Proposed

0.008

0.05)
sm
(4eimt3

i

0.00
0.5

0.6

0.7

precision

0.8

0.9

1.0

10000
0.5

0.6

0.7

precision

0.8

0.9

1.0