一般論文

DBSJDBSJ
Journal,Vol.11, No.3
Journal,Vol.
11, No.3

February 2013

February 2013

類似検索における逐次入れ替えによるピボット改善選択法

Improving Pivot Selection Techniques by
Iterative Swapping for Similarity Search

三津山 雅規† 斉藤 和巳‡
池田 哲夫‡ 大久保 誠也‡
武藤 伸明‡
Masaki MITSUYAMA Kazumi SAITO
Tetsuo IKEDA Seiya OKUBO
Nobuaki MUTOH
本論文では，類似検索を高速化させるための，Random In
Worst Out 法（以下，RIWO 法）に基づいたピボット集合の新構
築法を提案する．RIWO 法は，Local Optimum Selection 法の入れ替えるピボット集合の要素の選択方法を改良したものである．RIWO 法は，指定したサイズの良いピボット集合を高速に構成する．しかしながら，通常，与えられたデータベースの適切なピボット数は事前に知ることができない．本論文では，多様なデータに対して計算機実験をすることにより，ピボット数が既知の場合において，RIWO 法は従来手法と比較して，人工データ
では約 1/2，現実データでは約 1/7 以下の構成時間で同等のピボット集合を構成することを示す．また，RIWO 法に基づいた
RIWO-INC 法を提案し，計算機実験により，ピボット数が未知の場合において，RIWO-INC 法は従来手法と同程度の計算量
で，より良いピボット集合を構成することを示す．
We address the problem of selecting an adequate set ofpivot objects for similarity search, and propose a newtechnique referred to as RIWO (random in worst out),
which is an improved version of LOS (local optimum
selection) proposed by Bustos, et al. Here RIWO removes
the poorest pivot object after a random pivot selection,
while LOS removes it before a pivot selection. In addition,
we present RIWO-INC (RIWO-incremental) so as to copewith a problem setting that we need to incrementally
select the pivot objects. In our experiments using one
synthetic and two real data sets, we show that for given
numbers of pivot objects, RIWO could more efficiently
select better pivot sets, in comparison to LOS, as well as
existing INC (incremental) proposed by Bustos, et al. In
case of the incremental problem setting, we show thatRIWO-INC could select slightly better pivot sets incomparison to existing INC, bringing about comparable
computational load.

† 学生会員静岡県立大学大学院経営情報イノベーション
研究科修士課程 j11113@u-shizuoka-ken.ac.jp‡ 正会員 静岡県立大学大学院経営情報イノベーション研
究科 {k-saito, t-ikeda, s-okubo, muto}@u-shizuoka-ken.ac.jp

1．はじめに近年，インターネットの発達などにより，マルチメディア
データが大量に蓄積されているため，与えられたクエリから類似したオブジェクトを検索する類似検索の研究が重要になってきている．マルチメディアデータにおける，オブジェ
クトはメトリック空間あるいは多次元空間に存在している
ため，オブジェクト間の類似度を計算するにはかなりの計算時間が必要となる．類似検索を行うには，この計算を大量に行わなければならない．そのため類似検索では，その計算回数を削減し，検索を大幅に高速化させるために，一部のオブジェクトを選定して導くピボット集合（詳細は 2.2 節で述べる）を用いる方法が提案されている．
ピボット集合をランダムに構成しても検索を高速化できるが，より高速な検索を実現するピボット集合を構成する方法が存在する．Bustos らは，より良いピボット集合の指標として目的関数を定義し，貪欲法を用いてピボット集合にピボットを逐次追加することで目的関数値を最適化する
Incremental 法（以下，INC 法）を提案している．また，ピボット集合の要素を入れ替えることで目的関数値を改善させる Local Optimum Selection 法（以下，LOS 法）も提案している．そして，計算機実験により INC 法と LOS 法について，同程度の良いピボット集合が得られることを示している[1]．
ピボット集合は，通常，与えられた未知のデータベースに対して構成するため，経験的に類似したデータを扱った場合を除けば，適切なピボット数は事前に知ることができない．
ピボット数を調整する際，LOS 法は各ピボット数に対するピボット集合を再構築する必要があるが，INC 法では今まで求めたピボット集合にピボットを追加するだけで済む．したがって，ピボット数の調整が必要な状況では，INC 法が LOS
法よりも優れているといえる．
これらの手法は，静的なデータベースに対してピボット集
合を構成する手法であるが，Bustos らは，増加するデータベースに対して動的にピボット集合を構成可能な SSS 法[2]，Dynamic 法[3]を提案している．
我々は，これまでに静的なデータベースに対して，良いピボット集合を構成する手法を提案してきた．[4]では，Bustos
らの目的関数がサブモジュラという性質をもつことを証明
し，単純な貪欲法によるピボット集合の構成を遅延評価により高速化した．また，[5]では，新たな手法である Random In
Worst Out 法（以下，RIWO 法）を提案した．RIWO 法は，
LOS 法の入れ替えるピボット集合の要素の選択方法を改良したものである．そして初期実験により，ピボット数が 100の場合においては，INC 法よりも良いピボット集合を得られることを示した．
本論文では，多様なデータに対して計算機実験を行うこと
により，ピボット数が既知の場合において，RIWO 法が INC
法よりも高速に良いピボット集合を得られることを示す．また，RIWO 法に基づいた RIWO-INC 法を提案する．そして，計算機実験により，ピボット数が未知の場合において，
RIWO-INC 法は INC 法と同程度の計算量で，より良いピボット集合を構成することを示す．
本論文の構成は以下となる．2 節では，問題設定について述べる．3 節で従来手法，4 節で RIWO 法，及び RIWO-INC法の詳細とその主たる計算量について述べる．5 節では，人工データと現実データを用いた実験により，RIWO 法，及び

1―9―日本データベース学会論文誌 Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 年 No.3
2月
2013年 2月

一般論文

DBSJDBSJ
Journal,Vol.11, No.3
Journal,Vol.
11, No.3

February 2013

February 2013

RIWO-INC 法が従来手法よりも良いピボット集合が得られることを計算機実験により示す．6 節でまとめと今後の研究について述べる．

2．問題設定類似検索とは，クエリと類似したオブジェクトをデータベースなどの中から同定する問題を指す．オブジェクト間の類
似度は，距離関数により求まり，距離関数は，非負性，対称性，及び三角不等式の性質を満たす．この性質を基に多くの高速化技術が提案されている．高速化技術の多くは，ピボッ
ト集合を用いた手法，またはクラスタリングを用いた手法に分類できる．本論文では，ピボット集合を用いた手法を扱う．
ピボット集合を用いた類似検索は，大きく分けて次の2つのフェーズに分けられる．最初のフェーズは，ピボット集合を構成するフェーズであり，最初に1度だけ実行される．2
つ目のフェーズは，ピボット集合を用いて，与えられたクエリに対して類似したオブジェクトを求めるフェーズであり，クエリが与えられる度に実行される．類似したオブジェクトの検索をより高速化させるようなピボット集合を高速に構成することが本論文の課題である．

2.1 レンジクエリ

類似検索は，扱われるクエリにより，クエリから一定レンジ内にあるオブジェクトを全て列挙するレンジクエリ，クエリと最も類似したオブジェクトを同定する最類似検索，及びクエリの近傍にある個のオブジェクトを同定する k-NNなどに分けられる．本論文では，レンジクエリを扱う．
距離空間 (𝕏𝕏， ) 上のデータベース 𝒰𝒰 が与えられる．𝒰𝒰

は個のオブジェクト集合 𝒰𝒰{𝑢𝑢1 𝑢𝑢2

𝑢𝑢 |𝑢𝑢𝑛𝑛𝕏𝕏}である．レンジクエリは，クエリ 𝑞𝑞 𝕏𝕏 とレンジ 𝑟𝑟 が与えられたとき， 𝑞𝑞 と 𝑢𝑢 の距離 (𝑞𝑞 𝑢𝑢) が 𝑟𝑟 以下となる𝑟𝑟} を求める問𝑢𝑢
𝒰𝒰 の集合 ℛ(𝑞𝑞) {𝑢𝑢|𝑢𝑢
𝒰𝒰， (𝑞𝑞 𝑢𝑢)
題である.

2.2 ピボットを用いたレンジクエリ

マルチメディアデータなどでは，オブジェクト間の距離(𝑞𝑞 𝑢𝑢) を求めるためには，かなりの計算時間を要する．さらにデータが大規模である場合，ℛ(𝑞𝑞) を求めるには，オブジェクト間の距離計算を大量に行わなければならない．ℛ(𝑞𝑞)を求めるために，𝑞𝑞 と全ての 𝑢𝑢 について距離計算を行うと，1回の距離計算を行うための計算量を 𝐶𝐶 とするなら，𝐶𝐶 の計算量が必要となる．𝐾𝐾 個のピボットで構成されるピボット

集合 𝒫𝒫{𝑝𝑝1 𝑝𝑝2

𝑝𝑝𝐾𝐾 | 𝑝𝑝

𝒰𝒰} を用いることで ℛ(𝑞𝑞) を求めるための (𝑞𝑞 𝑢𝑢) の距離計算回数を削減できる．
ピボット集合を用いた類似検索は次の手順で実行される．
まず，ピボット集合を構成するフェーズは以下のように行われる．
step1． オブジェクト集合 𝒰𝒰 が与えられる;
step2． 𝒰𝒰 からピボット集合 𝒫𝒫 を構成する;
step3． 各ピボット 𝑝𝑝 𝒫𝒫 と各オブジェクト 𝑢𝑢 𝒰𝒰との距離 (𝑝𝑝 𝑢𝑢) を計算しキャッシュする;
次に，ピボット集合を用いて与えられたクエリに対してℛ(𝑞𝑞) を求めるフェーズは以下のように行われる．
step4． 与 え ら れ た ク エ リ 𝑞𝑞 𝕏𝕏 と 各 𝑝𝑝 𝒫𝒫 の 距 離(𝑞𝑞 𝑝𝑝) を計算する;
step5． ℛ(𝑞𝑞) を求める;

以上の手順により， (𝑞𝑞 𝑢𝑢) の距離計算回数を削減できる理由を示す．𝑞𝑞 と 𝑝𝑝 の距離 (𝑞𝑞 𝑝𝑝)，𝑝𝑝 と 𝑢𝑢 の距離 (𝑝𝑝 𝑢𝑢) は，
距離の三角不等式(𝑞𝑞 𝑢𝑢)| (𝑞𝑞 𝑝𝑝)(𝑝𝑝 𝑢𝑢)|(1)
が成り立ち，レンジ 𝑟𝑟 に対し| (𝑞𝑞 𝑝𝑝)(𝑝𝑝 𝑢𝑢)|𝑟𝑟(2)ならば，式(1)より， (𝑞𝑞 𝑢𝑢)
𝑟𝑟 となる．即ち，式(2)を満た
す 𝑢𝑢 については， (𝑞𝑞 𝑢𝑢) の計算をしなくてよい． (𝑝𝑝 𝑢𝑢) は，𝑞𝑞 が入力される前に事前計算しておくことが可能である．ある 𝑢𝑢 について，𝐾𝐾 個のピボットのいずれかが式(2)を満たすならば， (𝑞𝑞 𝑢𝑢) の計算を削減できる．即ち，𝐾𝐾 個のピボットについて計算された | (𝑞𝑞 𝑝𝑝)(𝑝𝑝 𝑢𝑢)| の最大値を𝐷𝐷(𝑞𝑞 𝑢𝑢) (𝒫𝒫) max| (𝑞𝑞 𝑝𝑝)(𝑝𝑝 𝑢𝑢)|𝑝𝑝 𝒫𝒫と定義するならば，𝐷𝐷(𝑞𝑞 𝑢𝑢) (𝒫𝒫)𝑟𝑟 を満たす(𝑞𝑞 𝑢𝑢) の計算を削減することができる．
この手法の計算量は，ピボット集合 𝒫𝒫 を構成する計算量と ℛ(𝑞𝑞) を求める計算量に分けられる．距離計算回数の期待値 は ， 𝒰𝒰𝒰

{𝑢𝑢|𝑢𝑢𝒰𝒰，𝐷𝐷(𝑞𝑞 𝑢𝑢) (𝒫𝒫)𝑟𝑟} と す る と ， 𝑞𝑞 と 各

𝑝𝑝 𝒫𝒫 の距離 (𝑞𝑞 𝑝𝑝) を求めるための計算量 𝐶𝐶𝐾𝐾 及び，式(2)を満たさず，省略できなかった|𝒰𝒰𝒰| 個のオブジェクトに対する距離を求めるための計算量 𝐶𝐶(|𝒰𝒰𝒰|) からなり，合わせて 𝐶𝐶 𝐶𝐾𝐾 𝐶 (|𝒰𝒰𝒰|)𝐶 となる．

ピボット集合の構成方法が，距離計算回数の期待値に影響することは，すでによく知られている．距離計算回数の期待値をなるべく小さくするようなピボット集合を高速に構成することが本研究の課題である．

3. 従来手法
ピボット集合を構成するアルゴリズムとして，幾つかのア
イディアに基づく手法が提案されている．そのアイディアとは，良いピボット集合の要素は各オブジェクトと離れており，
かつピボット同士も離れているというものである[6]．このア
イディアに基づいたピボット集合を構成する手法として，例
えば[7]では，既に選択されたピボットとの距離が最大となるオブジェクトをピボットとして逐次的にピボット集合に追加する手法を提案している. また[8]では, 距離分散を用いて,お互いにピボットが離れるようにピボット集合を構成している．
Bustos らは，より良いピボット集合の指標として目的関数を定義した．そして，ピボット集合を構成する問題を，目的関数値を最大化するピボット集合を求める最適化問題として定式化した．ただしこの最適化問題は，NP 困難であり，
厳密解を求めるのは困難である．そこで Bustos らは，近似的解法として貪欲法を用いる INC 法，及びピボットの入れ替えを行うことでピボット集合の改善を行う LOS 法を提案
し，[7]，[8]よりも良いピボット集合が得られることを計算機実験により示している．本節では Bustos らの手法の詳細について述べる．

3.1 ピボット選択の評価基準となる目的関数

Bustos らは，距離計算回数の期待値の削減に繋がる目的
関数を定義している．𝒰𝒰 からランダムに選択した 𝑇𝑇 個のオ
ブジェクトペアを(𝑎𝑎 𝑏𝑏 )|(𝑎𝑎 𝑏𝑏 ) 𝒰𝒰 𝒰𝒰}
𝒜𝒜 {(𝑎𝑎 𝑏𝑏 ) (𝑎𝑎 𝑏𝑏 )2

― 10 ―

日本データベース学会論文誌 Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 年 No.3
2月
2013年 2月

一般論文

DBSJDBSJ
Journal,Vol.11, No.3
Journal,Vol.
11, No.3

February 2013

February 2013

したとき，目的関数を以下のように定義している．
𝐹𝐹(𝒫𝒫)

3.2 INC 法∑ 𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒫𝒫)(3)(𝑎𝑎 𝑏𝑏) 𝒜𝒜

式(3)の値を最大化するピボット集合を求めるには，すべてのオブジェクトの組合せについて式(3)の値を求めれば可能だが，𝐾𝐾𝐾(𝐾 𝐾 1) 2 の計算量となる．Bustos らは式(3)の値を最大化する手法として，貪欲法を用いてピボット集合を構成する INC 法を提案している．INC 法は，全てのオブジ
ェクトについて目的関数値を計算しない．ピボットを 1 つ選
択する度に，𝒰𝒰 の部分集合
𝒞𝒞𝒞1 𝒞𝒞2𝒞𝒞

𝒞𝒞𝑊𝑊 | 𝒞𝒞𝑤𝑤 ϵ 𝒰𝒰，𝑊𝑊 𝑊 𝐾 𝑊

をランダムに構成し，その後，目的関数値を最大とする 𝒞𝒞をピボット 𝒞𝒞 ′ とする．𝒞𝒞 ′ は，次のように定義される．
{𝐹𝐹({𝒞𝒞})}
𝒞𝒞 ′

𝒞𝒞

𝒞𝒞 𝒞𝒞

このようにして高速化を実現している．以下に INC 法のア
ルゴリズムを示す．
step1． オブジェクト集合 𝒰𝒰 が与えられる;
step2． 𝒰𝒰 からランダムに 𝑇𝑇 個のオブジェクトペア 𝒜𝒜を構成する．𝒫𝒫 ← ∅ とする;
step3． step3-1 から step3-3 を 𝐾𝐾 回行う;
step3-1. 𝒰𝒰 からランダムに集合 𝒞𝒞 を構成する;
step3-2. 𝒞𝒞 ′ を求める;
step3-3. 𝒫𝒫 ← (𝒫𝒫 {𝒞𝒞 ′ }) とする;
step4． 𝒫𝒫 を出力し，終了する;
アルゴリズムの主たる計算は step3-2 であり，𝒞𝒞 𝒞𝒞 と
(𝑎𝑎 𝑏𝑏) 𝒜𝒜 のすべての組み合わせに対して 2 回ずつ距離を計算するため，2𝐶𝐶𝑇𝑇𝑊𝑊 の計算量がかかる．step3 は 𝐾𝐾 回繰り返すため，アルゴリズム全体の主たる計算量は 2𝐶𝐶𝐾𝐾𝑇𝑇𝑊𝑊 となる．
Bustos らは，大きな 𝒰𝒰 に対しても，比較的小さい 𝑊𝑊 で良い目的関数値が得られることを実験により示している．

3.3 LOS 法

Bustos らは，INC 法の他にピボットの入れ替えを行うことでピボット集合の改善を行う LOS 法も提案している．あるペア (𝑎𝑎 𝑏𝑏)

𝒜𝒜 について，𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑝𝑝 𝑊) が最大の値となる∗とし，𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑝𝑝 𝑊) が 2 番目に大きい値となる
𝑝𝑝 を 𝑝𝑝(𝑎𝑎
𝑏𝑏)

𝑝𝑝 を

∗∗
𝑝𝑝(𝑎𝑎
𝑏𝑏)

の貢献を

とする．また，あるピボット 𝑝𝑝 の目的関数値

𝑔𝑔 (𝒞𝑝𝑝 𝑊)とする．ここで𝛿𝛿(𝑎𝑎 𝑏𝑏)

∑ {(𝑎𝑎 𝑏𝑏) 𝒜𝒜𝛿𝛿(𝑎𝑎 𝑏𝑏) (𝑝𝑝
0

(𝑝𝑝

∗
𝑝𝑝(𝑎𝑎
のとき)
𝑏𝑏)

∗
𝑝𝑝(𝑎𝑎
のとき)
𝑏𝑏)

∗
∗∗
𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑝𝑝(𝑎𝑎𝑊) 𝐾 𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑝𝑝(𝑎𝑎
𝑊)
𝑏𝑏)
𝑏𝑏)

を，ランダムに選択した
𝒮𝒮

𝒞𝒮𝒮1 𝒮𝒮2

argmin 𝒞𝑔𝑔 (𝒞𝑝𝑝 𝑊)𝑊
𝑝𝑝

4. 提案手法

本節では，RIWO 法，RIWO-INC 法の詳細と主たる計算量について述べる．

4.1 RIWO 法

経験的に類似したデータを扱った場合や INC 法などの適用により，ピボット数が既知の場合において，高速に良いピボット集合を構成する方法として RIWO 法を提案する．
RIWO 法は，オブジェクト集合 𝒰𝒰 からランダムに選ばれたピボット 𝑢𝑢𝑛𝑛

𝒞𝑢𝑢𝑛𝑛 𝑊 と𝒞𝑢𝑢𝑛𝑛 𝑊 を除いたと

𝒞𝑢𝑢𝑛𝑛 𝑊 𝒞𝑝𝑝 𝑊 の目的関数値の差分値が̂最小となるピボット 𝑝𝑝 を取り除く．𝑝𝑝̂ は，次のように定義される．
𝑝𝑝̂
argmin 𝒞𝐹𝐹 (𝒫𝒫 𝒞𝑢𝑢 𝑊) 𝐾 𝐹𝐹 (𝒫𝒫 𝒞𝑢𝑢 𝑊 𝒞𝑝𝑝 𝑊)𝑊𝑝𝑝

𝒫𝒫 𝒞𝑢𝑢𝑛𝑛 𝑊

𝑝𝑝

𝒫𝒫 𝒞𝑢𝑢𝑛𝑛 𝑊

argmin 𝒞𝑔𝑔 (𝒞𝑝𝑝 𝑊)𝑊𝑛𝑛

𝑛𝑛

以下に RIWO 法のアルゴリズムの詳細を示す．
step1． オブジェクト集合 𝒰𝒰 が与えられる;
step2． 𝒰𝒰 からランダムに 𝑇𝑇 個のオブジェクトペア 𝒜𝒜と 𝐾𝐾 個の要素のピボット集合 𝒫𝒫 を構成する;
step3． step3-1 から step3-4 を 𝑄𝑄 回繰り返す;
step3-1. 𝒰𝒰 からランダムにピボット 𝑢𝑢𝑛𝑛 を選択する;
𝑇𝑇 個の (𝑎𝑎 𝑏𝑏)
新する;

1).

𝒫𝒫

𝒮𝒮 𝒮𝒮

𝒫𝒫

きのピボット集合 𝒫𝒫

2).

𝒮𝒮𝑋𝑋 | 𝒮𝒮𝑥𝑥 𝜖𝜖 𝒰𝒰，𝑋𝑋 𝑊 𝐾𝑊

中の貢献が最も大きい要素 𝒮𝒮 ′𝒰𝒰 をピボット集合 𝒫𝒫 に加え 𝒫𝒫

し，ピボット集合のあるピボット 𝑝𝑝

step3-2.

である．LOS 法では，貢献が最も少ないピボット
𝑣𝑣𝑣𝑣𝒞𝒞𝑣𝑣𝑣𝑣𝑣𝑣

𝒫𝒫 を得る．以下に LOS 法のアルゴリズムを示す．
step1． オブジェクト集合 𝒰𝒰 が与えられる;
step2． 𝒰𝒰 からランダムに 𝑇𝑇 個のオブジェクトペア 𝒜𝒜と 𝐾𝐾 個の要素のピボット集合 𝒫𝒫 を構成する;
step3． step3-1 から step3-4 を 𝐾′ 回行う;
step3-1. 𝑣𝑣𝑣𝑣𝒞𝒞𝑣𝑣𝑣𝑣𝑣𝑣 を求める;
step3-2. 𝒰𝒰 からランダムに集合 𝒮𝒮 を構成する;
step3-3. 𝒮𝒮 ′ を求める;
step3-4. 𝑔𝑔({𝒮𝒮 ′ }) 𝑔𝑔({𝑣𝑣𝑣𝑣𝒞𝒞𝑣𝑣𝑣𝑣𝑣𝑣}) ならば，𝒫𝒫 ← (𝒫𝒫 {𝒮𝒮 ′ }) {𝑣𝑣𝑣𝑣𝒞𝒞𝑣𝑣𝑣𝑣𝑣𝑣} とする;
step4． 𝒫𝒫 を出力し終了する;
距離計算は，step3-1 ならびに step3-3 で行われている．
step3-1 は初回のみ 𝑝𝑝 𝒫𝒫 と (𝑎𝑎 𝑏𝑏) 𝒜𝒜 のすべての組み合
わせに対して 2 回ずつ距離計算を行う．2 回目以降はキャッシ ュを 用い るため 距離 計算の 回数は 0 と なる ．つまりstep3-1 を 𝐾′ 回繰り返したときの計算量は 2𝐶𝐶𝐾𝐾𝑇𝑇 となる．
step3-3 は，𝒮𝒮 𝒮𝒮 と(𝑎𝑎 𝑏𝑏) 𝒜𝒜 のすべての組み合わせに対して 2 回ずつ距離を計算し，これを 𝐾′ 回繰り返すため，
2𝐶𝐶𝐾′𝑋𝑋𝑇𝑇 の計算量がかかる．したがって，アルゴリズム全体の主たる計算量は 2𝐶𝐶𝑇𝑇(𝐾𝐾 𝐶 𝐾′𝑋𝑋) となる．

{𝐹𝐹({𝒮𝒮})} と入れ替える．これを繰り返すことにより，最終的に目的関数値の高い

3― 11 ―∗∗∗𝒜𝒜 について 𝑝𝑝(𝑎𝑎，𝑝𝑝(𝑎𝑎を更𝑏𝑏)𝑏𝑏)

𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑢𝑢𝑛𝑛 𝑊)を計算する;𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑢𝑢𝑛𝑛 𝑊)

𝐷𝐷(𝑎𝑎 𝑏𝑏) ({𝑝𝑝 ∗ (𝑎𝑎 𝑏𝑏 )}) ならば，

∗∗
∗
∗
𝑝𝑝(𝑎𝑎
← 𝑝𝑝(𝑎𝑎，𝑝𝑝(𝑎𝑎← 𝑢𝑢𝑛𝑛 とする．また
𝑏𝑏)
𝑏𝑏)
𝑏𝑏)
∗
𝑊)
𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑝𝑝(𝑎𝑎𝑏𝑏)

𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑢𝑢𝑛𝑛 𝑊)∗∗
𝐷𝐷(𝑎𝑎 𝑏𝑏) (𝒞𝑝𝑝(𝑎𝑎𝑊)𝑏𝑏)

日本データベース学会論文誌 Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 年 No.3
2月
2013年 2月

一般論文

DBSJDBSJ
Journal,Vol.11, No.3
Journal,Vol.
11, No.3

February 2013

February 2013∗∗
← 𝑢𝑢𝑛𝑛 とする;
ならば，𝑝𝑝(𝑎𝑎𝑏𝑏)̂
step3-3. 𝑝𝑝 を求める;

step3-4.

𝒫𝒫 ← (𝒫𝒫{𝑢𝑢𝑛𝑛 })

{𝑝𝑝̂} とする;

step4． 𝒫𝒫 を出力し終了する;
距離計算は，step3-2-1 ならびに step3-2-2 で行われている．

step3-2-1 は 𝐷𝐷(𝑎𝑎 𝑏𝑏) ({𝑢𝑢𝑛𝑛 }) を各ペアについて計算するため計算するため 2𝐶𝐶𝐶𝐶 となる．step3-2-1 は，𝑄𝑄 回繰り返すため
2𝐶𝐶𝐶𝐶𝑄𝑄 となる．step3-2-2 は，初回のみ 𝑝𝑝 𝑝 𝒫𝒫 と (𝑎𝑎 𝑏𝑏) 𝑝 𝑎𝑎のすべての組み合わせに対して 2 回ずつ距離を計算する．2
回目以降はキャッシュを用いるため距離計算の回数は 0 となる．つまり step3-2-2 の計算量は 2𝐶𝐶𝐶𝐶𝐶𝐶 となる．したがってアルゴリズム全体の主たる計算量は 2𝐶𝐶𝐶𝐶(𝐶𝐶 𝐶 𝑄𝑄) となる．
Bustos らの LOS 法は，ランダムに選択されたピボット候
補と，現在のピボット集合の最悪の要素を入れ替える．これに対して RIWO 法は，ランダムに選択されたピボット候補
をピボット集合に追加した後，最悪の要素を削除する．即ち，
RIWO 法の方が，目的関数向上のためのピボット入れ替えの選択肢が広く，効率の良い入れ替えが可能である．LOS 法と比較して，RIWO 法は，同等の計算量で良いピボット集合を構成する．

算回数の期待値が最も少ないピボット数を RIWO 法で構成するピボット数とし，そのサイズのピボット集合を RIWO
法で構成する際，どの程度の構成時間でどの程度の距離計算
回数の期待値を達成できるかを調べた．

5.1 評価データと実験設定

評価データ，及び実験設定は Bustos らの実験を参考にしている．実験の評価データは人工データとして 14 次元のベ
クトルデータ，現実データとして NASA の画像データ，
Emacs の単語辞書データを扱う．
14 次元のベクトルデータ（以下，人工データ）は，14 個の 0～1 の要素からなり，110,000 のデータで構成される．
距離の計算は，ユークリッド距離を用いて計算する．NASAの画像データ（以下，NASA データ）は，40,700 の画像から構成されるデータであり，各画像は 20 次元の特徴ベクトルに変換されている．距離の計算は，ユークリッド距離を用いて計算する．Emacs の単語辞書データ（以下，Emacs データ）は，Emacs のスペルチェックのための辞書の単語データである．データ数は 479,829 であり，その中からランダムに選択した 110,000 のデータを用いている．距離の計算は，編集距離を用いて計算する．各実験のパラメータは表 1 のように設定している．

4.2 RIWO-INC 法

ピボット数が未知の場合，ピボット集合にピボットを逐次追加することでピボット数の調整を行う必要がある．ピボッ
ト数が未知の場合に，良いピボット集合を構成する方法として RIWO-INC 法を提案する．
RIWO-INC 法は，𝜀𝜀 個のピボットから構成されるピボッ
ト集合 𝒫𝒫 に対して，新たなピボット 𝑢𝑢𝑛𝑛 を 𝒫𝒫 に追加し，
RIWO 法の step3-1 から step3-4 を 𝐻𝐻 回行うことを繰り返し行うことで 𝒫𝒫 にピボットを逐次追加していく．以下に
RIWO-INC 法のアルゴリズムを示す．
step1． オブジェクト集合 𝒰𝒰 が与えられる;
step2． 𝒰𝒰 からランダムに 𝐶𝐶 個のオブジェクトペア 𝑎𝑎と 𝐶𝐶 個の要素のピボット集合 𝒫𝒫 を構成する;
step3． step3-1 を 𝜀𝜀 回繰り返す;
step3-1. RIWO 法の step3-1 から step3-4 を 𝐻𝐻 回行う;
step4． step4-1 から step4-2 を 𝐶𝐶 𝐾 𝜀𝜀 回繰り返す;
step4-1. 𝒰𝒰 からランダムにピボット 𝑢𝑢𝑛𝑛 を選択し，𝒫𝒫 ← 𝒫𝒫{𝑢𝑢𝑛𝑛 } とする;

step4-2. RIWO 法の step3-1 から step3-4 を 𝐻𝐻 回行う;
step5． 𝒫𝒫 を出力し終了する;
距離計算は，step3-1 ならびに step4-2 で行われている．
step3-1 の計算量は RIWO 法の step3-1 から step3-4 を 𝐻𝐻 回
行 うこ とを 𝜀𝜀 回 繰 り返す ため ，2𝜀𝜀𝐶𝐶𝐶𝐶(1 𝐶 𝐻𝐻 ) と なる．
step4-2 の計算量は RIWO 法の step3-1 から step3-4 を 𝐻𝐻
回行うことを 𝐶𝐶 𝐾 𝜀𝜀 回繰り返すため，2𝐶𝐶𝐶𝐶(𝐶𝐶 𝐾 𝜀𝜀 )(1 𝐶 𝐻𝐻 )となる．したがって，アルゴリズム全体の主たる計算量は2𝐶𝐶𝐶𝐶𝐶𝐶(1 𝐶 𝐻𝐻 ) となる．

5. 評価実験

本節では，計算機実験により，ピボット数が未知の場合，
各ピボット数に対し，RIWO-INC 法と INC 法を用いて，同じ計算量でピボット集合を構成した際，どの程度距離計算回数の期待値に差が出るのかを調べた．また，INC 法の距離計

表 1．実験で用いたパラメータ
Table.1 Parameter settings in our experiments
NASA
Emacs
データ名
人工データ
110,000
40,000110.000
データ数
オブジェクト数

100,000

37,000100,000

クエリ数

10,0003,700

10,000

ペア数100,000

37,000100,000

レンジは，人工データ，及び NASA データでは 0.01%のオブジェクトを同定するレンジクエリで評価した．つまり，オブジェクト数に対して |ℛ(𝑞𝑞)| ≈ 0 0001 となるように 𝑟𝑟 を設定した．
また Emacs データは 𝑟𝑟 𝑟 2 に設定した．
これらのレンジ設定は，Bustos らの実験と同一の実験設定を使用している[1]．
各手法におけるパラメータは以下のように設定した．INC
法の 𝑊𝑊 は，Bustos らの実験と同様に 50 とした．LOS 法の𝑋𝑋 は，1 回の繰り返しの計算量が，INC 法のピボット 1 つを追加する計算量と同等になるように 𝐶𝐶 𝐶 ′𝑋𝑋 𝑟 𝐶𝐶𝑊𝑊 としている．ここで 𝐶𝐶 𝐶 ′𝑋𝑋 𝑟 𝐶𝐶𝑊𝑊 は， ′𝑋𝑋 𝑟 𝐶𝐶(𝑊𝑊 𝐾 1) であり，Bustos らは， ′𝑋𝑋 の計算量を維持しつつ， ′ と 𝑋𝑋 のパラ
メータを変更し，実験を行っている．本実験では，Bustos
らの実験で最も良い結果であったパラメータである′ 𝑟 𝐶𝐶，𝑋𝑋 𝑟 𝑊𝑊 𝐾 1 を用いる．また，RIWO-INC 法の 𝜀𝜀 は5 とした．

5.2 ピボット数が未知の場合

ピボット数が未知の場合，ピボット集合にピボットを逐次追加することでピボット数の調整を行う必要がある．このよ
うにピボット数が未知の場合，RIWO-INC 法は INC 法よりも良いピボット集合を構成できることを示す．実験では，各ピボット数に対し，RIWO-INC 法と INC 法を用いて，同じ計算量でピボット集合を構成した際，どの程度距離計算回数の期待値に差が出るのかを調べた．図 1 から図 3 に結果を示
す．実験結果は，10 回の試行の相加平均であり，各実験に

4― 12 ―

日本データベース学会論文誌 Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 年 No.3
2月
2013年 2月

一般論文

DBSJDBSJ
Journal,Vol.11, No.3
Journal,Vol.
11, No.3

February 2013

February 2013

おける距離計算回数の期待値の標準偏差を縦長の長方形で示す．
図 1 の人工データ及び，図 3 の Emacs データでは，
RIWO-INC 法は，INC 法と比較して縦長の長方形同士が十分離れており，有意に少ない距離計算回数の期待値が得られている．図 2 の NASA データでは， RIWO 法が INC 法よりも各ピボットにおいて，有意とはいえないものの少ない距
離計算回数の期待値が得られている．RIWO-INC 法が INC
法よりも少ない距離計算回数の期待値が得られている要因
は，INC 法がピボットを 1 つ追加するためにかかる計算量に対し，RIWO 法の 1 回の入れ替えにかかる計算量が少ないた
め，高速に良い目的関数値が得られているためであると考えられる．

5.3 ピボット数が既知の場合

経験的に類似したデータを扱った場合や INC 法などの適用により，良いピボット数を推測できる．このようなピボッ
ト数が既知の場合に，RIWO 法が高速に良いピボット集合を得られることを示す．具体的には，INC 法の距離計算回数の期待値が最も少ないピボット数を RIWO 法で構成するピボ
ット数とする．そして，そのサイズのピボット集合を RIWO
法で構成する際，どの程度の構成時間でどの程度の距離計算
回数の期待値を達成できるかを調べた．加えて LOS 法の実験も行った．ピボット数は，人工データでは 600 個，NASA
データでは 70 個，Emacs データでは 240 個である．図 4 から図 6 に結果を示す．図中の●が，INC 法において距離計算
回数の期待値が最も少ない場合である．図 4 の人工データの結果では，LOS 法が INC 法の距離計算回数の期待値を達成するには同程度の距離計算回数が必要である．INC 法において最も少ない距離計算回数の期待値 は 1644 であり，約 30
億回の距離の計算をしている．それに対し，RIWO 法では，
約 1/2 の距離計算回数で同等の距離計算回数の期待値を達成している．図 5 の NASA データは，INC 法において最も少ない距離計算回数の期待値は 228 であり，約 2 億 6 千万回の距離の計算をしている．それに対し RIWO 法では，約 1/7 の距離計算回数で INC 法の距離計算回数の期待値を達成している．図 6 の Emacs データは，最も RIWO 法の INC 法との差が顕著である．INC 法において最も少ない距離計算回数の期待値は 442 であり，約 24 億回の距離の計算をしている．
それに対し，RIWO 法は，約 1/8 の距離計算回数で INC 法の距離計算回数の期待値を達成している．
これらの結果により，RIWO 法は，INC 法と比較して，人工データでは約 1/2，現実データでは約 1/7 以下の距離計算
回数の期待値で同等のピボット集合が得られているため，特に現実データにおいて顕著な性能改善が期待できる．

図 1．人工データ．
Fig.1

Artificial data．

図 2．NASA データ．
Fig.2

NASA data．

6. おわりに
本論文では，多様なデータに対する計算機実験により，
RIWO 法が従来手法（INC 法）よりも少ない距離計算回数で同等の良いピボット集合が得られることを示した．具体的には，RIWO 法は従来手法と比較して，人工データでは約 1/2，
現実データでは約 1/7 以下の距離計算回数で同等のピボット集合が得られた．また，RIWO 法に基づいた RIWO-INC 法を提案し，ピボット数が未知の場合，INC 法と同程度の計算量で，より良いピボット集合を構成することを計算機実験により示した．

5― 13 ―

図 3．Emacs データ．
Fig.3

Emacs data．

日本データベース学会論文誌 Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 年 No.3
2月
2013年 2月

一般論文

Journal,DBSJDBSJ
Vol.11, No.3
Journal,Vol.
11, No.3

February 2013

February 2013
今後は，ピボット集合の構成の更なる高速化及び，類似検索の性能を向上させるピボット集合の構成手法の研究を行
う．

[謝辞]

本研究は，科学研究費補助金基盤研究(C) (No. 23500128)の補助を受けた．

[文献][1] B．Bustos，G．Navarro，and E．Chavez．Pivot selection
techniques for proximity searching in metric spaces.
Pattern Recognition Letters，24(14)：2357-2366，2003．
Else-vier．
[2] O．Pedreira and N．R．Brisaboa．Spatial selection ofsparse pivots for similarity search in metric spaces．
LNCS (4362)， pages 434-445，2007．
[3] B．Bustos, O．Pedreira，N．Brisaboa．(2008) A dynamic
pivot selection technique for similarity search ．
SISAP’08．IEEE，pp 105-112[4] 三津山 雅規，武藤 伸明，斉藤 和巳，池田 哲夫，類似検索における遅延評価を用いたピボット選択の高速化，DEIM Forum 2011，Vol.A9-6，(2011)．
[5] 三津山 雅規，斉藤 和巳，池田 哲夫，大久保誠也，武藤伸明，大規模データにおける逐次入れ替えによるピボット
改善選択法，DEIM Forum 2012，Vol.A7-5，(2012)．
[6] P．Zezula，G．Amato，V．Dohnal，and M．Batko．
Similarity search．The metric space approach，volume
32．Springer，2006．
[7] L．Mico，J．Oncina，and R．E．Vidal．A new versionof the nearest-neighbor approximating and eliminating
search (aesa) with linear pre-processing time andmemory requirements．Pattern Recognition Letters，
15:9-17，1994．
[8] P ． Yianilos ． Data structures and algorithmsfor
nearestneighbor search in general metric space ．
SODA1993，pages 311-321，1993．

図 4．人工データ．ピボット 600 個．
Fig.4

Artificial data．600 pivots．

図 5．NASA データ．ピボット 70 個．
Fig.5

三津山 雅規 Masaki MITSUYAMA

NASA data．70 pivots．

静岡県立大学大学院経営情報イノベーション研究科修士課
程在学中．2011 静岡県立大学経営情報学部卒業．類似検索の研究に従事．日本データベース学会学生会員．

斉藤 和巳 Kazumi SAITO

経営情報イノベーション研究科教授．1985 慶應義塾大学理
工学部数理科学科卒業．知能情報学，発見科学，複雑ネット
ワークの科学に従事．

池田 哲夫 Tetsuo IKEDA

経営情報イノベーション研究科教授．1981 東京大学大学院
理学系研究科修士課程修了．データ工学，情報検索，GIS(地理情報システム)に従事．

大久保 誠也 Seiya OKUBO

経営情報イノベーション研究科助教．2005 電気通信大学大学院電気通信学研究科博士後期課程電子情報学専攻修了．情報セキュリティ，量子計算に従事．

武藤 伸明 Nobuaki MUTOH

図 6．Emacs データ．ピボット 240 個．
Fig.6

経営情報イノベーション研究科准 教 授 ．1995 横浜国立大学
大学院工学研究科博士課程後期修了．離散幾何学，計算幾何学に従事．

Emacs data．240 pivots．

6― 14 ―

日本データベース学会論文誌 Vol.11, No.3
日本データベース学会論文誌 Vol.11,
2013 年 No.3
2月
2013年 2月