空間インデックスを用いたk-NN検索アルゴリズム 指導教官

ICS-07B-357
空間インデックスを用いた k-NN 検索アルゴリズム
指導教官
大沢 裕 教授
平成１９年２月１９日提出
工学部情報システム工学科
油井 真斗
埼玉大学工学部情報システム工学科 大沢研究室
埼玉県さいたま市桜区下大久保 255
概要
k-NN(k Nearest Neighbor) 検索は，空間上に指定された質問点に近接するオブ
ジェクトを，空間データベースの中から k 個求める演算である．このような演算は
空間データ構造を用いることで効率よく実行でき，すでに R 木や R*木などのデー
タ構造を対象として多くの研究が行われている．一方，GBD 木と呼ばれる空間デー
タ構造が提案されている．GBD 木は，領域式と呼ばれる座標表現方式を用いるこ
とで，効率の良いデータ管理と検索が可能なデータ構造である．本研究では，この
GBD 木に注目し，GBD 木に適した k-NN 検索アルゴリズムを考案する．そして，
GBD 木における k-NN 検索の性能を他構造 (R 木および R*木) と比較し，その性能
を評価する．
目次
概要
i
第 1 章 はじめに
1
1.1 背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.3 本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
第 2 章 関連研究
3
2.1 空間データ構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.1
R木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.2
R*木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1.3
基本的な検索 . . . . . . . . . . . . . . . . . . . . . . . . . .
5
GBD 木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.1
概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.2
空間の分割方法と領域式 . . . . . . . . . . . . . . . . . . . .
6
2.2.3
GBD 木の構造 . . . . . . . . . . . . . . . . . . . . . . . . . .
8
k-NN 検索アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3.1
深さ優先探索による k-NN アルゴリズム . . . . . . . . . . .
8
2.3.2
枝刈りの改良 . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2
2.3
第 3 章 GBD 木のための k-NN 検索アルゴリズム
i
15
3.1 最近接オブジェクトの検索 . . . . . . . . . . . . . . . . . . . . . . .
15
3.1.1
葉ノードにおける処理 . . . . . . . . . . . . . . . . . . . . .
17
3.1.2
ソート方法の改良 . . . . . . . . . . . . . . . . . . . . . . . .
18
3.1.3
ノードの探索順序の検討 . . . . . . . . . . . . . . . . . . . .
18
3.1.4
改良アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . .
20
k-NN 検索への拡張 . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.2
第 4 章 最良優先探索による k-NN 検索
24
4.1 概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2 問題点とその解決方法 . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.3 優先順位付きキュー . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.4 アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
第 5 章 実験
31
5.1 実験方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.2 実験結果および考察 . . . . . . . . . . . . . . . . . . . . . . . . . .
33
5.2.1
深さ優先アルゴリズム . . . . . . . . . . . . . . . . . . . . .
33
5.2.2
最良優先アルゴリズム . . . . . . . . . . . . . . . . . . . . .
41
第 6 章 おわりに
44
謝辞
45
参考文献
46
ii
第1章
1.1
はじめに
背景
k-NN(k Nearest Neighbor) 検索とは，空間データベースの中から，指定された点
(あるいはオブジェクト) に近接する空間オブジェクトを近い順に k 個求める演算で
ある．k-NN 検索は GIS(Geographic Infomation System:地理情報システム) や CAD
の分野における基本的かつ重要な演算のひとつであるため，これまでに多くの研究
が行われてきた．
k-NN 検索を高速に行うための手段のひとつとして，空間データ構造を用いたイン
デックス作成が挙げられる．空間データ構造とは，空間データベースを互いに近接
性のあるデータから成るグループ (ページと呼ぶ) に分割し，データ検索を効率化す
るためのデータ構造である．現在広く用いられている空間データ構造として，R 木
[4] やその改良型である R*木 [1] などが挙げられる．これらのデータ構造を対象とし
て，Roussopoulos らは深さ優先探索に基づいた k-NN 検索アルゴリズムを提案して
いる [8]．これは，木の各レベルにおいて検索点に最も近接するノードを選択しつつ
木を下に向かって辿り，近接オブジェクトを探す手法である．また，Hjaltason[5] や
Berchtold[2] らは，優先順位付きキューにノードを挿入することによって，常に最良
な順序で木の探索を行うことが可能な方式を提案している．このような手法は，先
に述べた深さ優先 (depth-first) 探索に対して，最良優先 (best-first) 探索と呼ばれる．
1.2
目的
大沢研究室では，空間および時間データを扱うことが可能な GIS として，STIMS(SpatioTemporal Information Management System:時空間情報管理システム) の研究開発
を行っている．STIMS では，データ検索を効率よく行うため，GBD 木 [9] と呼ば
れる空間データ構造を採用している．GBD 木は，領域式と呼ばれる座標表現方式
1
に基づいて空間分割を行うデータ構造で，R 木よりも高速なインデックス作成およ
び検索が可能である．
本研究では，この GBD 木に着目し，GBD 木に適した k-NN 検索アルゴリズムを
模索する．そして，考案手法の性能を他構造 (R 木と R*木) との比較実験を行うこ
とにより評価する．
1.3
本論文の構成
本論文は全 6 章から成る．その構成は以下の通りである．
第 2 章では，空間データ構造の概要および k-NN 検索に関する先行研究について
まとめる．
第 3 章では，GBD 木のための k-NN 検索として，深さ優先探索に基づいたアルゴ
リズムを提案する．
第 4 章では，最良優先探索に基づいた手法として，ディスクアクセスを低く抑え
ることを目的とした k-NN 検索アルゴリズムを考案する．
第 5 章では，第 3 章および第 4 章で述べたアルゴリズムを実装し，その性能を検
証する．
第 6 章では，本研究のまとめを行う．
2
第2章
関連研究
本章では，空間データ構造の概要と，k-NN 検索に関する先行研究についてまと
める．はじめに，代表的な空間データ構造のひとつである R 木およびその改良型の
R*木について述べ，本研究の対象である GBD 木について説明する．続いて，k-NN
検索に関する研究の 1 つとして，R 木を用いた深さ優先探索によるアルゴリズムに
ついて説明する．
2.1
2.1.1
空間データ構造
R木
R 木 [4] は，多次元データを効率よく管理するために提案されたデータ構造であ
る．R 木は，B 木の考え方を多次元に拡張した構造で，2 次元以上のデータを扱うこ
とを可能としている．B 木と同様，R 木は根ノードからすべての葉ノードまでの距
離が等しい完全平衡木である．R 木の各ノードは，M 個のスロットから構成される．
非葉ノードの場合，各スロットは，子ノードへのポインタと，その子ノード以下に含
まれるすべてのデータを包含する長方形を保持する．この長方形を MBR(Minimal
Bounding Rectangle) と呼ぶ．葉ノードの場合は，オブジェクトへのポインタおよ
びすべてのオブジェクトを包含する MBR となる．各葉ノードおよび非葉ノードは，
根ノードを除いて，必ず m 個以上のスロットに子ノードあるいはオブジェクトが格
納される．m は M の 30∼40%程度に設定される．
図 2.1 に M = 3 の場合における R 木の構成例を示す．同図上の a∼j はオブジェ
クトの MBR を，A∼F はノードを表す．また，破線の長方形は各ノードに対応する
MBR を表している．この階層構造を図で表現すると同図下のようになる．図の例
では，4 つの葉ノードおよび 3 つの非葉ノードから構成され，木の高さは 2 となる．
オブジェクトを木に追加する過程で，ノードの分割が生じると，R 木では分割後
の２つの MBR の面積の合計が最小となるような組み合わせを求めて分割する．そ
3
図 2.1: R 木の構成例 (上:MBR の構成，下:木構造)
のため，分割の結果によっては，2 つの MBR 間に重なり (オーバーラップ) が生じ
ることがある．
2.1.2
R*木
前節で述べたように，R 木では，MBR の面積を基準にノード分割を行うため，
ノード間にオーバーラップが生じたり，細長い MBR が生じたりする場合が多い．
R*木 [1] では，R 木のこのような性質を改善するため，MBR の面積だけでなく，周
囲長や MBR 同士の重なりに注目したデータ投入を行う．これらのパラメータに注
目することによって，R 木と比較して MBR がより正方形に近く，MBR 同士の重な
りが少ない木を生成することができる．
R*木におけるデータ挿入アルゴリズムのもう一つの特徴は，ノードのあふれが生
じたときに，そのノード中のエントリの一部を再挿入する点である．これは，R 木
において，無作為に削除したデータを再び木に挿入したとき，検索性能が向上する
4
という実験結果に基づいている．R*木では，データの投入によってノードにあふれ
が生じると，ノードの MBR の中心点から遠くにあるエントリの一部をそのノード
から削除し，再挿入する．再挿入されたエントリは，以前と同じノードに配置され
るか，またはより適した (より MBR 間の重なりが少なくなるような) ノードに置か
れる．
R*木におけるデータ挿入のアルゴリズムは，R 木と比較して非常に複雑である
が，R 木よりも検索性能が良い．
2.1.3
基本的な検索
R 木や R*木などのデータ構造を用いて，ある与えられた矩形領域 R 内に含まれ
るすべてのオブジェクトを取得する方法について述べる．このような処理は範囲検
索 (range query, window query) と呼ばれ，GIS において頻繁に行われる演算のひと
つである．基本的には，各ノードの MBR と指定領域との重なりの有無を調べ，重
なる場合のみそのノードを辿ればよい．
範囲検索
rangeSearch(node : Node, rect : Rectangle, list : List of Object)
1: node が葉ノードの場合，node 中のすべてのオブジェクト obj に対して，以下の
処理を行う．
1-1: obj と rect が重なる場合，obj を list に追加する．
2: node が非葉ノードの場合，node 中のすべての子ノードエントリ child に対して，
以下の処理を行う．
2-1: child の MBR と rect が重なる場合，rangeSearch(child, rect, list) を実行する．
引数リストの node は検索対象となるノードを，rect は検索範囲をあらわす矩形
領域を，list は検索結果を格納するリストを表す．範囲検索を行うときは，根ノー
ドを指定してこの処理を実行する．
5
2.2
2.2.1
GBD 木
概要
GBD 木 [9] は R 木やその改良型と同様，階層的にデータの存在する空間の分割を
行い，その分割過程を木構造で管理する多次元データ構造である．GBD 木は R 木
と同様に完全にバランス化された木構造で管理される．R 木はデータの投入削除や
検索を MBR のみを用いて行うが，GBD 木では領域式と呼ばれる位置の表現方式を
用いて投入削除およびノード分割を行う．領域式についての詳細は後述するが，空
間上の位置および大きさを表すためのビット列として表現される．各図形オブジェ
クトはその中心点の領域式によって投入される位置が決定される．
GBD 木の各ノードは M 個のスロットから構成され，各スロットは対応する子
ノードへのポインタと，そのノードの MBR および領域式を補助情報として持つ．
葉ノードの場合，全スロットのうち (M + 1)/3 個以上がオブジェクトで埋まってい
ることが保証されている．
GBD 木や R 木などのデータ構造では，できるだけ多くのスロットが子ノードま
たはオブジェクトに割り当てられている方が，木全体のノード数および段数を抑え
られるため効率が良い．GBD 木では，根を除くノードにおいて平均で 70 ％前後の
スロットが有効に使われていることが実験によって示されている．これは R 木と比
較して高い数値であり，効率の良いデータ構造といえる．また，GBD 木ではデー
タ投入やノード分割を領域式を用いて行うため，R 木や R*木よりも初期構築を高
速に行うことが可能である．
2.2.2
空間の分割方法と領域式
GBD 木で管理する領域の形は分割座標軸を巡回的に替えながら，面積二等分割
を繰り返すことにより得られる正方形，または縦横比が 1:2 の長方形である．領域
式は「0」，
「1」および終了を表す記号「＊」で表現される．
図 2.2 に GBD 木における領域の分割過程と対応する領域式の例を示す．
1. 領域式中のビット「0」は空間を二等分割したときの座標原点に近い側の領域
に，
「１」は遠い側の領域に対応している．図 2.2 の場合，y 軸と平行な軸で二
等分割したとき，左半分が「0」，右半分が「1」となり，x 軸と平行な軸で二
等分割したとき，下半分が「0」，上半分が「1」となる．
6
図 2.2: 領域式の概要
2. 領域式の最も左側のビットが最初の空間分割に対応しており，右側にいくに
従いより小さな領域の分割に対応している．
図 2.2 における領域「10 ＊」を例にとると，y 軸に平行な軸で二等分割したうちの
右半分を，さらに x 軸に平行な軸で二等分割したうちの下半分となる．
領域式に対して，以下の順序関係を定める．この関係は，ノード中のスロットの
並び順を決定するために用いられる．
定義 2.1 (領域式の順序関係) それぞれの長さが n1 ，n2 ，(n1 ≥ n2 ) の領域式 R1 ，
R2 において，
1. R1 の上位 n2 ビットが R2 に一致するとき，R1 < R2 とする．
2. 上位 n2 ビット目までに R1 と R2 のパターンに不一致があるとき，一致しない
最初のビットが「0」の方を小さいものとする．
R1 を「01101 ＊」，R2 を「0110 ＊」とすると，上位 4 ビットが一致しており，か
つ R1 のビット長のほうが長いため，R1 < R2 となる．また，R1 を「10110 ＊」，R2
を「100 ＊」とすると，3 ビット目のパターンが異なり，R2 の 3 ビット目が「0」で
あるため R1 > R2 となる．
7
次に，領域式の包含関係を示す．この包含関係は，オブジェクトが木に投入され
る際に，格納されるべき葉ノードを決定するために用いられるほか，3 章で述べる
k-NN 検索においても用いられる．
定義 2.2 (領域式の包含関係) それぞれの長さが n1 ，n2 ，(n1 ≥ n2 ) である領域式
R1 ，R2 において，R1 の上位 n2 ビットが R2 と一致するとき，R1 は R2 に包含され
るといい，R1 ⊂ R2 と表現する．
たとえば，R1 を「1001 ＊」，R2 を「100 ＊」とするとき，R1 のほうがビット長
が長く，R1 の上位 3 ビットが R2 と一致しているため，R1 ⊂ R2 となる．
2.2.3
GBD 木の構造
図 2.3 に GBD 木の構成例を示す．図の a∼l はオブジェクトの MBR を表してい
る．また，A∼G は葉ノードまたは非葉ノードであり，外枠の長方形はそれぞれに
対応する MBR を表す．これらを木構造で表現すると同図下のようになる．図のよ
うに，各スロットは対応する領域式を補助情報として持っている．例えば，ノード
D の領域式は「0110 ＊」となる．GBD 木ではノード中のスロットの整列方法に以
下のような規則を設けている．
1. ノード中のスロットは，対応する領域式の大小関係に従い，昇べきの順に整
列される．例えば，図 2.3 のノード A 中のスロットは，
「00 ＊」，
「0110 ＊」，
「0
＊」の順序で整列されている．
2. 各ノードの最終スロットには，そのノード自身に対応する全領域の領域式が
置かれる．すなわち，最終スロットの領域式はそのノード自身の領域式と一
致する．図 2.3 を例にとると，ノード A とその最終スロットに格納されてい
るノード E は共に「0 ＊」となる．また，根ノードの最終スロットである B は
全領域の領域式と一致していなければならないため「＊」となる．
2.3
2.3.1
k-NN 検索アルゴリズム
深さ優先探索による k-NN アルゴリズム
空間インデックスを用いて k-NN を求めるための手法として，深さ優先探索によ
るアルゴリズムが提案されている．この手法では，木の根ノードから探索を開始し，
8
図 2.3: GBD 木の構成例 (上:MBR の構成，下:木構造)
最近接オブジェクトを含む可能性が高いノードを選択しながら木を下方に辿る操作
を再帰的に繰り返しつつ，最近接オブジェクトを探す．Roussopoulos らは，ノード
の選択方法として，検索点 Q から MBR までの最小距離 (MINDIST) が小さいもの
を優先的に辿る手法を提案している [8]．このアルゴリズムを説明する前に，幾つか
の必要な定義について述べる．
定義 2.3 (MBR) n 次元空間において，ある MBR を R とするとき，R の各座標軸
における両端点を S および T とすると，R は以下のように定義される．
R = (S, T )
ただし，S = [s1 , s2 , · · · , sn ]，T = [t1 , t2 , · · · , tn ] であり，1 ≤ i ≤ n に対して si ≤ ti
である．
9
定義 2.4 (MINDIST) ある点 P と MBR R との最小距離 M IN DIST (P, R) は次
のように定義される．
v
u n
uX
M IN DIST (P, R) = t |pi − ri |2
i=1



 si
if pi < si
if pi > ti
otherwise.
ri =  ti


pi
定義より，R 内に含まれるオブジェクトの中で最も検索点 Q に近いものへの距離
を dist とすると，M IN DIST (Q, R) は dist の取りうる最小値 (下界) となる
(M IN DIST (Q, R) ≤ dist)．
次に，dist の取りうる最大値 (上界) を知るため，MINMAXDIST を導入する．
定義 2.5 (MINMAXDIST) ある点 P と MBR R に対して，M IN M AXDIST (P, R)
を次のように定義する．
s
M IN M AXDIST (P, R) =
1≤k≤n
(
rmk =
(
rMk =
X
min (|pk − rmk |2 +
|pi − rMi |2 )
i̸=k,1≤i≤n
sk if pk ≤ (sk + tk )/2
tk otherwise.
sk if pk ≥ (sk + tk )/2
tk otherwise.
M IN M AXDIST (Q, R) は，R 中で最も Q に近接するオブジェクトの距離の最大
値 (上界) となる．したがって，M IN DIST (Q, R) ≤ dist ≤ M IN M AXDIST (Q, R)
が成立する．これは，MBR の各辺に少なくとも一回は内部オブジェクトが接して
いるためである．
図 2.4 に，二次元平面における MINDIST および MINMAXDIST の様子を示す．
図の MBR C のように，点が MBR の内部にある場合は MINDIST は 0 となる
(M IN DIST (Q, C) = 0)．
MINDIST と MINMAXDIST を用いれば，検索中に辿る必要がない (最近接オブ
ジェクトを含まない) ノードを枝刈りすることが可能である．以下に，3 つの可能な
枝刈り方法を示す．
10
図 2.4: MINDIST と MINMAXDIST
H1: M IN DIST (Q, A) > M IN M AXDIST (Q, B) となるような MBR A，B が同
一ノード内に存在するとき，A は最近接オブジェクトを含まないため枝刈り
する (下方向枝刈り)．
H2: ある時点における最近接オブジェクトの候補を O とする．Q と O との距離が
ある MBR R の M IN M AXDIST (Q, R) より大きい場合，R 中に O より近い
オブジェクトが存在するため O を捨てることができる (上方向枝刈り)．
H3: ある MBR R に対して，M IN DIST (Q, R) が Q と O との距離より大きい場
合，R は最近接オブジェクトを含まないため枝刈りする (上方向枝刈り)．
以下に，上記の枝刈りを利用した 1-NN 検索アルゴリズムを示す．
R 木における最近接オブジェクトの検索
nearestNeighborSearch(node : Node, q : Point, nearest : Nearest)
1: node が葉ノードの場合，node 内の各オブジェクト obj に対して，以下の処理を
繰り返し行う．
1-1: obj と q との距離が nearest の距離以下であれば，nearest を obj で更新する．
2: node が非葉ノードの場合，以下の処理を行う．
11
図 2.5: R 木における NN 検索
2-1: node 内のすべての子ノードエントリを含む ActiveBranchList を作成する．
2-2: ActiveBranchList を MINDIST の昇順にソートする．
2-3: 下方向枝刈りを実行する．
2-4: ActiveBranchList の先頭より順番にエントリ child を取り出しながら，以下の
処理を繰り返し行う．
2-4-1: nearestNeighborSearch(child.node, q, nearest) を実行する．
2-4-2: 上方向枝刈りを実行する．
引数リストにおける node は探索対象となるノード，q は検索点，nearest は最近
接オブジェクト (の候補) となる．この処理を実行する前に，あらかじめ nearest の
距離を ∞ としておく必要がある．
このアルゴリズムの具体的な処理の流れを，図 2.5 の R 木を例に説明する．図に
おける Q は検索点である．まず，根ノードから探索を開始する．根ノードは非葉
ノードなので，ActiveBranchList を作成する．ノード A，B はともに MINDIST が
12
0 で等しいため，リストの内容は [A, B] となる．したがって，ノード A を辿る．ノー
ド A において，BranchList を作成し，MINDIST 順でソートすると，[D, C] となる．
次はノード D が選択される．ノード D は葉ノードなので，最も近接するオブジェ
クトを探す．この場合は c が最近接オブジェクトの候補となる．木を上方向に辿る
と，ノード C が残っているが，M IN DIST (Q, C) は c の距離より大きいため枝刈
りされる．ノード A の探索が終了したので，根ノードに戻る．根ノードにはノード
B が残っているが，B の MINDIST は 0 なので辿られる．ノード B では F が最初
に辿られる．F を調べると，h が c より近くに位置しているので，最近接オブジェ
クトの候補を h に更新する．ノード E は枝刈りされ，すべての探索が終了する．結
果，最近接オブジェクトの解は h となる．
2.3.2
枝刈りの改良
2.3.1 節で述べた深さ優先アルゴリズムでは，3 つの枝刈りによる手法を提案して
いるが，[3] によれば，MINMAXDIST を用いた枝刈り (H1 および H2) は不要であり，
これらの枝刈りを行わなくても探索ノード数には影響を及ぼさない．MINMAXDIST
の計算には，O(d)(d は次元数) のコストがかかるため，特に高次元空間における検
索においては，MINMAXDIST の計算を行わないほうが高速化できる可能性がある．
以下に，枝刈り方法を改良した NN 検索アルゴリズムを示す．このアルゴリズム
では，H1 と H2 による枝刈りは行わず，H3 による枝刈のみを行う．
R 木における最近接オブジェクトの検索 (改良版)
nearestNeighborSearch(node : Node, q : Point, nearest : Nearest)
1: node が葉ノードの場合，node 内の各オブジェクト obj に対して，以下の処理を
繰り返し行う．
1-1: obj と q との距離が nearest の距離以下であれば，nearest を obj で更新する．
2: node が非葉ノードの場合，以下の処理を行う．
2-1: node 内のすべての子ノードエントリを含む ActiveBranchList を作成する．
2-2: ActiveBranchList を MINDIST の昇順にソートする．
2-3: ActiveBranchList の先頭より順番にエントリ child を取り出しながら，以下の
処理を繰り返し行う．
2-3-1: 枝刈り (H3) を実行する．
13
2-3-2: nearestNeighborSearch(child.node, q, nearest) を実行する．
MINMAXDIST による枝刈りが不要である理由について簡単に説明する．以下，
ノード N の MINDIST，MINMAXDIST をそれぞれ M IN DISTN ，M IN M AXDISTN
と表記する．あるノード内において，M IN M AXDISTB < M IN DISTA となるよ
うな兄弟ノード A, B が存在する場合を仮定する．2.3.1 節のアルゴリズムを用いれば，
H1 によってノード A は枝刈りされる．MINMAXDIST の性質より M IN DISTB <
M IN M AXDISTB であるため，M IN DISTB < M IN DISTA であることは明らか
である．したがって，ノード A より先にノード B が辿られる．ノード A が辿られる
直前における最近接オブジェクトの候補の距離を disttemp とする．この時点でノー
ド B が探索されているため，
disttemp ≤ M IN M AXDISTB
が成立する．よって，条件 M IN M AXDISTB < M IN DISTA より，
disttemp < M IN DISTA
である．よって，ノード A は H3 によって枝刈りされる．
このように，H1 によって枝刈りされるノードは，H1 の枝刈りを行わなくても必
ず H3 によって枝刈りされるため，MINMAXDIST は不要である．
14
第3章
GBD 木のための k-NN 検索ア
ルゴリズム
本章では，本研究で提案する GBD 木のための k-NN 検索アルゴリズムについて
述べる．GBD 木においては，その特徴である領域式を活用することによって，検
索を効率化できる可能性がある．以下ではその手法について説明したのち，より処
理を効率化するための改良方法について述べる．
3.1
最近接オブジェクトの検索
GBD 木において，オブジェクトを木に投入する場合，まず，オブジェクトの中
心点の領域式を求めておく．そして，その領域式を包含する領域式を持つノードを
選択しつつ木を下方に辿り，投入する葉ノードを決定する．したがって，あるオブ
ジェクトを見つけるためには，その中心点の領域式を求め，その領域式を用いて投
入時と同じ処理を行えばよい．
この性質から，ある点 Q に近接するオブジェクトを探す場合，Q の領域式を包含
するノードを選びつつ葉ノードまで辿れば，そこに最近接オブジェクトが含まれて
いる可能性が高いと考えることができる．そして，一度葉ノードに到達した後は，R
木と同様に MINDIST が小さいノードを優先して辿りながら，より近くにオブジェ
クトが存在するかどうかを検証する．
一般的に，ある領域式を包含する領域式をもつ子ノードは同一ノード内に複数存
在する．このような場合には，包含する領域式の中で最も小さい (最も長い) ものを
選ぶ．これは，GBD 木のノード分割の性質に因るものである．図 3.1 は，GBD 木
における葉ノード分割の例を示している．この例ではページサイズを 6 としている．
「00 ＊」で表されるノードに，ページサイズを上回る 7 個目のデータ g が投入され
ると，オブジェクトをそれぞれの領域式に従って 2 つのグループ (先頭が「000」の
ものと「001」のもの) に分ける．このとき，分配結果がアンバランスであれば，多
15
図 3.1: GBD 木における葉ノード分割の例
いほうのグループをさらに 2 分割していく操作を，バランスの良い分配が得られる
まで繰り返す．そして，最後の 2 分割において分割後のデータ個数が多かった領域
(「0010 ＊」) と，分割前のノードと同じ領域 (「00 ＊」) でノード分割を実行する．
非葉ノードの分割方法は葉ノードの場合と異なるが，分割前の領域式とそれより小
さい領域式で分割される点は共通である．
したがって，検索点の領域式が「0010· · · ＊」であった場合には，
「00 ＊」を辿る
前に，より内側で内包している「0010 ＊」を辿ったほうが，最近接オブジェクトを
早く発見できる可能性が高く，効率が良くなると期待できる．各ノードのスロット
は領域式の大小関係に従ってあらかじめ整列されているため，先頭スロットから順
に領域式を検証し，検索点の領域式を包含する最初のスロットを辿るという単純な
操作によって，この処理は実現できる．
16
以下に，GBD 木における 1-NN 検索の基本的な流れを示す．その後，処理をより
効率良く行うための改良方法を説明する．
GBD 木における 1-NN 検索 (基本)
NearestNeighborSearch(node : Node, q : Point, nearest : Nearest)
1: node が葉ノードの場合，node に置かれているすべてのオブジェクト obj に対し
て，以下の処理を行う．
1-1: q と obj との距離が nearest の距離より小さい場合，nearest を obj で更新する．
2: node が非葉ノードの場合，以下の処理を行う．
2-1: node に置かれている子ノードのリストを先頭から走査し，q の領域式を包含
する領域式をもつ最初のノード child を探す．
2-2: NearestNeighborSearch(child, q, nearest) を実行する．
2-3: まだ辿っていない子ノードを，q との MINDIST の昇順にソートする．
2-4: 2-3 で作成したリストの先頭から順に要素 child を取り出し，以下の処理を繰
り返す．
2-4-1: child と q との MINDIST が nearest の距離以下であれば，NearestNeighborSearch(child,
q, nearest) を実行する．
2-4-2: 2-4-1 に該当しない場合は，繰り返し処理を終了する．
3.1.1
葉ノードにおける処理
NN 検索では，葉ノードに格納されているオブジェクトの中から最近接オブジェ
クトを探す必要がある．扱うデータが点などのシンプルなものであれば，この処理
は簡単に行うことが可能である．しかし，ポリラインのような複雑なデータを扱う
場合で，なおかつそのデータが外部ファイルに記録されているようなシステムを用
いる場合，そのオブジェクトを読み込むコストや，ポリラインと点との距離を求め
るコストが発生する．ポリラインの頂点数を n とすると，距離を求めるには O(n)
のコストがかかる．また，頂点数が多ければ，その分読み込むデータのサイズが大
きくなるため入出力コストがかかる．このため，オブジェクトとの実距離を求める
回数を削減することで，処理の効率化が期待できる．
そこで，葉ノードの各エントリに対して，その MBR との MINDIST を求め，MINDIST
が現在の候補の距離以下の場合にのみ，オブジェクトにアクセスし，距離を求める
17
ように改良する．このように変更することによって，実際の距離を計算する回数を
削減することが可能である．
また，葉ノードにおいても中間ノードと同様に，各エントリをあらかじめ MBR
の MINDIST の昇順にソートすることによって，さらにオブジェクトへのアクセス
回数を削減できる可能性がある．MINDIST が小さいオブジェクトほど実距離も小
さいと期待できるためである．第 5 章でこの 2 つの改良手法を用いた場合の性能を
検証する．
3.1.2
ソート方法の改良
非葉ノードにおいては，検索点の領域式を包含するノードを辿った後は，MINDIST
が小さいノードを優先的に辿る．そのため，すべての子ノードを MINDIST の昇順
でソートする必要があるが，ページサイズが大きい場合にはこのソート処理にコ
ストがかかる場合がある．もし，最近接オブジェクトの候補がすでに見つかってお
り，その距離が dist であるなら，M IN DIST (Q, R) > dist となるノード R は辿る
必要がないため枝刈りが可能である．そこで，ソートの前にあらかじめ不要なノー
ドを枝刈りしておくことで，ソートにかかるコストを低減することが可能である．
図 3.2 にその例を示す．図中の A から G は同一ノード内の子ノードを，Q は検索点
を表す．現在の候補の距離が dist であるとき，MINDIST が dist より大きいノード
A, D, E, G は辿る必要がないことが分かっているのであらかじめ枝刈りする．そし
て，残されたノード B, C, F を MINDIST の昇順でソートすればよい．
3.1.3
ノードの探索順序の検討
GBD 木や R 木などのデータ構造においては，各ノード間の MBR に重なり (オー
バーラップ) が生じることが多い．もし，MBR の重なっている部分に検索点が置か
れた場合，MINDIST が 0 となるノードが複数生じるため，従来の手法ではどのノー
ドを優先的に辿るかが曖昧になる．
MINDIST が等しいノードが複数存在する場合，どのノードを優先するかによっ
て合計探索ノード数が変化する場合がある．その一例を図 3.3 に示す．図中の A1 か
ら A3 はノード A の子ノードを，B1，B2 はノード B の子ノードを表しており，Q
は検索点である．Q は A および B の内部に位置しているため M IN DIST (Q, A) =
M IN DIST (Q, B) = 0 である．よって，次の 2 通りの処理が考えられる．
18
図 3.2: ソート方法の改良
• ノード A を先に訪問した場合，得られる最近オブジェクトの距離は最短の場合
で M IN DIST (Q, A2) である．この距離は M IN DIST (Q, B1) より大きいた
め，ノード B を訪問したときには必ずノード B1 を訪問しなければならない．
• ノード B を先に訪問した場合，得られる最近オブジェクトの距離は最悪の場
合でも M IN M AXDIST (Q, B1) である．この距離は A 中のすべての子ノー
ドの MINDIST より小さいため，ノード A を訪問したときにはどのノードも
たどる必要がない．
よって，その他のノード探索数を無視すれば，ノード B を優先して訪問した方が，
ノード A を訪問した場合より最低でも 1 回探索ノード数を削減できる．
このような例から，MINDIST が等しかった場合の優先順位を定めることによっ
て，アクセスするノード数を削減できる可能性がある．最適なノードの探索順序を
予測するのは難しいが，以下にその一例を示し，5 章で性能を検証する．
• ノードの領域式が Q の領域式を包含していれば，そのノードを優先する．
• ノードの領域式に対応する矩形領域を R′ とするとき，M IN DIST (Q, R′ ) の
小さいノードを優先する．
19
図 3.3: ノードの探索順序によってアクセスノード数が変化する例
3.1.4
改良アルゴリズム
以上に述べた改良手法を取り入れた改良アルゴリズムを示す．
GBD 木における 1-NN 検索 (改良版)
searchNN(node : Node, q : Point, nearest : Nearest)
1: node が葉ノードの場合，node に置かれているすべてのオブジェクトエントリ obj
に対して，以下の処理を行う．
1-1: q と obj の MBR との MINDIST が nearest の距離以下であれば，以下の処理
を行う．
1-1-1: obj のポインタをもとにオブジェクトを読み込む．
1-1-2: q とオブジェクトとの距離が nearest の距離以下であれば，nearest をそのオ
ブジェクトで更新する．
2: node が非葉ノードの場合，以下の処理を行う．
2-1: node に置かれている子ノードのリストを先頭から走査し，q の領域式を包含
する領域式をもつ最初のノード child を探す．
20
2-2: searchNN(child, q, nearest) を実行する．
2-3: ActiveBranchList を初期化する．node 内のすべての子ノード child に対して以
下の処理を行う．
2-3-1: child がまだ辿られておらず，かつ q との MINDIST が nearest の距離以下で
あれば，child を ActiveBranchList に追加する．
2-4: ActiveBranchList を，MINDIST を第 1 キー，所定の値を第 2 キーとしてソー
トする．
2-5: ActiveBranchList の先頭から順に要素 child を取り出しつつ，以下の処理を繰
り返す．
2-5-1: child と q との MINDIST が nearest の距離以下であれば，searchNN(child, q,
nearest) を実行する．
2-5-2: 2-5-1 に該当しない場合は，繰り返し処理を終了する．
1-1 では，オブジェクトの MBR との MINDIST の値をチェックすることで，オブ
ジェクトとの実距離を検証する回数の削減を図っている．2-3-1 では，各子ノード
との MINDIST を検証することで，ActiveBranchList に入れる要素を限定している．
次に，このアルゴリズムを用いた最近接オブジェクト検索の処理の一例を示す．
図 3.4 における Q を検索点とする．説明を簡単にするため，オブジェクトと検索点
との実距離は MINDIST に等しいものとする．まず，ノードとの包含関係を調べる
ために Q の領域式を求めておく．領域式は「0011· · · ＊」となる．以下，Q とオブ
ジェクト o との実距離を DIST (Q, o) と表記する．
• 根ノードにおいて，Q の領域式を包含する領域式を持つノードを先頭から探
す．A の領域式「0 ＊」が該当するので，A を辿る．
– ノード A において，Q の領域式を包含するノードを先頭から探す．C の
領域式「00 ＊」が該当するので，C を辿る．
∗ ノード C において，最初のオブジェクト a との距離を求め，一時的
な最近接オブジェクトの候補とする．
∗ M IN DIST (Q, b) > DIST (Q, a)，M IN DIST (Q, c) > DIST (Q, a)
であるため，オブジェクト b，c にはアクセスしない．
– ノード A に戻り，MINDIST が DIST (Q, a) 以下となる他のノードを求
める．D のみが該当するため，D を辿る．
∗ ノード D において，最初のオブジェクト d との MINDIST を求め
る．M IN DIST (Q, d) > DIST (Q, a) であるため，d にはアクセス
しない．
21
図 3.4: GBD 木における 1-NN 検索
∗ 次のオブジェクト e の MINDIST は DIST (Q, a) 以下であるため，実
際の距離を求める．DIST (Q, e) < DIST (Q, a) であるため，候補を
e で更新する．
• 根ノードに戻り，MINDIST が DIST (Q, e) 以下となる他のノードを求める．
該当するノードは存在しないため処理を終了する．
結果として，Q に対する最近接オブジェクトは e であることが求められた．この
例では，非葉ノードへのアクセス数が 2，葉ノードへのアクセス数が 2，オブジェク
トへのアクセス数が 2 である．葉ノードにおいて MINDIST によるチェックを行わ
ない場合と比べて，この例ではオブジェクトアクセス数を 3 削減できた．
22
図 3.5: k-NN 検索 (k=3, ノード A 探索終了時の様子)
3.2
k-NN 検索への拡張
1-NN 検索を一般化し，k 個の近接オブジェクトを求められるように拡張したの
が，k-NN 検索である．k-NN を求めるには，1-NN アルゴリズムを以下のように変
更すればよい．
• k 個の近接オブジェクトを格納可能なバッファを用意する．そして，k 個の近
接オブジェクトを常に近い順にバッファに貯えておく．
• k 番目の近接オブジェクトとの距離を用いて，MINDIST による枝刈りを行う．
図 3.5 は，3-NN 検索において，ノード A の探索が終了した時点の様子を示した
ものである．この時点での近接オブジェクトのバッファの内容が [e, a, b] であるとす
ると，枝刈りの基準値は DIST (Q, b) となる．M IN DIST (Q, B) はこの距離より小
さいため，1-NN 検索の場合とは異なりノード B も辿らなければならない．b より
近接するオブジェクトがノード B 内に含まれる可能性があるためである．
ページサイズが小さい場合や，k が大きい場合には，一回の葉ノード訪問ではバッ
ファが k 個に満たない場合がある．このような場合には，k 個のオブジェクトが見
つかるまで枝刈りを行わずに無条件に次のノードを辿ればよい．
23
第4章
4.1
最良優先探索による k-NN
検索
概要
3 章までは，深さ優先に基づいた k-NN 検索アルゴリズムについて述べた．一方
で，深さ優先探索とは異なるアプローチによるアルゴリズムが提案されている．最
良優先 (best-first) 探索と呼ばれる方式がこれに該当する．最良優先探索アルゴリズ
ムは，最近接オブジェクトを含む可能性の高いノードを常に取り出せるような優先
順位付きキューを 1 つ用意し，その先頭要素を取り出してはその子ノードエントリ
を再びキューに挿入するという処理を繰り返しつつ，最近接オブジェクトを探す方
式である．
最良優先によるアルゴリズムは，深さ優先探索が持つ問題点を解決している．深
さ優先探索では，訪問したノードごとに独立した探索リストを作成し，探索順序を
決める．そのため，探索順序が常に MINDIST 順とは限らず，実際には辿る必要の
ないノードを辿る場合がある．一方の最良優先探索では，ノードごとに独立して探
索順序を決めるのではなく，常に木全体で最良となるような順序に従って木を探索
する．常に最良な順序で探索することが可能なので，深さ優先探索よりノードアク
セス回数を低く抑えることができ，入出力コストを低減できる可能性がある．
図 4.1 は，両探索方式の比較を示している．深さ優先探索の場合，もし A を先
に訪問すれば，A 内のすべてのノードは B 内のノードよりも優先して探索される．
そのため，G のほうが C より近くに位置しているにもかかわらず，C の探索順序
の方が上となる．最良優先の場合，常に MINDIST が最小のノードを展開し，単一
のキューに子ノードを挿入する (図右下参照)．そのため，ノードの探索順序は常に
MINDIST 順となる．
最良優先による k-NN 検索アルゴリズムに関する研究には [5] や [6]，[2] などがあ
る．以下に，[2] で提案されているアルゴリズムを記述する．
24
図 4.1: 深さ優先探索と最良優先探索の比較
1: PartitionList を，根ノード中のすべての子ノード要素で初期化する．
2: PartitionList を，MINDIST の昇順にソートする．
3: PartitionList が空でない間，以下の処理を繰り返す．
3-1: PartitionList の先頭要素が葉ノードの場合，以下の処理を行う．
3-1-1: 葉ノード中のオブジェクトで最も近接するオブジェクトを探し，これを NNC
とする．
3-1-2: NNC が NN より近接していれば，以下の処理を行う．
3-1-2-1: PartitionList を NNC の距離で枝刈りする．
3-1-2-2: NN を NNC で更新する．
3-2: PartitionList の先頭要素が非葉ノードの場合，以下の処理を行う．
3-2-1: PartitionList の先頭をそのノードのすべての子ノードで置き換える．
3-2-2: PartitionList を MINDIST の昇順にソートする．
4: NN を出力する．
25
4.2
問題点とその解決方法
4.1 節で述べたアルゴリズムでは，葉ノードにおける処理が深さ優先アルゴリズ
ムと同様である．すなわち，葉ノードに達した時点で葉ノード内の各オブジェクト
が最近接オブジェクトとなり得るかどうかを調べる．このアルゴリズムは点データ
を扱う場合を対象としているので，この手法でも問題がないように思われる．点と
点の距離は非常に簡単に求めることが可能なためである．しかし，3.1.1 でも述べ
たように，複雑な形状のオブジェクトを扱う場合で，そのデータが外部のファイル
に記録されている場合には，ノードの読み込み回数だけでなくオブジェクトの読み
込み回数も処理速度に影響を与える．そのため，オブジェクトへのアクセス回数を
極力低く抑えるための改善が必要である．オブジェクトアクセスを低減するには，
ノードだけでなく，オブジェクトも常に MINDIST の小さい順に検証する方法が適
切と思われる．
[5] では，座標データを扱う 4 分木において，近接オブジェクトを検索するアルゴ
リズムを提案している．このアルゴリズムでは，距離が最小の要素を取り出すこと
が可能な優先順位付きキューを用意し，各領域を検索点との MINDIST をキーとし
てキューに挿入する．そして，葉ノードが展開された場合にはそのノードに含まれ
る各オブジェクト (点) への距離を求め，キューに挿入する．キューの先頭要素がオ
ブジェクトであった場合は，そのオブジェクトを近接オブジェクトとして報告する．
このアルゴリズムの利点は，オブジェクトを常に 1 つずつ (近い順に) 報告する点に
ある．そのため，この手法は求める近接オブジェクトの個数 (k) に対して柔軟性が
あり，k 番目の近接オブジェクトが見つかれば，キューの内容を記憶させておくこ
とでただちに k+1 番目の近接オブジェクトを探すことができる．
本研究では，k の値はあらかじめ定まっているものとし，オブジェクトへのアクセス
回数を削減する目的でこのアルゴリズムを拡張する．オブジェクトを常に MINDIST
の昇順に検証するため，葉ノードが展開されたら，オブジェクトとの実距離を求め
るかわりに，各オブジェクトの MBR との MINDIST を求め，その値をキーとして
キューに挿入する．キューの先頭がオブジェクト (の MBR) であったら対応するオブ
ジェクトを読み込み，検索点との実距離を求め，近接オブジェクト用のリストに挿
入する．この手法では，求めたオブジェクトの実距離が常に近い順であるとは限ら
ないため，k 個のオブジェクトが求められても，k 番目のオブジェクトより近くに他
のオブジェクトが存在する可能性がある．そこで，キューの先頭要素の MINDIST
を常にチェックし，MINDIST が k 番目のオブジェクトの実距離より小さい間はノー
ド展開 (あるいはオブジェクト検証) を行うようにする．この処理が終了するのは，
キューの先頭要素の MINDIST が k 番目の近接オブジェクトの距離を上回った場合
26
である．
4.3
優先順位付きキュー
最良優先型のアルゴリズムでは，1 個の優先順位付きキューにノードおよびオブ
ジェクトを挿入するため，キューのサイズが大きくなる．そのため，深さ優先型の
アルゴリズムに比べて 1 回のノード処理にかかる CPU コストは大きくなることが
予想される．よって，優先順位付きキューの取り扱いについて少し考慮する必要が
ある．
優先順位付きキューを実現するためのデータ構造としてはヒープが有名である．
ヒープを用いれば，先頭要素の取得およびデータの挿入を O(log n)(n はヒープのサ
イズ) のコストで実行できる．キューのサイズを N ，1 ノードあたりの子ノード (ま
たはオブジェクト) 数を M とすると，多くの場合では N > M と考えられるため，
1 回のノード処理に要するコストは O(M log N ) となる．
一方，[2] のアルゴリズムでは，単純なリストに子ノードを挿入し，すべての要素を
MINDIST の昇順に再ソートするという方式を採っている．この手法では，O(N log N )
のコストがかかる．このアルゴリズムでは，リストを用いることによって，不要な
要素の枝刈りを可能としている．すなわち，最近接オブジェクトの候補が更新され
るたびに，その距離を基準として枝刈りが実行される．もし，ヒープを用いて枝刈
りを実行しようとすると，1 個の要素を削除するたびに O(log N ) のコストがかかっ
てしまうため非効率である．枝刈りを行うことで，優先順位付きキューのサイズを
低く維持できる可能性があるが，枝刈りを行うことができるのは近接オブジェクト
の候補がすでに k 個見つかっているときだけである．そのため，k が大きい場合に
は枝刈りが実行可能になるまでに時間がかかるので，枝刈りによる改善効果はあま
り期待できないと思われる．
これらの点を踏まえ，優先順位付きキューの実装としてヒープ構造を選ぶ．ヒー
プを用いることによって枝刈りは事実上不可能になるが，不要な要素をキューに挿
入しないようにすることで，キューのサイズを低く抑えられる可能性がある．すな
わち，k 個の解オブジェクトの候補がすでに見つかっている場合に，k 番目のオブ
ジェクトの距離より大きい MINDIST を持つノードあるいはオブジェクトについて
は検証する必要がないためキューに挿入しない．
27
4.4
アルゴリズム
以上の点を踏まえた改良アルゴリズムを以下に示す．このアルゴリズムはすでに
k-NN 検索に対応しており，結果として k 個の近接オブジェクトを含むリストを返
す．
最良優先探索による k-NN アルゴリズム (改良法)
NearestNeighborSearch(Q : Point, k : Integer) : List of Object
1: PriorityQueue を初期化し，根ノードを挿入する．
2: PriorityQueue が空でない間，以下の処理を繰り返す．
2-1: PriorityQueue の先頭要素 E を取り出す．
2-2: E の距離が NNList の k 番目要素の距離より大きい場合，繰り返し処理を終了
する．
2-3: E がオブジェクトをあらわす場合，以下の処理を行う．
2-3-1: E のポインタをもとに対応するオブジェクト O を読み込み，O と Q との実
距離を求める．
2-3-2: 求めた距離が NNList の k 番目要素の距離以下であれば，NNList に O を挿
入する．
2-4: 2-3 に該当せず，E が葉ノードの場合，以下の処理を行う．
2-4-1: E のポインタをもとに対応する葉ノード Node を読み込む．
2-4-2: Node 中のすべてのオブジェクトエントリ Entry に対して，以下の処理を行う．
2-4-2-1: Entry の MBR と Q との MINDIST を求める．
2-4-2-2: MINDIST が NNList の k 番目要素の距離以下であれば，MINDIST をキー
として PriorityQueue に挿入する．
2-5: 2-4 に該当しない場合，以下の処理を行う．
2-5-1: E のポインタをもとに対応する非葉ノード Node を読み込む．
2-5-2: Node 中のすべての子ノードエントリ Entry に対して，以下の処理を行う．
2-5-2-1: Entry の MBR と Q との MINDIST を求める．
2-5-2-2: MINDIST が NNList の k 番目要素の距離以下であれば，MINDIST をキー
として PriorityQueue に挿入する．
28
3: NNList を返す．
このアルゴリズムの処理の一例を次に示す．図 4.2 のような GBD 木において点
Q が指定されたとき，Q に最も近接するオブジェクトを 1 つ求める場合を考える．
1. まずはじめに根ノードを展開する．根ノードには G，H の 2 つの子ノードが
あり，これらをキューに挿入すると [H, G] となる．
2. キューの先頭要素 H を取り出し，ノード H を展開する．H には D，E ，F の
3 つの子ノードがあり，これらをキューに挿入すると，[F, G, D, E] となる．
3. キューの先頭要素 F を取り出し，ノードを展開する．F には 2 つのオブジェ
クト m，n がある．これらを MINDIST をキー値としてキューに挿入すると，
[m, G, D, n, E] となる．
4. キューの先頭要素 m を取り出す．m はオブジェクトなので，オブジェクト m(太
線で示されるポリライン) を読み込み，m と Q との実距離 DIST (Q, m) を求
める．m を最近接オブジェクトの候補とする．
5. キューの先頭要素 G を取り出し，ノードを展開する．G には 3 つの子ノード
A，B ，C があるが，このうち B は MINDIST が DIST (Q, m) より大きいた
め考慮に入れる必要がない．よって A と C がキューに挿入され，キューの内
容は [C, A, D, n, E] となる．
6. 先頭要素 C を取り出し，ノードを展開する．C には 3 つのオブジェクト e，f ，g
があるが，このうち e は MINDIST が DIST (Q, m) より大きいため考慮に入れ
なくてよい．よって f ，g がキューに挿入され，キューの内容は [f, A, g, D, n, E]
となる．
7. 先頭要素 f を取り出す．f はオブジェクトなので，対応するオブジェクトを読
み込む．f の実距離は DIST (Q, m) より小さいため，候補を f で更新する．
8. 先頭要素 A を取り出す．A の MINDIST は DIST (Q, f ) より大きいため，こ
れ以降のノードに最近接オブジェクトが含まれることはない．よって処理を
終了し，f を結果として返す．
この処理では，H, F, G, C の 4 つのノードと，m, f の 2 つのオブジェクトにアク
セスした．
29
図 4.2: 最良優先探索による NN 検索
30
第5章
5.1
実験
実験方法
本章では，GBD 木における k-NN 検索アルゴリズムを実装し，他構造 (R 木およ
び R* 木) との性能比較や，改良方式の性能評価を行う．実験には，さいたま市 (図
5.1) と那覇市 (図 5.2) の地図データを用いる．地図データのオブジェクト数および
ファイルサイズを表 5.1 に示す．
名称
地図 A
地図 B
表 5.1: 使用した地図データ
地域
総オブジェクト数 データサイズ
さいたま市
那覇市
27074
151698
図 5.1: さいたま市 地図
31
1.32MB
9.57MB
図 5.2: 那覇市 地図
各オブジェクトは数個∼数百程度の頂点から成るポリラインで表現される．実験
に用いる 2 種類の地図にはそれぞれ以下のような特徴がある．
• 地図 A: 道路，鉄道，河川，行政界 (市町村界) などから成る．道路や行政界は
細かく分断されており，1 つのオブジェクトの規模は比較的小さい．
• 地図 B: 道路，建物，河川，行政界 (街区界，字丁目界) などから成る．建物の
形状が詳細に記述されている．道路などは細かく分断されているが，各行政
界は 1 本の閉じたポリラインで表現されており，数百の頂点から成る大規模
なものが多い．
作成した空間インデックスは，R 木 (2 乗コストアルゴリズムによる)，R*木，お
よび GBD 木である．それぞれに対して，ページサイズを 20 から 100 まで変化させ
たものを作成した．地図 B をもとに作成したインデックスの葉ノード数，非葉ノー
ド数を図 5.3 に示す．また，葉ノードにおけるページ占有率を図 5.4 に示す．
図を見てわかるように，GBD 木の占有率は R 木を上回っているが，R*木には及
ばないものとなっている．そのため，合計ノード数は R*木が最も少なく，次いで
GBD 木，R 木の順に多くなる．
擬似乱数を用いて，地図の全範囲を包含する矩形領域内にランダムな検索点を
500 個発生させた．以降の実験では，500 個の検索点に対して k-NN 検索を行い，そ
の平均値を算出した結果を示す．なお，R 木および R*木の性能検証には 2.3.2 節で
述べた改良アルゴリズムを用いる．
32
図 5.3: 合計ノード数の比較 (左: 非葉ノード数，右: 葉ノード数)
図 5.4: ページ占有率の比較
5.2
5.2.1
実験結果および考察
深さ優先アルゴリズム
各データ構造間の比較
図 5.5 は，ページサイズを変化させたときのアクセスノード数の推移を示したも
のである．なお，使用データは地図 B である．
図を見てわかるように，GBD 木と R 木との間にははっきりとした性能差があり，
特にページサイズが小さい場合には GBD 木は R 木の 6 割程度のノードアクセスで
検索が可能である．ページサイズが増加するに従い両者の差は小さくなる傾向にあ
33
図 5.5: ページサイズごとのアクセスノード数の比較 (1-NN および 10-NN)
るが，これは合計ノード数や木の高さが減少し，各 MBR の面積が大きくなるため，
R 木においても適切なノード探索が可能になるためであると思われる．一方，R*
木と GBD 木との差はわずかであり，R*木の方が 0.7 から 1 程度アクセスノード数
が少ないという結果が出ている．両者のわずかな差の原因として考えられるのは，
R*木の方がページ占有率が高く，合計ノード数が少ないという点である．図 5.6 は，
1-NN 検索におけるアクセスノード数の全ノード数に対する割合を求めることで，各
構造のノードの絞込み効果の違いを示したものである．
図 5.6: アクセスノード数の全ノード数に対する割合
このように，R 木は他構造と比較してアクセスしたノード数の割合が大きく，R*
34
木は一部のページサイズを除いて GBD 木より割合が若干小さいことがわかる．こ
の結果より，木全体のノード数以外にも検索性能に影響を与える要素があることが
考えられる．検索性能に影響を与える他の要素としては，MBR 間の重なりが挙げ
られる．R*木では，MBR の重なりが少なくなるようなデータ挿入を行うが，これ
に対し，GBD 木では領域式に基づいたデータ挿入およびノード分割が実行され，
MBR は考慮されない．このような違いから，GBD 木は R*木に比べて若干 MBR の
重なりが多くなるものと思われる．検索点を内包する (MINDIST が 0 となる) ノー
ドはすべて辿らなければならないという性質上，MBR の重なりが検索性能に与え
る影響は大きいと思われる．
続いて，検索個数 (k) を増加させたときの 3 構造の検索性能を検証する．地図 A
におけるアクセスノード数およびアクセスオブジェクト数をそれぞれ図 5.7，図 5.8
に，地図 B における同様の結果を図 5.9，図 5.10 に示す．それぞれページサイズが
25 および 50 の場合について，k を 1 から 100 まで段階的に増加させたときの結果を
まとめている．なお，オブジェクトアクセス数は 3.1.1 節で述べた改良法 (MINDIST
によるソートを行わない) を用いて検証した．
図 5.7: k-NN 検索におけるアクセスノード数 (地図 A)
地図 B の結果に見られるように，k の増加に従い，R 木と GBD 木のアクセスノー
ド数の差は広がる傾向があり，ページサイズが 25 の場合には，100-NN 検索におい
て R 木の半分程度のノードアクセスで検索が可能である．1-NN のときと同様，R*
木と GBD 木の性能差はわずかであるが，ページサイズや地図データによって若干
異なる性質を示している．まず，地図 A では R*木の方が GBD 木より 3∼7%程度
性能がよく，ページサイズが大きいほど差は広がる傾向にある．アクセスオブジェ
クト数に関しては両者ともほぼ同じ数値を示している．一方，地図 B ではページサ
イズが小さい場合に GBD 木が R*木をわずかに上回るという結果が得られている．
アクセスオブジェクト数では両者に大きな差が見られ，最大で 30%程 GBD 木の方
が少ない．
35
図 5.8: k-NN 検索におけるアクセスオブジェクト数 (地図 A)
図 5.9: k-NN 検索におけるアクセスノード数 (地図 B)
先にも述べた MBR 同士の重なりが，このような結果の違いに影響を与えている
可能性が考えられる．直観的に，MBR の面積の合計が大きいほど MBR 間の重なり
も大きくなると考えられるため，各空間インデックスに対して，葉ノードの MBR
面積の合計値を算出した (図 5.11 参照)．
地図 B の結果を見てわかるように，R*木と GBD 木の面積合計値は R 木と比べ
て圧倒的に小さい．また，地図 A の算出結果を見ると，どのページサイズにおいて
も GBD 木より R*木の方が面積が小さいが，一方の地図 B では，ページサイズが
大きい場合には R*木の方が面積が小さいが，ページサイズが小さい場合には逆に
GBD 木の方が小さいという結果が得られている．また，地図 B ではページサイズ
が大きくなるほど面積の合計が小さくなる傾向が見られる．これを先ほどの k-NN
検索の結果と照らし合わせると，MBR 面積の合計が小さい方が，(特に k が大きい
場合に) 検索性能が良いという関連性が見受けられる．
地図データによってこのような葉ノード面積の違いが現れるのは，両データの特
36
図 5.10: k-NN 検索におけるアクセスオブジェクト数 (地図 B)
図 5.11: 葉ノードの MBR 面積の合計値の比較
徴に因るところが大きいと思われる．地図 A は，オブジェクトの (MBR の) 面積が
比較的均一である．R*木は MBR の重なりが少なくなるような分割を目指すため，
このようなデータにおいては性質のよい分割を行うことができる．一方の地図 B は，
オブジェクトの面積の分布にばらつきがあり，小さいデータや大きいデータが混在
している．面積の大きいデータが木に投入されると，投入先の葉ノードの MBR はそ
れに従い拡大される．R*木では各ノードの MBR を参照してデータの投入先を決定
するため，その後のデータ分配に与える影響が大きく，ノード分割が頻発し，ノー
ドの MBR に無駄なスペースが発生する可能性がある．特にページサイズが小さい
場合には，各葉ノードの面積が小さいため影響が大きく，葉ノードの面積合計が大
きくなるものと思われる．GBD 木の場合，データは中心点の領域式によって投入
先が決定されるため，MBR の変化による影響は少なく，データは性質よく分配さ
れる．
37
検索点の位置による性能の違い
本実験で用いた地図 B は，地図の外部に空白部分が多いという特徴がある．この
空白部分に置かれた点から k-NN 検索を行った場合，検索点から最近接オブジェク
ト間での距離は必然的に遠くなる．このような検索は，地図内部の点における検索
とはやや異なる性質を持っていると思われる．そこで，500 回試行のうち，検索点
から最近接オブジェクトまでの距離が遠いもの 3 割と，近いもの 3 割についてそれ
ぞれ平均アクセスノード数を算出し，比較を行った．R*木と GBD 木に対してこの
比較を行った結果を図 5.12 に示す．
図 5.12: 距離の遠近によるアクセスノード数の比較
結果を見ると，GBD 木の場合には近接点からの検索の方が遠隔点からの検索よ
りアクセスノード数が少ないが，R*木ではその逆の結果が得られている．また，近
接点からの検索にのみ注目した場合，R*木より GBD 木の方がアクセスノード数が
少なく，ページサイズが小さいほどその差が大きいことが分かる．このように両者
の結果に違いが現れる理由として，以下のような性質の違いが考えられる．
• GBD 木では，最初に辿るノードを決定するときに領域式を用いるため，複数
ノード間に重なりがある場合でも辿るべきノードを一意に決定でき，適切な
ノードを選択することができる．そのため，地図データの密度が高い点から
の検索に強いものと思われる．一方，地図外部から検索を行った場合，デー
タの分布によっては最初に辿るノードより近くに他のノードが存在する場合
も考えられ，検索性能が落ちる可能性がある．
• R*木の場合，MINDIST が小さいノードを優先して辿るが，MBR 間の重なり
が多い場合には，MINDIST が 0 となるノードが複数あるため，あいまいさが
生じる．そのため，地図内部からの検索に弱点を持っている．一方，地図外
部からの検索ではこのようなあいまいさが生じる可能性は比較的低いと思わ
れ，適切なノード選択ができる．
38
オブジェクトアクセス数の改善効果
続いて，3.1.1 節で述べた葉ノード処理の改良法によって，オブジェクトアクセス
数がどの程度改善するかを GBD 木を用いて検証する．図 5.13 は，ページサイズが
25 と 100 の場合において，各方式のオブジェクトアクセス数の比較を示したもので
ある．
図 5.13: オブジェクトアクセス数の比較
項目「全オブジェクト」は訪問した葉ノードに含まれるオブジェクトの総数を，
「MINDIST 枝刈り」は MINDIST が候補オブジェクトの距離より大きい場合にそ
のオブジェクトにアクセスしない方式を，
「MINDIST ソート＋枝刈り」は事前に葉
ノードの内容を MINDIST の昇順にソートする方式を表す．このように，MINDIST
によるチェックを入れることによって，実際にアクセスされるオブジェクト数は大
幅に減少した．特に 1-NN 検索においては数分の一に減少しており，MINDIST に
よるチェックが重要であることがわかる．一方，事前に MINDIST の昇順にソート
しておく手法は，ページサイズが大きい場合にある程度の改善効果が見られるが，
ページサイズが小さい場合にはあまり有効とはいえず，ソートしない場合と比べた
ときの減少量はわずかであった．これは，ページサイズが小さい場合にはソートの
範囲が 20 個前後とごく少数であり，より多くの葉ノードを検証しなければならな
いため，オブジェクトを真に MINDIST 順に調べるのが困難であることが理由に挙
げられる．
ソート方法の改良による効果
3.1.2 節で述べた，ソート前に枝刈りを行う手法によって，どの程度の改善効果が
得られるかを検証するため，訪問した各非葉ノードにおいてソートした要素数を求
め，その平均値を算出した．GBD 木と R*木における算出結果を図 5.14 に示す．
39
図 5.14: ソート前の枝刈りによる改善効果
この結果に見られるように，GBD 木の場合はソート前に枝刈りを行うことによっ
て大幅にソートに要する個数が減少した．なお，GBD 木と R*木で改善後の個数に
大きな差があるのは，GBD 木では最初に領域式を用いて木を辿る際にはソートを行
わず，子ノード訪問から戻った時点でソートを行うためである．すなわち，初めて
ソートする時点で近接オブジェクトの候補が k 個見つかっている場合が多く，ソー
ト前の枝刈りが可能であることが要因となっている．また，ページサイズが 100 の
場合に，k=50 の付近からソート個数が増加する傾向が見られるが，これは 1 回の
葉ノード訪問では k 個のオブジェクトが見つからず，最初の (あるいはそれ以降の)
ソートで多くの要素をソートする必要があるためである．
ノードの探索順序
MINDIST が等しかった場合の探索順序を定めることで検索性能がどのように変
化するかを検証する．本実験では，以下に示す 3 通りの手法について，アクセスノー
ド数とアクセスオブジェクト数を求めた．その結果を表 5.2 に示す．
探索順序 A MINDIST が等しいノードの探索順序は特に定めない．この場合，領域
式が小さい方が自然に優先されて辿られる．
探索順序 B ノードの領域式が検索点の領域式を包含していれば，そのノードを優
先する．
探索順序 C ノードの領域式に対応する長方形領域を求め，これを R′ とする．この
とき，M IN DIST (Q, R′ ) が小さい方を優先して辿る．
結果に見られるように，探索順序 B と探索順序 C ではほぼ同じ結果が得られて
おり，探索順序 A を用いた場合と比べて微小ながら改善効果が得られた．このこと
40
表 5.2: ノードの探索順序による比較 (ページサイズ:25, 上段:アクセスノード数，下
段:アクセスオブジェクト数)
k
1
10
20
40
60
80
100
探索順序 A
探索順序 B
探索順序 C
11.880
11.796
11.790
16.184
15.860
15.864
18.416
17.992
17.986
22.252
21.672
21.668
25.564
24.890
24.872
28.860
28.120
28.112
31.780
30.968
30.958
探索順序 A
探索順序 B
探索順序 C
9.490
9.160
9.096
38.004
34.692
34.552
62.554
57.968
57.474
102.794
96.396
95.810
141.110
133.102
133.114
178.148
168.484
168.326
213.914
203.234
202.968
から，領域式の範囲との厳密な距離を用いることでより適切なノードを辿ることが
できるが，単純な包含判定のみを用いた場合にもこれと同様の効果が得られること
が分かる．
5.2.2
最良優先アルゴリズム
最良優先探索によるアルゴリズムを用いたときのアクセスノード数を，地図 A，
地図 B の両データについて調べた．その結果を図 5.15，図 5.16 に示す．
図 5.15: アクセスノード数の比較 (地図 A)
深さ優先型アルゴリズムの場合と同様，GBD 木は R 木より少ないノードアクセ
スで検索が可能であることがわかる．GBD 木と R*木のアクセスノード数はほぼ同
等であるが，いずれの地図においても R*木の方が若干少ない．また，図 5.9 に示
した深さ優先型のアルゴリズムの結果と比較すると，1-NN 検索ではほとんど差は
41
図 5.16: アクセスノード数の比較 (地図 B)
見られないが，k の増加に従い差が広がる傾向が見られる．例えば，ページサイズ
が 25 の GBD 木の場合，k=100 において最良優先型の方が 15%ほど性能が良い．R
木においてはさらに差が大きく，約 35%性能が良い．このことから，最良優先探索
における，常に MINDIST の小さい順にノードを検証するという手法の有用性がわ
かる．R 木において 2 種類の方式の性能差が大きいのは，細長い MBR が多数存在
しているためであると思われる．MBR が細長いと，検索点から各子ノード (また
はオブジェクト) までの距離にばらつきが生じるため，深さ優先探索において常に
MINDIST 順にノードを探索することがいっそう困難になる．GBD 木や R*木では
MBR が比較的正方形に近いことから，両方式の差は小さいものと思われる．
続いて，4 章で述べたオブジェクトアクセスの改良法を用いた場合にどの程度の
改善効果が得られるかを検証する．図 5.17 は，最良優先型アルゴリズムにおいて深
さ優先型と同様の葉ノード処理を行った場合と，改良手法を用いた場合のアクセス
オブジェクト数の比較を示している．
図 5.17: 改良手法におけるアクセスオブジェクト数 (左:地図 A，右:地図 B)
42
この結果に見られるように，オブジェクトを MINDIST の昇順に調べることによっ
てアクセスオブジェクト数が減少した．特に，地図 B における改善効果が大きく，
ページサイズが 50 の場合には半分程度に減少している．また，どちらの地図にお
いても，検索個数 (k) よりわずかに多い程度のオブジェクトを調べるだけで検索が
可能であることがわかる．この数値は，データ構造やページサイズに依らず，デー
タの性質と検索個数に依存する．
図 5.18 は，この手法を用いた場合に，キューのサイズがどの程度まで上昇するかを
示したものである．キューにノードまたはオブジェクトを追加する際に，MINDIST
をチェックして不要なものを除外した場合 (改良後) と，そうでない場合 (改良前) の
比較を示している．
図 5.18: 優先順位付きキューの最大サイズ (地図 B，GBD 木，ページサイズ 50 の
場合)
ここではページサイズが 50 の場合のみ示しているが，ページサイズが大きくな
るほどキューの最大サイズは大きくなる傾向が見られた．キューのサイズは，ペー
ジサイズを m，探索したノード数を n，非葉ノードを含めた全ノードのページ占有
率を p とすれば，mnp と見積もることができる．GBD 木の場合，p はページサイズ
によらずおよそ 0.6 程度であり，実験結果とほぼ一致している．ページサイズが大
きいほどキューのサイズが大きくなるのは，ページサイズが大きいほど絞込み効果
が小さく，mn が増大するためである．
キューのサイズは数百程度に増加するが，これは木全体のノード数およびオブ
ジェクト数から見ればごく小さな数値であり，この手法が十分実用的であることが
分かる．
43
第6章
おわりに
本論文では，GBD 木のための k-NN 検索アルゴリズムとして，深さ優先探索と
最良優先探索の 2 通りのアプローチに基づいた手法を述べた．
深さ優先探索では，GBD 木の特徴である領域式を活用することによって，R 木よ
り効率の良い検索が可能である．また，R*木に近い性能を有しており，条件によっ
ては若干 R*木を上回る結果も得られた．
最良優先探索では，ノードとオブジェクトの両方を常に MINDIST の昇順に検証
することによって，ディスクアクセス回数を削減できることを示した．特にオブジェ
クトアクセスに関しては，データ構造やページサイズの影響を受けずに一定のコス
トで検証できるという利点がある．
両方式を比較した場合，1-NN 検索では大きな差はみられず，最良優先方式では
優先順位付きキューを要するという性質から，時間計測の結果ではわずかに深さ優
先方式が勝るという結果も得られている．一方，複数個のオブジェクトを検索する
場合には，ディスクアクセスを低く抑えることが可能な最良優先方式が有用である．
44
謝辞
研究ならびに生活面においてご指導を賜りました大沢 裕教授に深く感謝致し
ます．
また，先輩としていつもよきアドバイスをくださいました，根岸 幸生氏，Indit
Widhijaningrum 氏，大森 洋平氏，村上 義載氏，王 玉娜氏，大木 彩加氏，栗
原 孝暢氏，高沢 聡氏，そして同期生として苦労を共にした伊藤 雅亮氏，猪又
正樹氏，並木 琢氏，並びに私を暖かく見守って頂いた両親はじめとする周囲の
すべての皆様に深く感謝致します．
45
参考文献
[1] N. Beckmann, H. P. Kriegel, R. Shneider and B. Seeger: “The R*-tree: an
efficient and robust method for points and rectangles”, In Proceedings ACM
SIGMOD Conference on Management of Data, pp. 322-331, (1990).
[2] Stefan Berchtold, Christian Bohm , Daniel A. Keim, and Hand-Peter Kriegel:
“A Cost Model For Nearest Neighbor Search in High-Dimentional Data Space”,
In Proceedings of PODS’97, pp. 78-86, (1997).
[3] King Lum Cheung and Ada Wai-chee Fu: “Enhanced Nearest Neighbor Search
on the R-tree”, SIGMOD Record Vol. 27 No. 3, pp. 16-21, (1998).
[4] A. Guttman: “R-trees: a dynamic index structure for spatial searching”, In
Proceedings ACM SIGMOD Conference on Management of Data, pp. 47-57,
(1984).
[5] Gisli R. Hjaltason and Hanan Samet: “Ranking in Spatial Databases”, Proceeding of the 4th Symposium onn Spatial Databases, pp. 83-95, (1995).
[6] Gilsi R. Hjaltason and Hanan Samet: “Distance Browsing in Spatial
Databeses”, ACM Transactions on Database Systems, pp. 265-318, (1999)
[7] Apostolos Papadopoulos and Yannis Manolopoulos: “Performance of Nearest
Neighbor Queries in R-trees”, Proc. of the 6th International Conference on
Database Theory, Delphi, Greece, pp. 394-408, (1997).
[8] Nick Roussopoulos, Stephen Kelley, and Frederic Vincent: “Nearest Neighbor
Queries”, In Proceedings ACM SIGMOD Conference on Management of Data,
pp. 71-79, (1995).
[9] 大沢裕, 坂内正夫: “2 種類の補助情報により検索と管理性能の向上を図った多
次元データ構造の提案”, 電子情報通信学会論文誌 D-I, Vol. J74-D-I, No.8, pp.
467-475, (1991).
46