DEIM Forum 2013 A9-5

空間データにおける 2n 分割木を用いた m-最近傍キーワード検索邱原†大森匡†

新谷 隆彦†† 電気通信大学大学院情報システム研究科 〒 182–8585 東京都調布市調布ケ丘１ー５ー 1
E-mail: †{kyuu ＿ genn,omori}@hol.is.uec.ac.jp, ††shintani@is.uec.ac.jp
あらまし

本稿は空間データにおける mCK(m-Closest Keywords:m-最近傍キーワード) 検索問題 [4] を扱う. 先行研

究である Zhang らの bR*-tree データ構造を用いた方式 [4] はノードの組合せと枝刈りを交互に行って, 探索空間を減らすが, いくつか制約がある. すなわち,(1) 頻繁に更新するデータに対して能力はよくない.(2) データセットのオーバラップには耐えられない. (3) 検索対象になるキーワードの集合が事前に決まっている必要がある. この問題に対して,
本稿は空間を 2n × 2n の領域に分割する木構造 (2n 分割木) を用いた探索アルゴリズムを述べ, 上記 (1)〜(3) を解決し,かつ, 枝刈り戦略を工夫して, 効率の向上を目指す.
キーワード

空間データ検索 m-最近傍検索

2n split tree for m-Closest Keyword search on spatial dataYuan QIU† , Tadashi OHMORI† , and Takahiko SHINTANI†† The University of Electro-Communications,Graduate School of Information Systems
E-mail: †{kyuu ＿ genn,omori}@hol.is.uec.ac.jp, ††shintani@is.uec.ac.jp
Abstract This work addresses the problem of m-Closest Keywords search(mCK search). A previous study byZhang et al[4] uses bR*-tree for this problem. This scheme eﬃcently reduces the search space but has some restrictions: (1)It is not good for frequently updated data. (2)It is not applicable for the overlap operation of data sets.
(3)It must know the keyword set before the bR*-tree’s construction. Thus we use the 2n split tree and propose acorresponding algorithm to overcome these restrictions and apply some pruning strategies to improve the eﬃciency.
Key words Spatial data search m-Closest Keywords search

1. は じ め に
1. 1 研究の背景と目的

新たなサービスが提供されている (microsoft asia の GeoLife[5]や GeoTag,Twitter[6])．このようなサービスへの適用も可能にしたい．

近年,Web 上での検索には空間的制約を含む検索の割合が高

本稿では，mCK 検索をデータの頻繁な更新やデータセット

く [1]，空間検索はサーチエンジンにおいても重要になっていのオーバラップには耐えられるように改良する．すなわち，グる．空間データへの新しい検索能力も重要である．例えば, 空

リッドデータ構造に基づいて空間を 2n × 2n の領域に分割する

間属性とテキスト属性を両方含むデータ集合に対した空間キー

木構造 (2n 分割木) を用いてデータを整理して，各キーワードワード検索が注目されている [2][3]．ユーザはいくつかのキーに関連するノードの入れ子ループで m 次元ノードセットを組ワードを入力して，空間とテキスト両方を関連する情報を探索み合わせるというストラテジーを考える．そして，二つの枝刈する方式である．Zhang らが提出した mCK 検索 [4] はこの方りルールを利用して探索空間を減少するアルゴリズムを提案す式の一種であり,m 個のキーワードを指定して, この m 個のキーる．また，キーワード近似 MBR を利用してアルゴリズムの最ワードに関連する一番近いオブジェクトセットを探すという問適化を試し，効率を向上する．

合せである. この検索の応用例として, 花火大会で「花火の場1. 2 問題の定義所」,「食事処」,「ショッピングセンター」の三つのキーワード

空間データ集合における mCK 検索とは m 個のキーワードを考えれば, 花火も見えるし, 食事もショッピングもできる最もに関連する「一番近い」にあるオブジェクトセットを探すこと小さいエリアを検索できる.

である．オブジェクトセットの「近さ」は定義 1 の直径によっ

一方で,GPS が普及するに伴って，様々な位置情報の付いているデータ (テキストや写真など) がデータセンターに集まって，て判断される [4]．

定義 1(直径)：m 個のオブジェクト t1 , t2 , ..., tm により構成頻繁に更新される場合，ノードのスプリットが多く，更新能力されたオブジェクトセット T に対して，セットの直径は式 (1)はよくない．また，クエリのキーワード数が多い場合 bR*-treeによって示す方式の枝刈り能力は高いが，サーチエンジンの観点からいくつdiam(T ) = max dist(ti , tj )ti ,tj ∈T(1)

式の dist(ti , tj ) はオブジェクト ti と tj の間の距離 (ここではのユークリッド距離にすることになっている) である．

かの制限がある．まず，bR*-tree 方式は複数のデータセットのオーバラップを使った mCK 検索には耐えられない．例えば，ホテルデータセットと観光所データセットは別の bR*-tree で格納する場合，同時にこの二つのデータセットに mCK 検索を行うと，うまくできない．次に，検索の対象になるキーワードのつまり，オブジェクトセットの直径は，セットの中にある任集合が事前に決まっている必要がある．そのため，本稿は空間意の二つのオブジェクトの間の距離の最大値である．この直径を 2n × 2n の領域に分割する木構造 (2n 分割木) を用いてデーが小さければ小さいほど全オブジェクトが近いと言える．

タの更新とオーバラップ問題に対処することを考え，枝刈りを定義 1 によると，mCK 検索は実際に m 個のキーワードに対して，それぞれのキーワードに関連する一つのオブジェクトを取って m 次元のセットを組み合わせる．そして，これらオブジェクトセットの内，直径が一番小さいものを選ぶ問題になる．
定義 2(mCK 検索)[4]：d 次元空間のオブジェクト集合を与えて，各オブジェクトは t(l1 , l2 , ..., ld , w)(l1 , l2 , ..., ld ：各次元の座標,w：関連するキーワード) の形式とする．mCK 検索は

m 個のキーワード {w1 , w2 , ..., wm } のクエリ Q に応じて，m次元のオブジェクトセット T = {t1 , t2 , ..., tm }(ti.w ∈ Q, またti.w =| tj.w ) に, 直径は最小なものを探すことである．

工夫して探索効率を上げる．

3. 2n 分 割 木
2n 分割木は四分木のように空間を再帰的に 2n × 2n の領域(セル) に分割するのに使われる．もし n は 2 の場合，16(=4×4)
分割木になる．図 2(b) は同図 (a) のデータ分布に対応する 16分割木である．各セルの情報は木のノードに格納される．各ノードに対して，ノード ID という番号を与える．ノード ID
はヒルベルトや z-order など空間充填曲線による番号がつけてもよいが，ここでは簡単に単純な左→右と上→下の順番で番号をつける．また，ノードの中にデータがあるのにかかわらず，例えば，図 1 は地図にキーワード {A，B, C} に関連するオブ

ノード番号はフル 16 分割木に対応している．そのため，再帰ジェクトの分布を表す．{A, B, C} をクエリとして mCK 検索

的にノード ID と 16 の割り算で得た商と余りを用いてセルのを行うと，丸印で囲んだ三つのオブジェクトによるセットが結位置が確定される．

果となり，目的のエリアも決めることができる．

ノード ID に加えて，すべての中間ノードにキーワードごとキーワード分布ビットマップという情報もつけられている．
キーワード分布ビットマップとは 2n × 2n をサイズとして，それぞれのビットは一つの子ノードを代表する．

•値が「1」の場合 該当キーワードが対応した子ノードに含まれる．

•値が「0」の場合 該当キーワードが対応した子ノードに含まれない．
図 2(b) によると，ノード ID が「0」(根ノード) のノード
図 1 mCK 検索の例にキーワード A のキーワード分布ビットマップは (1100 00000000 0000) であるので，根ノードの 1 番，2 番二つの子ノード，2. 先行研究との違い

つまりノード ID が「1」，「2」のノードがキーワード A を含んでいて，他の子ノードが A を含まないと表示する．このキー

mCK 検索について，先行研究とした D.Papadias らの Mul-

ワード分布ビットマップを利用して，任意のキーワード k に対

tiWay Spatial Joins(MWSJ) 方式 [7] と Zhang らの bR*-tree

して，根ノードから葉ノードまで k を含む子ノードへ辿ってかデータ構造を用いた方式 [4] がある．R*-tree に基づいたイ

ら，全ての k に関連するノードを探すことができる．

ンデックスを使ってデータをフィルタリングすることである．

そこで，2n 分割木のノードの形式は以下で表示する.

MWSJ はキーワード毎に R*-tree を構築してから入れ子ルー
プにより NN 探索を行なう方式である．bR*-tree は R*-tree のノードに各キーワードの含む情報と最小包囲矩形 (MBR) を記

葉ノード
中間ノード

:(ノード ID, データページへのポインタ):(ノード ID, 子ノードへのポインタ, キーワード分

布ビットマップ)

録して，検索の場合キーワードにかかわらず，根ノードから木をトラバースしながら，Apriori のストラテジーでノードセッ

4. 検索アルゴリズム

トの展開と枝刈りを交互に行って，探索空間を減らす．
しかし，MWSJ と bR*-tree 方式も R*-tree に基づいたデータを構築するので，位置情報のついたツイタのようにデータが4. 1 準備

mCK 検索の主要な動作はそれぞれのキーワードに関連する

(a) データの地理分布

図3

探索空間木

δ ∗ の初期値は対象となる全体空間の対角線の距離であり，つまり可能な直径の最大値である．δ ∗ は探索するとともに，減少する．
定義 4(二つのノードの M IN DIST と M AXDIST ):図 4 によると，二つのノード ni と nj を与えて，M IN DIST (ni , nj )は ni と nj に 代 表 さ れ た 矩 形 区 域 の 最 小 の 距 離 で あ り，

M AXDIST (ni , nj ) は ni と nj に代表された矩形区域の最大の距離である．

(b) 16 分割木のデータ構造

図 2 mCK 検索の例
図 4 M IN DIST と M AXDIST
データを組み合わせることである．そのため，2n 分割木を使う mCK 検索はデータの組み合わせ数を減少する必要がある．

隣接する二つのノードの M IN DIST は 0 となっている．

本稿は 2n 分割木をトラバースしながら，それぞれのキーワードに関連するノードを先に組み合わせて，ノードの間の距離で定義 5(ノードセットの M AXM IN DIST ):不要なデータの組み合わせを排除することを方針としてアルM AXM IN DIST (N ) はノードセット N の中に任意の 2 つゴリズムを提案する．具体的には m 個のキーワードのクエリの ノ ー ド の M IN DIST の 最 大 値 で あ る ．m 個 の ノ ー ド

Q = {w1 , w2 , ..., wm } に対して根ノードから，木の階層性質を{n1 , n2 , ..., nm } に構成された m 次元のノードセット N に利用して，各階層でそれぞれのキーワード wi (i = 1, 2, ..., m)

対して，M AXM IN DIST (N ) は式 2 に示す．に関連するノード nij (j = 1, 2, ...) を組み合わせ，m 次元のノードセット {n1a , n2b , ..., nmc }(a, b, .., c ∈ j) を作る．そして，

M AXM IN DIST (N ) =max

ni ,nj ∈N,i=j|(M IN DIST (ni , nj ))(2)

ノードセットを探索空間候補項にする．そこで，探索空間は「木の幅」と「木の深さ」二つの方向で生成する．
「木の幅」のM AXM IN DIST (N ) はノードセット N に対応しているほうは同じ階層で m 個のキーワードを入れ子ループでノードデータセットの直径の下限である．例えば，図 5 によって，キーを組み合わせることであるが，「木の深さ」のほうは木の階層をワード A, B, C に関連するノードセット N = {nA , nB , nC } に伸びることである．例えば，図 3 は図 2(b) の 16 分割木によっ

対して，M AXM IN DIST (N ) = M IN DIST (nA , nB )，つまて生成した探索空間木である．
「木の広さ」と「木の深さ」で探り dist(dA , dB ) >= M AXM IN DIST (N )(dA は任意の A に関索空間の生成は図の横軸と縦軸の方向に表す．
探索空間木からみると，16 分割木を用いて mCK 検索は状態空間探索の問題になる．本稿は探索空間木に深さ優先探索しながら，枝刈りを行うアルゴリズムを設ける．
枝刈りの判断基準を説明するためにいくつかの定義を与える．
∗∗

定義 3(閾値 δ ):δ は今まで計算した結果の中に一番小さい直径である．

連するデータ，dB は任意の B に関連するデータ) は必ず成立するので，ノードセット N {nA , nB , nC } により生成される答えの直径は M AXM IN DIST (N ) 以上である．

4. 2 枝刈りのルール
枝刈りの基準として，本稿は二つのルールを利用する．主に閾値 δ ∗ とノードの距離を比較して判断する．探索空間木の要素としたノードセットを判断して，もしルールを満足する場合，該当要素または要素を根ノードとしたサブ探索子空間を探索空

スしつつ，m 個のキーワードを入れ子ループでノードを組み合わせることであるので，アルゴリズムの設定について，再帰な方法で木のトラバースを行うが，非再帰のループでノードの組み合わせを実現する．具体的なアルゴリズムを Algorithm 1 に示す．このアルゴリズムでは，
図 5 M AXM IN DIST

1-5 行目:もしノードセットの要素は全部葉ノードの場合，各ノードに対応したキーワード関連するデータを取って，網羅的間木から枝刈りすることができる．以下の二つの枝刈りルールを説明する．にデータセットを組み合わせて最小の直径を求める．もし結果の直径は δ ∗ より小さい場合，δ ∗ を新しい直径に更新する．

10-12 行目:16 分割木の各ノードのキーワード分布ビットマップ[ルール 1]:クエリ Q = {w1 , w2 , ..., wm } に対応したノードを利用して，それぞれのキーワード wi に応じて，子ノードにセット N = {nw1 , nw2 , ..., nwm }(nwi : キーワード wi に関連キーワードを含むことによりリスト Li (i = 1, 2, .., m) を作る．

するノード, i = 1, 2, .., m) について，もし M IN DIST (nwi∗14-47 行目:while ループでリスト L1 〜Lm に対して深さ優先で，nwj ) > δ (nwi ，nwj ∈ N ) が成立すれば，ノードセット N要素の組み合わせを作り，バックトラッキングで枝刈りを行なが排除される．つまり，ノードセットに，ある二つのノードのう．一つのノードセットができれば，木の下へたどる．つまり∗間の M IN DIST が δ より大きければ，該当ノードセットが子ノードのセットを入力として再帰的に mCKSearch を呼び排除される．

出す (40 行目)．
具体的な例を挙げる．図 7 のように示す．

証明:nwi と nwj はキーワード wi と wj に関連するので，もし M IN DIST (nwi ，nwj ) > δ ∗ であれば，すべてのキーワー
ド wi に関連するデータ dwi とキーワード wj に関連するデー
タ dwj に対して，dist(dwi ，dwj ) > δ ∗ ．結果としたデータセッ

LA = {n1 , n2 }LB = {n1 , n6 }LC = {n2 , n6 }ト {..., dwi , .., dwj , ...} の直径 > δ ∗ は必ず成立するので，ノードセット N が排除される．

[ルール 2]:クエリ Q = {w1 , w2 , ..., wm } に対応したノード
セット N = {nw1 , nw2 , ..., nwm }(nwi : キーワード wi に関連するノード, i = 1, 2, .., m) について，もしノード nwi に対して，M AXDIST (nwi , nwt )< M AXM IN DIST (N )(t =1, 2, ..., m 且つ t =| i) が全部成立すれば，ノード nwi をノードセット N から一時的に削除する．
図 7 ノードの組み合わせ
例えば，図 6 により，キーワード A, B, C に関連するノード
セット N = {nA , nB , nC } に対して，1, 2, 6 はノード ID である．もし，LA の n1 と LB の n1 はルー

M AXM IN DIST (N ) = M IN DIST (nA , nB )ル 1 を満たすなら，LA の n1 へ戻り LB の n6 を試して、成功

M AXDIST (nC , nA ) < M AXM IN DIST (N )する．そして，LC の n2 へたどって、LC の n2 と LA の n1 ，M AXDIST (nC , nB ) < M AXM IN DIST (N )LC の n2 と LB の n6 両方を判断して，ルール 1 を満足するの直径は A と B に関連するデータの間の距離で決まると確定しで，LB の n6 へ戻り LC の n6 を試して、成功する．そして，て，C に関連するデータとは関係ないので，子ノードの組み合ノードセットを作って，入力として再帰的に mCKSearch をわせまたはデータの組み合わせにおいて，C に関連するノード呼び出す．

またはデータを以降の δ ∗ の計算対象から外す．

18-25 行目:ルール 1 が判定される．
28-39 行目:ルール 2 が判定される．
4. 4 アルゴリズムの最適化ルール 1 はキーワードに関連するノードの間の M IN DISTを計算して枝刈りを行うが，隣接するノードの間の M IN DISTは 0 であるので，枝刈りの能力が低い．枝刈りの能力を高めるため，近似キーワード MBR という概念を提出する．

図6

ル ー ル 2
定義 6(キーワード近似 MBR):ノード n において，n の子ノー4. 3 アルゴリズム
n2 分割木を用いた mCK 検索は木を深さ優先探索でトラバー

ドのうち，キーワード wi を含むノード集合から成る MBR を，wi の近似 MBR と呼ぶ．(n の wi についての wi の近似 MBR

は n が持つ wi のキーワード分布ビットマップから求める)
例えば，図 8 は図 2(a) のノード 1 と 2 におけるキーワード

A と C の近似 MBR を示す．左のノード 1 はキーワード A のAlgorithm 1 mCKSearch(keywordSet, nodeSet, T ree)Input: keywordSet : 現在に行うキーワードの集合
nodeSet : 現在に行うノードの集合

分布ビットマップを使って，キーワード A はノード 1 の 7,13番目の子ノードに含まれるので，A に対してノード 1 の近似

T ree :16 分割木
Output: δ ∗ : 今まで計算した直径の最小値．

MBR は赤い太い線で囲んだ矩形により表示される．同様に，右のノード 2 のキーワード C の近似 MBR は青い線で囲んだ矩形により表示される．ノード間の MINDIST の計算ではな
く，代わりに近似 MBR 間の MINDIST を利用して，ルール 1

1: if nodeSet のすべてのノードは葉ノード then2:d ← ExhaustiveSearch(nodeSet)3:

if d < δ ∗ thenδ∗ ← d4:を判断する最適化方法を提案する．そうすると，隣接ノードで5:あっても，最小距離は 0 ではない可能性があるので，枝刈りす

6: else

れば，探索空間を減少することができる．

7:

num ← keywordSet の中にキーワードの数

8:

newN odeSet ← ∅9:maxM inDist ← 0

10:

for node i in nodeSet do11:

図85. 実キーワード近似 MBR験Java 言語で図 2 に従った 16 分割木のデータ構造と mCK 検索のアルゴリズムを実装した．実験用マシンは Intel(R) Xeon(R)end ifLi ← traverse(i)12:end for

13:

k←1

14:

while k >= 1 do15:// 順番で Lk を要素をアクセス

16:

if Lk に次の要素がある then17:n ← Lk の次の要素

18:

for node j in newN odeSet do

19:

dist ← M IN DIST (j, n)

20:

if dist > δ ∗ then
14 行へ

21:2.67GHz の CPU と 12GB のメモリを用いる．OS は Vine

22:

Linux5.1 である. 対象になるデータは人工生成されることと実23:

際のデータ二つ種類で，提案したデータ構造と mCK 検索のア

24:

end if

ルゴリズムの検索性能を見る．

25:

end for26:

n を newN odeSet に入れる27:

if k = num then

5. 1 人工生成データ
性能評価について，クエリのキーワードの数 と データの数(レコード数) の二つのパラメータを変えて検索性能を評価す

else if dist > maxM inDist thenmaxM inDist ← distfor node a in newN odeSet do

28:
29:

る．最後はキーワードの分布が偏る場合について結果の直径とf lag ← T RU E

30:

実行時間の関係を調べる．

31:

for node b in newN odeSet do< maxM inDist thenif M AXDIST (a, b) =f lag ← F ALSE

5. 1. 1 クエリのキーワードの数の影響

32:

対象データについて，キーワードの総数が 100 と決めて，各33:

end if

キーワードに 100 個のレコードを関連づけ，ランダムで座標を34:

end for35:

if f lag = T RU E then

生成して木に入れる．つまり，レコードの数が 10000 である．

16 分割木のセルの容量は 100 とする．実験の結果を図 9 に示

a の keyword を keywordSet から一時的に除く

36:

a を newN odeSet から一時的に除く

37:

す．図 9(b) はランダムで m 個のキーワードを選んで検索を38:

end if

行うのを 1 回として 100 回実行の平均時間である，図 9(a) は39:

end for

ノード組み合わせの数は根ノードから葉ノードまでチェックし40:たノードセットの個数の平均値である．

41:

以下の 3 通りの枝刈り戦略を用いた方式について評価した:

mCKSearch(keywordSet, newN odeSet, T ree)elsek ←k+142:

end if43:

ルール 1 :(単にルール 1 を使う方式である.)

44:

ルール 1 と 2 :(ルール 1,2 両方を使う方式である.)

45:

最適化 :(キーワード近似 MBR を使って M IN DIST を求め，

46:

end ifルール 1 と 2 も使う方式である.)

47:

end whileelsek ←k−1

48: end if

図 9 によると，m の増大に応じて，実行時間とノード組み合(a) ノード組み合わせの数

図9(b) 実行時間

図 11

偏りデータ分布クエリのキーワードの数の影響
全空間を 100 セルを区切り，一つのセルにただ一つのキーワーわせの数は指数で増加する．ルール 1 と 2 を使う方式のは単にルール 1 を使う方式より実行時間が多い．原因はデータは地図に均一分布しているから，結果の直径は小さい．そのため，隣接のノードの組み合わせが多いので，ルール 2 は枝刈りできないのみならず，余計な判断時間がかかる．

ドに関連するレコードを入れる．そして，ランダムで m = 3, 4のキーワードのクエリで実行する．一つのセルの対角距離を1unit として，実行結果の直径 δ を 10 個の間隔 (0-1unit,12unit,...,8-9unit,9-10unit) に分けると，δ は必ず 1 つの間隔に落ちる．150 回の実験を行って，δ を分けて，各間隔に落ちた時のクエリ 1 回あたりの実行時間の平均値を図 12 に示す．(図5. 1. 2 レコードの数の影響対象になるデータについて，キーワードの総数が 100，各キー12(a) が m = 3, 図 12(b) が m = 4)

ワードに 100,300,500,700,900 のレコードを関連づけて実験を行う．つまり，レコードの総数は 10000,30000,50000,70000,90000である．16 分割木のセルの容量は 100 とする．クエリのキーワードの数 m = 4 とする．実行時間とノード組み合わせの数も 100 回実行の平均値である．結果を図 10 に示す．(図 9(a)，図 10(a) でルール 1 のみの方式はルール 2 の場合とほぼ一致している)(a) m=3(a) ノード組み合わせの数(b) 実行時間

図 10 レコードの数の影響 (m=4)(b) m=4

図 10 によると，レコードの増大に応じて，実行時間とノー

図 12 結果の直径 δ の影響ド組み合わせの数が増加する．16 分割木の階層が増加する と各葉ノードにレコードの数が増えるのも実行時間が増加する原図 12 によると, 結果の直径とともに実行時間は変化する．

因となる．このテストでは対象データはランダムでデータを生データが離れる場合，ルール 2 は明らかに有効に働いている．

成したため，答えになるオブジェクト集合が近くにある可能性データが離れて，判断必要なキーワードを削減するので，ノーが高い．そこで，閾値 δ ∗ は速く減少して，大部分の探索空間ドの組み合わせあるいは葉ノードのデータの組み合わせが減少が枝刈りした場合の結果になっている．

されるので，検索効率が高くなる．

5. 1. 3 データの偏りの影響

5. 2 実際のデータ

現実のデータは偏る場合もある．つまり，閾値 δ ∗ が大きく，本稿はアメリカの国勢調査局の TIGER(Topologically Inte-

大部分の探索空間を走査してから，結果を求める場合もある．

grated Geographic Encoding and Referencing)[8] システムか

そこで，偏るデータを生成して行う．生成データの分布を図 11らテキサス州のランドマークデータを取得して，16 分割木のに示す．

データ構造を作って，mCK 検索の実験を行った．データ総数

は 6613 個であり，キーワードの数は 35 である．16 分割木のセルの容量は 30 とする．木の高さは 6 である．

6. お わ り に

性能評価について，人工生成データと同じく，クエリのキー

本稿では，空間データの mCK 検索問題を扱って，データのワードの数により検索性能を評価する．ランダムで m 個のキー更新とデータセットのオーバラップ効率を考えて 2n 分割木のワードを選んで検索を行うことをテスト 1 回として，各 m にデータ構造を用いて，それぞれのキーワードに関連するノード対して 100 回テストを行い，実行時間の平均値を計算した．結の組み合わせ探索を行い，二つの枝刈りルールを利用して効率果を図 13 に示す．

化を図る方法を提案した．またキーワード近似 MBR を使ってアルゴリズムを最適化した．実験では，均一分布と偏り分布の人工生成データを使って，クエリのキーワードの数とレコードの数の変化に応じる実行時間の変化を調べた．その結果枝刈りルール 1 と 2 と最適化方法は探索空間を減少できることが判った．また，実データで実験を行った．結果によって，クエリのキーワードの数が多い場合，探索効率は良くないが，値の小さな δ ∗ の初期値を指定することで，探索時間が明らかに減少できると判った．
今後の課題としては，今のアルゴリズムは順番でノードの図 13 クエリのキーワードの数 m の影響 (実際のデータ)セットを組み合わせるので，枝刈りの効率はデータ分布による異なる．そのため，探索順を priority 順に変えることや δ ∗ の

図 13 を見ると，ルール 2 はそれほど有効に働いていない．原

上限を早く決める方法を導入することが重要である．

因は結果の直径は小さい，つまり求めたオブジェクトがお互いに近いからである. また，クエリのキーワードの数が多い場合，謝辞：本研究の一部は科研基盤 C24500109 の助成による.

実行効率は良くないと判る．原因として，提案のアルゴリズムは順番でノードを組み合わせているため，枝刈り能力がデータの分布より決まる．つまり，結果を見つける時点が遅ければ遅いほど閾値 δ ∗ の収束が遅く，探索空間木にチェックしたノードセットが多いので，時間がかかると考えられる．
上記の原因を検証するために，δ ∗ の初期値を指定する場合について同じの実験を行った．
テキサス州の一辺の長さは約 1000km ぐらいで，δ ∗ の初期値を 100km と 300km 二つ種類を設定する．つまり，直径が100km と 300km 以内の m 個のキーワードに関連するオブジェクトの集合を求めることになる．
実行結果を図 14 に示す．

(a) δ ∗ の初期値=300km(b) δ ∗ の初期値=100km∗

図 14 δ の初期値を指定する場合, クエリのキーワード m の数の影響
図 14 によって，δ ∗ の初期値が小さい場合，実行時間が明らかに減少することができる．そこで，もし値の小さな初期値を求めることができれば，検索効率が高くなるとわかる．この点が今後の課題である．

文

献[1] Christian S. Jensen. “Data Management on SpatialWeb”,keynote, Proceedings of the VLDB Endowment, Vol.
5, No.12, 2012
[2] R. Hariharan, B. Hore, C. Li, and S. Mehrotra. “Processingspatial- keyword queries in geographic information retrievalsystems.“ In SSDBM, pp. 16-25, 2007.
[3] Z. S. Li , B. H. Zhen , W. C. Lee, D. L. Lee , X. F. Wang
“ IR-Tree: An Eﬃcient Index for Geographic Document
Search” IEEE TRANSACTIONS ON KNOWLEDGE AND
DATA ENGINEERING, VOL. 23, NO. 4, APRIL 2011, pp.
585-599[4] D.X.Zhang, Y.M.Chee, Anirban Mondal, Anthony K.H.Tung,Masaru Kitsuregawa, ”Keyword Search in Spatial Databases:Towards Searching by Document,” IEEE ICDE, pp.688-699,2009.
[5] http://research.microsoft.com/en-us/projects/geolife/[6] http://twitter.com/[7] D. Papadias, N. Mamoulis, and Y. Theodoridis. “Processingand opti- mization of multiway spatial joins using R-trees.”
Proc. PODS, pp. 44―55, 1999.
[8] http://www.census.gov/geo/maps-data/data/tiger.html