DEIM Forum 2017 C8-2

集約 k 近傍の効率的な検索方法
塚原 拓人†

董

于洋†

陳

漢雄†

古瀬 一隆†† 筑波大学 〒 305–8571 茨城県つくば市天王台 1-1-1
E-mail: †s1520667@u.tsukuba.ac.jp, ††tou@dblab.is.tsukuba.ac.jp, †††chx@cc.tsukuba.ac.jp,††††furuse@cs.tsukuba.ac.jp
あらまし 集約近傍（aggregate nearest neighbor, ANN）検索とは，クエリ集合 Q に対して，定められた距離関数に基づき，データベース P から Q との集約距離が最も近いオブジェクトを探す問題である.ANN はデータマイニングや情報検索，中でも特に地理情報システムにおいて多く利用されている．ANN 検索から k 近傍を求める AkNN への拡
張は自然な要求である．今までには道路網上や平面上の L1 距離などの限定されたケースでの AkNN についての研究が確認されたが，多次元に対応できず，また，より一般的なユークリッド距離への拡張は不可能であった．本研究では，汎用的な AkNN 検索の効率的なアルゴリズムを提案し，これを検証する．
キーワード ANN, AkNN, データ索引, データ検索

1. 概

要

れる．
このような，ANN 検索から k 近傍を求める AkNN への拡張

近年，データマイニングや情報検索などに利用されているは自然な要求である．今までには道路網上や平面上の L1 距離

近傍探索は，情報検索の中でも重要な課題として活発に研究などの限定されたケースでの AkNN についての研究が確認さされている．近傍探索とは，データセットの中からクエリと最れたが，多次元に対応できず，また，より一般的なユークリッも類似度の高いオブジェクトを探索する問題である．近傍探索

ド距離への拡張は不可能であった．そこで， 本研究では一般的の一種である集約最近傍探索 (Aggregate Nearest Neighbor，な AkNN 検索に着目する．

ANN) とは，データセット P とクエリ集合 Q が与えられた時，既存の ANN 手法を直接 AkNN に適用することは不可能で

データセットの中から Q との集 約距離が最近となるオブジェ

はないが，このためには，この ANN 手法で求められた解を除クトを探す問題である．

いたデータに対して同じ ANN 手法を適用するという処理を

例えば，異なる場所にいる人たちがある会議に参加するとしk − 1 回繰り返す必要があり，非現実的である．

て，主催者が開催地を決めるとする． このとき，参加者たちの既存の ANN 手法を AkNN 手法に拡張した場合，ANN 手法

いる場所によって，集合場所までの距離や，そこに辿り着くまは一般に現在の最良解候補との集約距離を用いて枝刈りを行う

で の所要時間，かかる費用などがそれぞれ異なる． 主催者は，ため，最低でも k 個のエントリ（かデータ点）を常時確保して参加者の負担 (集合場所までの金額，時間等) が，できるだけ小初めて刈り取りが行える. これに対して本研究では，索引ノー

さくなるように集合場所を決めることになる． もし，主催者がドがデータ点を k 個以上含んでいる場合に，クエリ集合 Q と，参加者の合計負担金額を重視するなら，すべての参加者の場所

このノードとの距離を上界に用いた索引ノードの枝狩りすること集合地点との距離を計算し，合計距離の最も小さい場所を選とを可能とした．これにより不要エントリの早期発見が可能に

ぶ．このような検索の解を求めるためには，既存の ANN 手法

なり検索の効率が向上する．本論文では，この性質を利用したは計算時間が多くかかるという問題点がある． 特に，人数や集汎用的な AkNN 検索の効率的なアルゴリズムを提案し，これ合候補地の数が増えると，計算量が大きく増えていく．

を検証する．

このように，ANN はデータをベクトルで表現し，それらの距離で類似度を測る． しかし，ANN では数値化されたパラ2. 問 題 定 義

メータや，その重みがユーザの意図を正確に反映しない場合がD 次 元 の 空 間 に あ る 両 点 p1 = (x1 , · · · , xD ) と p2 =ある． すると ANN で求められる解が，ユーザが求める解と一(y1 , · · · , yD ) の距離 |p1 p2 | はマンハッタン距離やユークリッ

致しない可能性がある．

ド距離などがある. 本論文ではユークリッド距離を使う. p1 と先程の例で言うと，集合場所までの距離の合計が厳密に最短

p2 の距離 |p1 p2 | は式 1 で定義する.

となるような場所を探すことは可能であるが，ユーザーはある程度距離が短ければ，厳密に最近となるような場所よりも，集合場所の立地や，そこに辿り着くまでの交通手段の違い等の方が重要と考えるかもしれない．そのためには，最近となるオv
uDu∑|p1 p2 | = t|xi − yi |2

(1)

i=1

ブジェクトただ 1 つを検索するのではなく，集約距離が短い集

そして, sum や max, min 等の単調増加集約関数 f を用い

合場所候補を複数検索するといった方法が有効であると考えらて, データ点 p とクエリ集合 Q = {q1 , q2 , · · · , qn } との集約距

mindist(Nj , M ) の n(= |Q|) 倍となる. f = max か f = min

離 adist (p, Q) を式 2 で定義する.

adist (p, Q) = f (|pq1 | , |pq2 | , · · · , |pqn |) =

f
1<
= i<
=n

(|pqi |)(2)

定義 1 (集約 k 近傍検索: AkNN 検索) デ ー タ 集 合 P ={p1 , p2 , · · · , pN } とクエリ集合 Q = {q1 , q2 , · · · , qn } と正のの場合, amindist(Nj , M ) = mindist(Nj , M ) となる (式 3).

amindist(Nj , M ) >= best dist ⇔{n · mindist(Nj , M ) >= best dist (f = sum)(3)
mindist(Nj , M ) >best
dist (f = max or min)=

整数 k が与えられたとき, P の中から Q との集約距離が短い点
を順に k 個検索することを集約 k 近傍 (AkNN) 検索という.

ル ー ル 2:

点 pj と M の 集 約 距 離 amindist(pj , M ) がbest dist よ り 大 き い か 等 し い 場 合, pj は ANN の 解 に な

3. 関 連 研 究

ら こ と は な く, 従って 刈 り 取って も よ い.

集約最近傍 (aggregate nearest neighbor, ANN) 検索問題

f = sum の 場

合, amindist(pj , M ) は pj と M の最小距離 mindist(pj , M )は, [1] にて集約関数 sum について定義され, [2] にて集約関数の n(= |Q|) 倍 と な る.

が max や min などの単調増加関数に拡張された. 前章で述べ

amindist(pj , M ) = mindist(pj , M ) とする (式 4).

たように，集約関数が f = sum の場合, ANN の解はクエリ集
合 Q との合計距離が最も短い点である. f = max の場合, 各ク
エリ点との最長距離が最小となる点である. また f = min の場合, 各クエリ点との最短距離が最小となる点である. [1] と [2]f = max か f = min の 場 合,

amindist(pj , M ) >= best dist ⇔{n · mindist(Nj , M ) >= best dist (f = sum)>mindist(pj , M ) = best dist (f = max or min)(4)

では, MQM(multiple query method) 手法,SPM(single point

method) 手法, MBM(minimal bounding method) 手法の三つの ANN 手法が提案された. この三つの手法では, データ集合

P は R-tree と呼ばれる木構造によってインデックスされる.

ル ー ル 3:ノ ー ド Nj に つ い て , M と の 集 約 距 離

amindist(Nj , M ) が best dist より小さいが, Q との集約距
離 amindist(Nj , Q) が best dist より大きいか等しい場合, Nj
も刈り取ってもよい. amindist(Nj , Q) はすべてのクエリ点

qi ∈ Q と Nj の最小距離 mindist(Nj , qi ) の集約距離である.
すなわち, amindist(Nj , Q) =f

(mindist(Nj , qi )). (式 5).

1<
=i<
=n

amindist(Nj , Q) >= best dist ⇔図 1 2 次元の R-tree

f
1<
= i<
=n

(mindist(Nj , qi )) >= best dist

(5)

R-tree は B-tree のような木構造のデータ構造であり, 多次元
情報の空間インデックスに使われる．図 1 に 2 次元の R-treeの例を示す. 図のように，R-tree は入れ子状になった最小包囲
矩形 (MBR) にデータ点を階層的に格納する. R-tree は低次元のデータにおいては高速に近傍を求めることができるが, デー
タが高次元になると次元の呪いと呼ばれる現象が生じ, 近傍検索の性能は急激に下がり, 最悪の場合は計算量が O(N ) となる.

図 2 MBM の例 (集約関数 f = sum)

以下では距離が小さい順の最良優先探索を用いた MBM 手法について詳しく述べる.

[1] と [2] にて，著者たちは MQM 手法,SPM 手法,MBM 手

3. 1 MBM 手法法を提案し, MBM 手法はその中で最も高速な手法であること

MBM(minimal bounding method) 手法は SPM 手法の問題を示した．MBM 手法は今までで最速の手法である．

点を解決するために提案された手法である. 基本的な考え方はMBM 手法は Q の分布範囲が広いケースでも， ルール 3 が

SPM 手法と同様に, 枝刈りのルールを用いて, ANN の解を含有効であるため SPM 手法より高速である.

んでいないエントリ（ノードか点）を刈り取り，クエリ集合 Q

囲が広くかつ数が多い場合， すべてのクエリ点と R-tree にあしかし， Q の範の ANN の解を高速に求める. MBM 手法では集約中心 qm のるエントリからの距離を計算する必要があって， より時間が長代わりに, クエリ集合 Q と Q の最小包囲矩形 M が使われる.

くかかってしまう問題が残っている． また， 次元数が増える

MBM 手法は以下に示す 3 つの枝刈りルールを用いる.

と， R-tree のノード同士が重なってしまい， 式 5 でも多くのノードを刈り取ることができない可能性がある．

ルール 1: ノード Nj と Q の最小包囲矩形 M の集約距離

amindist(Nj , M ) が best dist より大きいか等しい場合, Nj の

3. 2 その他の手法
ANN 検索に関する研究は他にも [5], [6], [9], [7], [8], [10], [11]

刈り取ってもよい.

等 が 挙 げ ら れ る. [5] で は 索 引 を 使 わ な い vp-ANN 手 法 と

f = sum の場合, amindist(Nj , M ) は Nj と M の最小距離

Projection-Based Pruning 手法を提案した. [6] では誤差を許

中には best N N より良い解は含まれなく,容する代わりに高速な近似 ANN 検索手法を提案した．[7] では
楕円を用いて, [9] ではクエリ Q の重心との距離を用いてデー
タ集合 P を刈り取る手法を提案した．[8], [10] は道路網上にあるデータ集合の ANN 検索問題である．

3. 3 AkNN 検索
AkNN 検索に関する研究は [12], [13] 等が挙げられが，それぞれ [12] では集約距離 f = max における平面上の L1 距離に

amindist(Nj , Q) >= best maxdist ⇔{n · mindist(Nj , Q) >= best maxdist (f = sum) (6)mindist(Nj , Q) >best
maxdist (f = max or min)=
これは，より早い段階から刈り取りが行えるため，高速であると期待できる．

6. クエリの重心との距離による刈り取り

おける AkNN 検索，[13] では道路網にあるデータ集合 P における AkNN 検索と，前述のようなユークリッド距離の，多次元にも対応するような汎用的な AkNN 検索に関する手法は提案されていない．

MBM は Q の分布範囲が広くなると，クエリ Q の MBR である M と多くのノードや点が重なってしまう．その場合ルール 1 やルール 2 によって刈り取れるエントリが無くなり効率が落ちる．そこで Q の分布範囲に依らない刈り取りルールを導入

4. 提 案 手 法
前節で述べた MQM 手法,SPM 手法,MBM 手法は ANN 検索のための手法であり，AkNN 検索にそまま適用はできない．
全く手を加えないまま AkNN 検索を実行しようとすると，単純に ANN 検索を k 回実行することになるが，解が求まるまでに時間を要する ANN 検索に対して，この方法はあまりに非現実的である．単純な拡張方法として，best dist と best N N の代わりに，それぞれを ｋ 個を持つリストを保持し，常に距離順にソートする．MBM 手法における best dist を用いた比較の箇所を距離リストの中で最も悪いものと比較し，解を更新するたびにリストをソートすることで，AkNN 検索に拡張することができる．本稿ではこの AkNN に拡張した MBM 手法を拡張 MBM 手法と呼ぶ．

MBM は Q の分布範囲が広いケースでも，ルール 3 によりする．
補題 6.1 ある点集合 Q とその重心 G に対して，データ点 pjと G の集約距離は，pj と Q との集約距離よりも小さいか等
しい．
証明 6.1 adist(pj , G) =(G は Q の重心)
adist(pj , G) = |

∑n

∑n

−
−
→

i=0 Gqi +−−→ < ∑ni=0 qi pj | =

∑n

−−→

i=0 qi pj =

∑n

−−→

i=0 qi pj−−→

i=0 |qi pj | = adist(pj , Q) ■これを用いて，[9] と同様に，クエリ Q の重心 G を利用した，
新たな刈り取りルールを導入する．
ル ー ル 1’:ク エ リ の 重 心 G と ノ ー ド Nj と の 集 約 距 離

amindist(G, Nj ) が best dist より大きいか等しい場合，Njの中には best N N より良い解は含まれず，刈り取って良い．

多くのノードを刈り取ることができるため高速である．しかし，
ルール 3 ではルール 2 を満たす全てのノードに対して各クエリ点との距離を計算しなければならないため，R-tree のノードが重なる場合，特に高次元においては性能が低下する．これはAkNN 検索に拡張した場合においても同様である．また，最低でも最良解候補のデータ点を k 個確保するまでは刈り取りが行
えない．
以下では，データ点まで到達していなくてもエントリを刈り

amindist(Nj , G) >= best dist ⇔{n · mindist(Nj , G) >= best dist (f = sum)mindist(Nj , G) >dist (f = max or min)
best
=

(7)

ル ー ル 2’:ク エ リ の 重 心 G と デ ー タ 点 pj と の 集 約 距 離

amindist(G, pj ) が best dist より大きいか等しい場合，pj はbest N N より良い解ではなく，刈り取って良い．

取ることのできる，Q の分布範囲が広い場合や多次元における場合にも高速な AkNN 検索手法を提案する．

5. ノードとの最長距離による刈り取り
前述の通り，既存の ANN 手法を AkNN に拡張した場合，最低でも k 個のデータ点を確保しないと刈り取りが行えない．そこで，現在の最良解との距離 best dist だけでなく，現在の最短距離を持つノードとの最長距離 best maxdist を用いた刈り

amindist(pj , G) >= best dist ⇔{n · mindist(pj , G) >= best dist (f = sum)mindist(pj , G) >= best dist (f = max or min)(8)

また，このルールは前項のルール 4 に対しても同様に適用できる．

取りを導入する．
ル ー ル 4: ノ ー ド Nbest に 含 ま れ る デ ー タ 点 p の 数 がk 以 下 で あ る 場 合 ，ク エ リ Q と ノ ー ド Nj と の 集 約 距 離
amindist(Q, Nj ) が best maxdist より大きいか等しい場合，
Nj の中には best maxdist を持つノードに含まれるどの点よりも良い解は含まれず，刈り取って良い．

補題 6.2 ある点集合 Q とその重心 G に対して，ノード Njと Q の集約距離は，G と Nj との集約距離と Q と G の集約距
離の和よりも小さいか等しい．
証明 6.2 三 角 不 等 式 よ り dist(qi , Nj ) <= dist(qi , G) +dist(G, Nj )よって amindist(Q, Nj ) <= amindist(Q, G) + adist(G, Nj ) ■6.2 より，bestm axdist = amaxdist(G, Nj ) + adist(Q, G) としても刈り取り式は成り立つ．
そして，ルール 4 では，best maxdist を更新するたびにノー従って， AN Nmax においては， 凸包を構成する点集合 Qcに対してのみ距離計算を行えばそれ以外のクエリ点との距離計算が省略できるため，高速化が期待できる．

ドと Q の集約距離を計算しなくてはならなかったが，補題 6.2

しかし，高次元における凸包の作成コストは高い．そのためを用いることによって，以下のように，ノードとの集約距離を凸包を作成せずに Qc ⊂=Qx となるような，なるべく小さい点集

計算せずに刈り取りが行える．

合 Qx を取り出す．

ルール 4’: 現在の最長距離が最良であるノード Nbest に含ままず，クエリ Q の MBR を作成する，MBR の辺上に存在すれるデータ点 p の数が k 以上である場合，クエリの重心 G とる点は確実に凸包頂点に含まれるので Qx に追加する．この点

ノード Nj との集約距離 amindist(G, Nj ) が best maxdist よのうち，同じ頂点に隣接する 2 点を直線で結んだ時，その線より大きいか等しい場合，Nj の中には Nbest に含まれる点よりり外側に他のクエリ点が存在するならば，そのクエリ点は凸包も良い AkNN 解は含まれず，刈り取って良い．

頂点候補となる．つまり，その 2 点を結んだ直線のよりも内側

amindist(Nj , G) >= best maxdist ⇔{n · mindist(Nj , G) >= best maxdist (f = sum) (9)> best maxdist (f = max or min)mindist(Nj , G) =の点は凸包頂点にはなりえないということである．
そこで，Qx に追加したクエリ点のうち，同じ頂点に隣接す
る 2 点で MBR を作成する．それらに囲まれた点は凸包頂点になりえないので除外する．Qx に追加されたクエリ点と，除外

これらは，クエリ Q の分布範囲が広い場合でも，amindist

されたクエリ点以外について同様の手順を行い，全てのクエリが 0 になることは少なく，より多くのエントリを刈り取ること

点が Qx に追加されるか除外されるまで続けることで Qx を作ができると期待できる．

成する．

7. クエリの前処理による手法
7. 1 凸包の性質利用による手法 (f = max)

この手法は，クエリの分布範囲が広いほど多くの点が除外できるため，効果的であると期待できる．

7. 2 クエリのクラスタリングによる手法 (f = sum)

ある点集合 Q とその凸包に対して，Qクエリを複数に分割することによって，ルール 1,2 を以下のの中で任意の点 p との距離が最大となる点 qf は凸包頂点に含ように変形する．ただし，Qi ⊆ Q は div 個に分割したクエリ

まれる．

であり，Gi はそれらの重心，ni は分割したクエリにそれぞれ

補題 7.1 (凸包定理)

含まれるクエリ点の数である．
証明 7.1 凸包頂点集合 Qc と凸包頂点でない点 qi があったとき，任意の点 p と qi を直線で結ぶと，その直線と凸包が交差

ル ー ル 1”:ノ ー ド Nj と Q の 重 心 Gi の 集 約 距 離 の 和∑div
i=0 amindist(Gi , Nj ) が best dist よりも大きいか等しい場

する点 qx が存在する．qi は p と qx を結ぶ直線間に存在するこ合，Nj の中には best N N よりも良い解は含まれず，刈り取っとになるため |pqi | <= |pqx | である．また qx の存在する辺の両てもよい．

端の凸包頂点 qc1 , qc2 に対して |pqx | <= |pqc1 |, |pqx | <= |pqc2 | が成り立つ．よって |pqi | <= |pqx | <= |pqc | ■div∑amindist(Nj , Gi ) >= best dist ⇔

i=0
div
∑

ni · mindist(Nj , Gi ) >= best dist (f = sum)

(10)

i=0

ル ー ル 2”:デ ー タ 点 pj と Q の 重 心 G の 集 約 距 離

amindist(G, pj ) が best dist よりも大きいか等しい場合，pj はbest N N よりも良い解ではなく，刈り取ってもよい．
div∑

amindist(pj , Gi ) >= best dist ⇔

i=0
div
∑

図3 凸包定理

ni · mindist(pj , Gi ) >= best dist (f = sum)

(11)

i=0

これらは，クエリを分割しない場合よりも，より ANN 解ら
補題 7.2 AN Nmax において，クエリ集合 Q の凸包頂点集合

しいエントリに対して良い値を取ると期待できる．特に，クエを Qc とすると，AN N (Q) = AN N (Qc ) である．

リの分布範囲が広い場合において，多くのエントリを刈り取る
ことができると期待できる．これらの提案手法の f = sum に

証明 7.2 補題 7.1 より，クエリ Q の凸包頂点集合 Qc は，おける擬似コードを Algorithm1 に示す．

データ点 p に対して最大の距離をとるクエリ点 qf を含む．

これらの提案手法の計算量は，クエリに前処理を施す手法

AN Nmax の定義より，adist(Q, p) = adist(Qc , p) であるた

は f = sum と f = max がそれぞれ O(div ∗ n)，O(n)．デー

め,AN N (Q) = AN N (Qc ) である．■

タセットから k 近傍を求める計算量が両者ともに O(n ∗ N ) である．(f = max では n の代わりに，それよりサイズの小さい nx を用いる) よって f = sum,f = max それぞれの計算量

8. 実

験

は O(div ∗ n + n ∗ N )，O(n + nx ∗ N ) となる．それに対し

8. 1 実 験 環 境て，MBM の計算量は O(n ∗ N ) である．しかし，提案手法は提案手法の有用性を示すために, 提案手法と MBM 手法を

f = sum においては一般に div << N であり，f = max にお

AkNN 検索に拡張した拡張 MBM 手法について比較実験を行っいては n のサイズが減少するため，データセットから k 近傍をた. 実験環境を以下に示す. また,R-tree の実装は spatialindex-

求めるための計算量と比べて，前処理のコストは非常に小さい．

src-1.8.1（注 1）を利用した.

そのため，MBM との大きな差は無いと思われる．

Algorithm 1 提案手法 (f=sum) (root: R-tree root, Q: query
set)

•
•
•
•

OS: OS X Yosemite 10.10.5
CPU: 2.6 GHz Intel Core i5
メモリ: 8 GiB 1600 MHz DDR3
開発言語: C++

1: /* Qi は Q の部分集合である */8. 2 実験データ

2: /* Gi は Qi の重心である */3: /* H は amindist(Nj , Q) を昇順に並べた優先待ち行列である */実験は実データと合成データを用いて行った. 使用したデー

4: N ode ← root; best maxdist ← ∞; best dist[k] ← ∞;タは, 北アメリカの人口集落（注 2）の経緯度と, (0,1) の範囲にラ

best N N [k] ← null

ンダムで生成した一様分布データである. 実データは式 13 を

5: while N ode =| null && amindist(N ode, Q) < best dist[k − 1]do
6:と xmin はすべてのポイントの X 座標の最大値と最小値である.

if N ode.isIndex then7:/* N ode は R-tree の中間ノード */8:for ∀Nj ∈ N ode do

9:if amindist(Nj , Gi ) < best dist[k − 1] then10:

if amaxdist(Nj , Gi ) < best maxdist then

同様に ymax と ymin は Y 座標の最大値と最小値である.

′

x = (x − xmin )/(xmax − xmin )′if amindist(Nj , Qc) < best dist[k − 1] then11:y = (y − ymin )/(ymax − ymin )best maxdist ← amaxdist(Nj , Gi] )+adist(Gi , Q)13:/* best maxdist の更新 */実験は問い合わせ集合 Q の数 n，クエリの分布範囲 A(Q)，
各手法の結果を比較する. 実験で用いた各パラメータの値は表

end if

15:

18:

(13)

次元 D，k ，f = sum の場合はクエリ分割数 div を変化させ,

end if

14:

17:

(12)

H.push(Nj )

12:

16:

用いて座標値を変換し,(0,1) の範囲に正規化した. ここで xmax1 に示す.

end ifend for

表 1 パラメータ

else if N ode.isLeaf then

パラメータ

値

19:

/* N ode は R-tree の葉ノード */n = |Q|16, 32, 64, 128, 256, 512

20:

for ∀pj ∈ N ode doA(Q)0.01, 0.09, 0.16, 0.25, 0.49, 1

21:

if amindist(pj , Gi ) < best dist[k − 1] then22:

if adist(pj , Qc) < best dist[k − 1] thenbest N N [k − 1]23:←

pj ; best dist[k − 1]←D2, 4, 8, 16k

1, 5, 10, 15, 20

div

1, 5, 10, 15, 20, 25

adist(pj , Q) /* 候補 ANN の解の更新 */end if

24:
25:
26:

end ifend for27:

end if28:

N ode ← H.pop()

8. 3 実 験 結 果
以下の実験結果は, ランダムに生成したクエリ点に対して 100回の実験を行い, その平均を取ったものである.

29: end while
30: return (best N N )（注 1）：http://download.osgeo.org/libspatialindex/spatialindex-src-1.8.1.tar.gz（注 2）：populated places,http://www.rtreeportal.org/

[a]f = sum (div=20)[b]f = max

図 4 vary k (n = 128, A(Q) = 1.0, dim = 2)[a]f = sum (div=2)[b]f = max

図 6 vary n (A(Q) = 1.0, dim = (2or8), k = 20, div = 20)[a]f = sum (div=2)[b]f = max

図 7 vary area (n = 128, dim = (2or8), k = 20, div = 20)

8. 3. 1 合成データの比較である．この結果から，sum は，n のサイズが大きくな

図 4 は k を変化させたときの，拡張 MBM 手法と提案手法

るにつれて，拡張 MBM は性能が低下しているが，提案手法はの実行速度の比較である．f = max において MBM が k が増

変わらず高速であることが分かる．また，sum 右図の高次元

加するにつれて性能低下しているが，提案手法は変わらず高速においても同様に提案手法が高速であることが分かる．また，であることが見て取れる．

max は，左図 dim = 2 の場合，n のサイズが大きくなるにつれて，拡張 MBM と比べて提案手法が高速であることが分かる．しかし，右図 dim = 8 においては，提案手法はあまり効果がない事が分かる．これは，高次元においては，ほぼ全てのクエリ点が凸包頂点候補となってしまうためであると考えられる．
図 7 は，dim = 2 と dim = 8 のとき，クエリの分布範囲

A(Q) を変化させたときの実行結果の比較である．sum は，左図 dim = 2 のとき，A(Q) が小さい場合において，提案手法が
図 5 vary div (n = 128, A(Q) = 1.0, dim = 2, k = 20)

拡張 MBM よりも遅くなる場合が存在する．これは，Q の分布
範囲が狭い場合において，クエリを分割する手法があまり有効

図 5 はクエリの分割数 div を変化させたときの提案手法の実行でないからだと考えられる．右図 dim = 8 のときにおいては，速度である．div = 20 までは速度は向上しているが，div = 25

重心との距離を用いた刈り取りが有効であり，どの分布範囲にでは div = 20 よりも遅くなっている．これは，クエリの分割

おいても高速である．max は，左図 dim = 2 のときは，A(Q)によって削減できる距離回数計算の数と，分割することで増えが大きいほど提案手法が有効であることが分かる．これは，分た各重心との距離計算回数が逆転したものと思われる．

布範囲が広いほうが凸包頂点候補となる点が少なくなるためだ

図 6 は dim = 2 と dim = 8 のとき，クエリ集合 Q のサイズ

n を変化させたときの，拡張 MBM 手法と提案手法の実行速度と考えられる．右図 dim = 8 においては，ほぼ全てのクエリ点

[a]f = sum (div=2)[b]f = max

図 8 vary dim (n = 128, A(Q) = (0.25or1.0), k = 20)[a]vary n (A(Q)=1.0, dim=2, k=20, div=20)[b]vary area (n=128, dim=2, k=20, div=20)
図9 実データが凸包頂点候補となってしまいうため，分布範囲が広くなっても差は見られないが，重心距離との刈り取りによって一定の高速化が成されているのが分かる．
図 8 は，A(Q) = 0.25 と A(Q) = 1.0 のとき，次元 dim を変化させたときの，実行速度の比較である．sum はどちらにおいても提案手法が高速であり，次元や分布範囲に依らず提案手法が有効であることが分かる．
しかし max は，高次元になるにつれ，提案手法が拡張 MBMに近づいているのが分かる．これらの結果から，重心距離との刈り取りは，集約距離 max においてはあまり効果的でないと考えられる．

8. 3. 2 実 デ ー タ
図 9 は，実データに対して，クエリの分布範囲 A(Q) とクエ
リサイズ n を変化させたときの実行速度の比較である．n については，左図の sum が合成データと比べて提案手法の効率が落ちているのが分かる．これは，クエリを分割する手法が，特に一様分布のような広い分布のデータに対して効率的であるためと考えられる．A(Q) においては，sum，max 共におおよそ合成データと同じ傾向が見られる．

9. ま と め
本研究では ANN 検索の拡張として，AkNN 検索を提案した．AkNN の解を高速に求めるために，重心との距離による刈り取り手法，R-tree のノードとの距離を用いた刈り取り手法，
クエリの前処理による手法を提案した．実験から，集約距離

sum においては，低次元かつクエリの分布範囲が狭い場合以外
では，提案手法が高速であることを示した．しかし，集約距離

max においては，低次元では凸包の性質利用による手法が効果的であることを示したが，高次元においては効果が薄いことも分かった．
更なる効率化や，各手法の効率が落ちる場合での効果的な手法の提案が今後の課題となる．

文

献[1] D. Papadias, Y. Tao, K. Mouratidis and C. Kit Hui. Group
Nearest Neighbor Queries. In: ICDE, pp.301-312(2004)[2] D. Papadias, Y. Tao, K. Mouratidis and C. Kit Hui. Aggregate Nearest Neighbor Queries in Spatial Databases. ACM
Trans. Database Syst. 30(2), 529-576(2005)[3] H. Chen, R. Shi, K. Furuse and N. Ohbo. Finding RkNN
Straightforwardly with Large secondary Storage. In: INGS,
pp.77-82(2008)[4] Y. Luo, J. Liu, C. Lian and H. Chen. Finding RkNN
by Compressed Straightforward Index. In: ISKE, pp.279284(2008)[5] Y. Luo, H. Chen, K. Furuse and N. Ohbo. Eﬃcient Methods
in Finding Aggregate Nearest Neighbor by Projection-Based
Filtering. In: ICCSA, pp.821-833(2007)[6] 連 燦紅. On eﬃcient approximate aggregate nearest neighborsearch.. 筑波大学コンピュータサイエンス専攻修士論文,(2012)[7] H. Li, H. Lu, B. Huang and Z. Huang. Two Ellipse-based
Pruning Methods for Group Nearest Neighbor Queries. In:
GIS, pp192-1999(2005)[8] M.Yiu, N. Mamoulis and D. Papadias. Aggregate Nearest
Neighbor Queries in Road Networks. IEEEE Trans. Knowl.
Data Eng. pp820-833 (2005)[9] S. Namnandorj, H. Chen, K. Furuse and N. Ohbo. Eﬃcient Bounds in Finding Aggregate Nearest Neighbors. In:
DEXA, pp.693-700(2008)[10] L. Zhu, Y. Jing, W. Sun and P. Liu. Voronoi-Based Aggregate Nearest Neighbor Query Processing in Road Networks
In: GIS, pp518-521(2010)[11] F. Li, B. Yao and P. Kumar. Group Enclosing Queries. In:
TKDE, pp, 1526-1540 (2011)[12] Haitao Wang. Aggregate-MAX Top-k Nearest Neighbor
Searching in the L1 Plane. Int. J. Comput. Geometry Appl.
25(1): 57- (2015)[13] Maytham Safar. Group K -Nearest Neighbors queries inspatial network databases. Journal of Geographical Systems
10(4): 407-416 (2008)[14] Camila Ferreira Costa, Javam C. Machado, Mario A. Nascimento, Jos Antnio Fernandes de Macdo. Aggregate knearest neighbors queries in time-dependent road networks.
MobiGIS 2015: 3-12