FIT2010（第 9 回情報科学技術フォーラム）D-008
ŀkÛĊ łį3÷ö Pivot ĴÄÀå ¢ŁĢq
Empirical Evaluation of Pivot Selection Methods for Fast Similarity Search  1   2 "  3   3Hisashi Kurasawa Daiji Fukagawa Atsuhiro Takasu Jun Adachi

1. ŀkÛĊ!Ńė8L?69F `.97Wk
8L?69F3ÆÂę0ńŀkÛĊ!óvÛĊ+E
ZCOZ@ 9WZHY:Ý5X<WAQ łį±ăń¾!ĨľĂĹ(RFWD9ĂĹ)Á0Ĩľ(ŀk®)3¤ħŀkÛĊ łį3÷ÅŃŀkÛĊĊ° ûāĸõ/č40ńÕĊ°!Ĩľzð3êŀk®$3¤ħŃO9FXĹ UZ9WDGĨľ+ÌĹ ĐĽĨľ3Á0ńŀkÛĊĊ°!Ń\ğ_ą¯ Ĩľ zð3òŃ8L?69Fē `.97W.Ĩľ ĳ8L?
69F3ŃÙ/0 ò10ńŀkÛĊĊ°!ŃÙ108L?69F %ÛĊÑõñ0ĨľĠĆ;@F3Ã.1ŃÏ ÛĊ 0ń
ŀkÛĊĊ°Ń Pivot "10ì8L?69F. ĨľŃĊ°¤ħ 8L?69FĽ3|«öĵ~BDF
~0Ċ°g Àå ò.10[1]ń´ÖÀå!Ń Pivot !ĂĹ ĄlĒ08L?69F3Ĵ#ĎŁ[2]+8L?69F ~ª 9V@CÜİ[3]3*ĴÄ1ń .Ń1 Àå*í¡~ª38L?69F (Ø /Ńäò¸ßń'/ŃUZ>!Á8L?69F ~ª3(Ń13µ¼0Ċ°Àå3Ĵ"".ń Ń¾!.,0~ª 8L?69FØöŀkÛĊĊ°Ń Pivot Capacity Tree (PCTree)3ÇÚ[2]ń
ÑŃ¾!~ª í¶3Ħ$0)Ń Pivot ~Ĩľ¤0Ċ°Ô IVY@&ØÛĊÑ Ù/&Ø ĢqĺËŃ Pivot Capacity (PC)3¡Ĕń PCTree !Ń PC 3Ò0 Pivot 8L?
69FĽ3|«ö~ŃÔÜİ Ċ°3ÜĈ0ń
ÕĀ! PCTreeĉĥÐ ³ŃĊ°¸ĖĢq¢Ł ďØ3Če0ń¢Ł!Ńd©öñ½
O9FXEZC fŃyĘûā ¢Łò.1 3  ¢EZC3oŃÛĊÑõñ0ĨľĠĆ;@F3éń1 EZC¤*ÇÚÀå!łį
ÛĊ 0 3ýń

2. Pivot Capacity Tree
PCTree !.,0~ª 8L?69F¤łįŀkÛĊ3¢Ę0 3÷öĊ°Àå0ń

2.1 Pivot CapacityPCTreePivot 3ĴÄ0ļì0ĢqĺËPCĭ$0ń PC !Îú 97W~ª¤Ó²
0Ċ°¸Ė3Ěń PC !8L?69FĽ Pivot 1 ×c  The University of Tokyo2 ·þ  Doshisha University
3 ăº ûā¿ National Institute of Informatics

 1 Pivot Capacity ) ĂĹ~Ĩľ. 2 ÿŀ üîË3ĠĆŃ øbºķ.¥ ń!ŃĨľĂĹ M=(D,d) Pivot p ~Ĩľ rpD '10ĵ~ĂĹ R 3 2 ~0»¡0ńŃÕĀ!97W ~ª!8L?69
F ~ª[ * i¡0ń
Ċ°Ô IVY@ üîËp  rp - R ~1 2  ĵ~ĂĹ!Ń

R1( p,rp ) = {o " R | d(o,p) # rp },R2( p,rp ) = {o " R | d(o,p) > rp },Ě0ń¾!Ńĕ3 Inside region Ń³ĕ3 Outsideregion #ńŃ97W q ¨0ĵ~ĂĹüîË X Ěń q
R1(p,rp) Ń R2(p,rp)¨0 3
11 X1,p,rp Ń X2,p,rp 0ń SR 3 R '108L?
69FĽ0Ń X  üî!ŃP(X1, p, rp ) =| SR1 (p, rp ) || SR |,P(X 2, p, rp ) =| SR 2(p, rp ) || SR |,Ě0ńÙ/ üîË
 8L?69FĽ S 8L?69F o . k Ĭuë' Ĩľ ro,k,S ¡Ĕ0ń 13oŃ R 3h^ 3 ĵ~ĂĹ~ 0ń

R'1 ( p,rp ,k) = {o " R | d(o,p) + ro, k, S # rp},R'2 ( p,rp ,k) = {o " R | d(o,p) # ro, k, S > rp},R'3 ( p,rp ,k) = R " R'1 ( p,rp ,k) " R'2 ( p,rp ,k).

¾! 1.3Ŀ Inside-safe region Ń Outside-safe region ŃBoundary region #ń 1.ĵ~ĂĹ!ŃÛĊÑÙ
10ć Ĳ3Ě0ń{nö!Ń97W qInside-safe region ¨0 Ń k Ĭuë3ÛĊ0ļ
Outside region '108L?69FĽ3Ù10ń109（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）ÝŃ q Outside-safe region ¨0 ! Inside region'108L?69FĽ3Ù10ń q
RÕ1(p,rp) ŃRÕ2(p,rp) Ń RÕ3(p,rp)  ĂĹ¨03üîË Y 
Y1,p,rp Ń Y2,p,rp Ń Y3,p,rp ĚŃ üî3ã)0ŃP(Y1, p, rp ) =| SR '1 (p, rp ) |P(Y3, p, rp ) =,| SR || SR ' \3 (p, rp ) || SR |0ń
Pivot Capacity
 pivot p PCP(Y2, p, rp ) =,| SR ' 2 (p, rp ) || SR |,ĠĆt!Ń I(;)3øbºķ0Ń

PCk ( p) " max I(X;Y )4. rp¡Ĕń 1!ŃaxæĮrĩSEX0ń

2.2 Įrĩ£ķÝ PCTree Ċ°g !Ń8L?69FĽ¤ PCt3Ò08L?69F3 Pivot ġ¡Ń 2  ĵ~Ľ~0 3|«ö¢ĘŃÔÜİ Ċ°
3ÜĈ0ń Pivot 3Ĵ#ÀĿ3ĻĊ°g Àå!ŃyĘûā VPT[2]0ńĊ°g ;@Fè3÷ö Pivot sě =YMWY:Àå![4]3ì1ń ÛĊ}ð!Ń97W Pivot  Ĩľ3*\ğ_ą¯Ċ°Ô ÆĊ3Ù/0ń 1* VPT ÀĿ0ńÕĀ!ģċ!ùô0ń

3. 

! LC w1¸Ė3õÈ0  20ń SAT
ÛĊ;@F!àxË 2.%&2. ŃfÀå-/* ń 1¤Ń PCTree !àxË2.¬ÛĊ;@FèÒ*Ø3õÈ0  20ń ¢EZC3ò¢Ł!Ń 3  5 ! MVP Ń
4 ! LC¸Ė Ċ° Ø3õÈ0ń GHT !
NASA EZCŃ SAT ! Corel EZC¤¸Ė
¹ń[ÍŃ PCTree !1 EZC¤*fÀå3]0¸Ė0  20ń1-/ŃÇÚÀå
PCTree !EZC ~ª2.ŀkÛĊ łį3¢ï 0  üĤ ń!

¢Ł!Ńh^ EZCBDF3oòń¥ d©O9FXŅ 2 . 64 àxŃ9V@CË 100 Ń~Êt
0.02 çáĞ~ªŃ 100,000 jń¥ NASA Ņ 20 àx J@F:VQEZCŃ 40,150 jń¥ Corel Image Datasets Ņ 32 àx óvJ@F:VQEZCŃ
68,040 jń¥ PTYNY óvEZCBDFŅ 112 àx J@F:VQEZCŃ 112,544 j
1*UZ9WDGĨľ3ŀk®ŃEZCBDF~ªĶĜ  1,000 j397Wòńâī À å  ! Ń Metric Space Library[5]  Ç p  1   0
GHT[6]Ń MVP[7]Ń LC[8]Ń SAT[9]3oòńâīÀåĉČe0Ń GHT !8L?69
FĽ ~ 2  Pivot 3oÀå0ń MVP !
VPT ÉÀåŃ 1  Pivot 8L?69FĽ3 2h] ĵ~Ľ~0Àå0ń LC ! Pivot -¦ĵ~Ľ~0W@FÜİ Ċ°/Ń
SAT !:VKÜİ Ċ°0ńÀå Ģq§®![9]
ÝŃÛĊ¢ĘÑñ0ĨľĠĆ Ë3òń¢Ł
ďØ!97W 1,000 j ­t0ńďØ  đĪ!
Na•ve  Sequential Scan 3¢Ęļ ĨľĠĆË3 1
â3Ě0ń 2 ÞĪ!àxË3Ń
3 . 5 ÞĪ!97W ĝã0Ĭu8L?69FË3Ě0ń
  2 . 5 !11 EZCBDF¤0ďØ3ý0ń 2 .màx! MVP + GHT ŃłàxÕĀ!ŃĨľĂĹ3¤ħŀkÛĊĊ°Ń PCTreeĭ$ńd©EZC 3  ¢EZC3ò¢ŁďØ-/Ń PCTree !ĺıûāâīŃ.,0~ª 8L?69F¤ÛĊ;@F èØöĊ°
0 3üĤ ń
[1]P.Zezula, et al. Similarity Search: The Metric Space Approach.
Springer-Verlag, (2005).
[2]P.N.Yianilos. Data Structure and Algorithms for Nearest Neighbor
Search in General Metric Spaces. In SODA, (1993).
[3]H.V.Jagadish, et al. iDistance: An Adaptive b+-tree based Indexing
Method for Nearest Neighbor Search. ACM Trans. On Database
Systems, Vol.30, No.2, (2003).
[4]H.Kurasawa, et al. Pivot Selection Method for Optimizing bothPruning and Balancing in Metric Space Indexes. In DEXA, (2010).
[5]MetricSpaceLibrary,
http://www.sisap.org/Metric_Space_Library.html.
[6]J.K.Uhlman. Satisfying General Proximity / Similarity Queries with
Metric Trees. Information Processing Letters, Vol.40, No.4, (1991).
[7]T.Bozkaya, et al. Indexing Large Metric Spaces for Similarity SearchQueries. ACM Trans. On Database Systems, Vol.24, No.3, (1999).
[8]E.Chevez, et al. A Compact Space Decomposition for Effective
Metric Indexing. Pattern Recognition Letters, Vol.24, No.9, (2005).
[9]G.Navarro. Searching in Metric Spaces by Spatial Approximation.
The VLDB Journal, Vol.11, No.1, (2002).

 2 d©O9FX      3 NASA

 4 Corel Image Datasets   5 PTYNY

110（第2分冊）