影響圏を考慮した二色逆最近傍探索手法の提案

DEIM Forum 2016 D7-5

影響圏を考慮した二色逆最近傍探索手法の提案

後藤

佑介

†

大久保千織

††

岡鼻 雄飛

††

伊藤 大晃

††

千葉

孟

†

†

岡山大学大学院自然科学研究科 〒 700–8530 岡山県岡山市北区津島中 3–1–1

††

岡山大学工学部情報系学科 〒 700–8530 岡山県岡山市北区津島中 3–1–1

E-mail:

†

[email protected], [email protected],

††{

okubo,okahana,ito

}

@mis.cs.okayama-u.ac.jp

あらまし

本研究では，空間ネットワークにおいて，二つのグループ間で逆最近傍探索を行う二色逆最近傍探索を議

論する．既存の二色逆最近傍探索は，探索候補となるオブジェクトやクエリが動くたびにグループ間の位置関係を更

新するため，オブジェクト数の増加に応じて計算量は大きくなる．そこで，影響圏と呼ばれる領域を各オブジェクト

が設定し，領域単位でオブジェクトの位置情報を比較することで，計算量を削減できる．既存の二色逆最近傍探索で

は，地理情報を考慮した二つのオブジェクト間の距離であるネットワーク距離を用いた手法は，オブジェクトの探索

数が 1 の場合に限定されていた．本研究では，影響圏を考慮して，ネットワーク距離による探索数が複数となる場合

に拡張した二色逆最近傍探索手法を提案する．

キーワード

空間ネットワーク，クエリ処理，二色逆最近傍探索，影響圏

1.

は じ め に

ネットワーク上で移動端末による空間軸上の変化を表現でき る空間ネットワーク環境では，地理情報を扱うシステムとして

Geographic Information Systems (GIS) が広く用いられてい

る．また，GISの入力デバイスの一つであるGlobal Positioning

System (GPS) を用いた位置情報サービスが注目されており， さまざまな分野への応用が期待されている．空間ネットワーク 環境では，位置情報の問合せ元となるクエリオブジェクト（以 下，クエリ）が探索条件に応じて候補となる複数のターゲット オブジェクト（以下，ターゲット）を選択する．このとき，ク エリの位置情報をもとに，クエリからの距離が近いターゲット を探索する最近傍探索を用いることが有効であり，これまでに 多くの探索手法が提案されてきた． また，最近傍探索の考え方を用いて，クエリまでの距離が 近いターゲットを探索する逆最近傍探索に対する注目が高 まっている．逆最近傍探索は，同じグループに所属するクエリ と複数のターゲットとの関係性を探索する単色逆最近傍探索 (Monochromatic-RkNN)と，二種類のオブジェクトグループ に分けて，あるグループのクエリと他方のグループに所属す る複数のターゲットとの関係性を探索する二色逆最近傍探索 (Bichromatic-RkNN)に分類される．本研究では，二色逆最近 傍探索について考える． 最近傍探索を行う場合，問合せ元のクエリからすべてのター ゲットまでの距離情報を取得した上で，クエリから近い順番に ターゲットを求めると，計算量が膨大になり，探索時間は長大 化する．そこで，空間ネットワーク上で最近傍となるオブジェ クトの位置情報を追加した領域（以下，影響圏）を設定する． ユーザは，自身の現在位置がどのターゲットの影響圏かを確認 することで最近傍となるターゲットを探索でき，最近傍探索に かかる時間を短縮できる． 既存の二色逆最近傍探索では，地理情報を考慮した二つのオ ブジェクト間の測定距離であるネットワーク距離を用いた手法 は，オブジェクトの探索数が1の場合に限定されていた．本研 究では，影響圏を考慮して，ネットワーク距離による探索数が 複数となる場合に拡張した二色逆最近傍探索手法を提案する．

2.

空間ネットワーク

2. 1 概 要 空間ネットワークでは，多次元空間上で移動端末による空間 軸上の変化を表現できる．クエリは，空間ネットワーク上に存 在するターゲットの位置情報を取得することで，さまざまな サービスに利用できる． 空間ネットワークにおいて，オブジェクト間の距離は，ユー クリッド距離とネットワーク距離の二種類に分類される．以降 の節で順番に説明する． 2. 2 ユークリッド距離 空間ネットワーク上に存在する二つのオブジェクトについ て，オブジェクト間の直線距離をユークリッド距離と呼ぶ．例 えば，空間ネットワーク内に 二つのオブジェクトA(x1, y1)， B(x2, y2)が存在する場合，ユークリッド距離d(A,B)は以下の 式で表される． d(A.B)=

√

(x1− x2)2+ (y1− y2)2 (1) ユークリッド距離は，経路上に存在する障害物の有無に関わ らず，二つのオブジェクト間の最短距離を求めることができる． 2. 3 ネットワーク距離 空間ネットワークに地理情報を適用する場合，二つのオブ ジェクト間で山や川といった自然物，および家やビルといった 人工物を考慮する必要がある．このような空間ネットワーク上 で，ユーザがあるオブジェクトから別のオブジェクトへ移動す

A A A A A1 2 A4 3 6 5 図 1 最近傍探索 (k = 2) A A A A A1 2 A4 3 6 5 図 2 逆最近傍探索 る場合，二つのオブジェクト間の移動距離は，ユークリッド距 離よりも長くなる．このように，地理情報を考慮した二つのオ ブジェクト間の距離をネットワーク距離と呼ぶ．本研究では， 空間ネットワーク上の地理情報を反映した重み付きグラフを用 いて，二つのオブジェクト間の距離をネットワーク距離で表す．

3.

探 索 手 法

3. 1 最近傍探索 最近傍(k-Nearest Neighbor，以下，kNN)探索は，空間ネッ トワーク上に複数のオブジェクトが存在する場合，問合せ元と なるクエリから距離が近い順番にk個(k >_{= 1)}のターゲットを 探索する方法である．図1は，kが2の場合における最近傍探 索の例である．クエリがA4の場合の探索結果は，A4からの距 離が短い順番に，A2とA6となる． 3. 2 逆最近傍探索 逆最近傍(Reverse kNN，以下，RkNN )探索は，クエリに 対して複数のターゲットがどのような位置関係であるかを算出 して，最近傍探索と逆方向の関係を求める方法である．例えば， 図2において，A4のR1NNはA6 である． 逆最近傍探索では，クエリから1NNの関係にあるターゲッ トは，必ずしもクエリから逆に1NNの関係になるとは限らな い．例えば，図2の場合，A2 のR1NNとなるオブジェクトの うち一つはA4 となる一方で，A2の最近傍はA1となるため， A2はA4のR1NNではない． これまでの研究では，クエリの探索対象は，自身の現在位置 からどのくらいの距離でどの程度存在するかが重要とされてき た．しかし近年，多くのユーザが携帯端末で自分の位置情報を A A A A A A 1 1 2 4 3 6 5 B B B B B B 1 2 3 4 5 6 図 3 二色逆最近傍探索（グループ A がクエリの場合） A A A A A A 1 1 2 4 3 6 5 B B B B B B 1 2 3 4 5 6 図 4 二色逆最近傍探索（グループ B がクエリの場合） 管理されるようになり，人とのかかわりを間接的に意識する環 境が一般的になった．このため，多くのユーザは，自身の存在 が他者および他のグループからどのように意識されているかに ついての情報を取得したい要求が高まっている． 3. 3 単色逆最近傍探索 単色逆最近傍(Monochromatic-RkNN)探索は，3. 2節で述 べた一般的な逆最近傍探索である．クエリとターゲットは，同 じ種類のオブジェクトにおいて一対一で互いの位置関係を探索 するため，クエリの探索対象は，空間ネットワーク上に存在す るすべてのターゲットとなる．このとき，単色逆最近傍探索で は，クエリを自身の最近傍とするターゲットを探索する必要が ある． 3. 4 二色逆最近傍探索 二色逆最近傍(Bichromatic-RkNN，以下，BRkNN)探索は， 二つのグループで構成されたオブジェクト間で逆最近傍を探索 する．例えば，二つのコンビニエンスストアのグループA，B がある営業エリア内でそれぞれ複数の店舗を営業している場合， グループAに所属するオブジェクトがグループBに所属する オブジェクトを対象にしたRkNNの関係を図3に示す．また， 逆に，グループBに所属するオブジェクトがグループAに所 属するオブジェクトを対象にしたRkNNの関係を図4に示す． このような関係は，あるコンビニエンスストアのグループが 次にオープンする新規店舗の場所を決める場合に利用できる． しかし，二色逆最近傍探索に関する研究は，グループ間でオブ ジェクトの探索方法が複雑であるため，進んでいない．本研究 では，グループ間でオブジェクト逆最近傍探索を行うため，二 色逆最近傍探索を検討する．

母点

図 5 ボロノイ図

p

₁

p

p

2 3

s

1

s

2

s

7

s

8

s

9

s

12

s

₁₃

s

₁₄

s

15

s

11

s

10

s

4

s

6

s

5

s

3 図 6 ネットワークボロノイ図

4.

ネットワークボロノイ図

Voronoi Diagram (以下，ボロノイ図)は，空間ネットワーク 上で任意の位置に複数個の点(以下，母点)を配置した状況で， 同じ空間上に存在する点がどの母点に近いかに応じて領域分け した図である．図5は，二次元の空間ネットワーク上でユーク リッド空間を用いたボロノイ図の例である．黒点は母点，白点 は母点以外のオブジェクトである．白点のオブジェクトは，自 身が存在する領域内にある母点を自身の最近傍とする．空間 ネットワークにおけるユークリッド距離を用いたボロノイ図に ついて，領域の境界線は，二つの母点間で構成される垂直二等 分線の一部となる．

Network Voronoi Diagram (以下，ネットワークボロノイ図)

は，空間ネットワーク上でネットワーク距離を用いたボロノ イ図である．図6に，二次元の空間ネットワーク上でネット ワーク距離を用いたネットワークボロノイ図の例を示す．p1， p2 およびp3は母点となるオブジェクトであり，s1, s2, ..., s15 は母点以外のオブジェクトである．空間ネットワーク上におけ るオブジェクト間の経路上に存在する四角形は，母点が構成 する領域の境界を表す．図6の場合，オブジェクトs1, s2, s3 は，母点p1を自身の最近傍とするオブジェクトとなる．同様 に，オブジェクトs7, s8, s9, s12, s13は母点p2，オブジェクト s4, s5, s6, s10, s11, s14, s15は母点p3を自身の最近傍とするオブ ジェクトとなる． 図 7 ユークリッド距離を用いた逆最近傍探索における影響圏

5.

影

響

圏

5. 1 概 要 逆最近傍探索では，すべてのオブジェクトに対してクエリか らの距離がもっとも近いターゲットを探索するため，オブジェ クト数の増加に応じて計算量は膨大になる．そこで，オブジェ クトに対して逆最近傍探索を行うため，オブジェクトの影響圏 を作成する．影響圏は，空間ネットワーク上に存在するすべて のオブジェクトに対して，あるオブジェクトが自身を最近傍と 判断する領域である．クエリは，自身の位置情報を含む影響 圏をもつターゲットを最近傍として決定する．影響圏を作成す ることで，クエリの最近傍となるターゲットの探索時間を短縮 する． ターゲットtに対して，ユークリッド距離で逆最近傍探索の 影響圏を作成する例を図7に示す．図7では，影響圏を作成す るターゲットtとオブジェクトpi(i = 1,· · · , 7)が空間ネット ワークに存在し，tの影響圏を作成する．クエリqに対して最 近傍探索を行う場合，tの影響圏の内部にq が存在するため， qからもっとも近いオブジェクトはtであることが分かる． 影響圏は，ターゲットtと空間ネットワークに存在する各オ ブジェクト間の垂直二等分線で作成される．図7の場合，影響 圏はtとpi (i = 1,· · · , 4)による垂直二等分線によって作成さ れる． 5. 2 影響圏の作成手法 逆最近傍探索における単純な影響圏作成手法（以下，単純手 法）では，空間ネットワークに存在するすべてのオブジェクト は，クエリとの垂直二等分線を引く．図7のように，ターゲッ トtとオブジェクトpi(i = 1,· · · , 7)が空間ネットワークに存 在する場合，すべてのオブジェクトpi に対してターゲットt からの距離が近い順に垂直二等分線を引き，影響圏を作成する． 単純手法では，クエリは影響圏の作成に影響を与えないオブ ジェクトに対しても垂直二等分線を引くため，効率が悪い．図 7の場合，単純手法では，クエリとp5, p6,およびp7 との間に 引く3本の垂直二等分線は，影響圏の作成に影響しない．

6.

関 連 研 究

6. 1 逆最近傍探索 逆最近傍探索に関する研究はいくつか行われている．Taniar らは，空間ネットワークにおける最近傍探索の重要性につい て述べている[1]．Taniarによると，最近傍探索手法は4種類 に分類できる．一つ目は空間を考慮した手法であり，オブジェ クト間のユークリッド距離の他に，道路ネットワークと呼ばれ るオブジェクト間の道路距離をもとに構成されたネットワー ク上で最近傍探索を行う．近年では，ユークリッド距離とネッ トワーク距離を組み合わせた手法[2], [3]や，Network Voronoi Diagram (NVD)を用いた手法[4]が提案されている． 二つ目は結果を利用した手法であり，クエリが正確にk個の オブジェクトを探索する必要性を検討する．既存の最近傍探索 では，オブジェクトの探索条件に制約を加えてk個のオブジェ クトを正確に探索する場合がほとんどであった．しかし，空間 ネットワークや地理的な状況を考慮した場合，探索したオブ ジェクトがk個未満であったり，k個以上となっても問題ない 場合が存在する．そこで，オブジェクトをクラスタリングして， クエリが一定領域内のクラスタを探索するように条件を緩和す ることで，より一般的な空間ネットワークで最近傍探索を利用 できる手法が提案されている[5]． 三つ目は，クエリを発行する地点を考慮した手法である．こ れまでの手法では，一つのクエリ発行をもとに多くのオブジェ クトから候補となるk個のオブジェクトを探索していたが，同 時に複数のクエリが発行される場合に最近傍探索を行う手法を 検討する必要がある．例えば，複数のクエリオブジェクトが同 じオブジェクトを選択しないように探索する場合，処理は複雑 になる．そこで，データマイニングによるクラスタリングの概 念を導入した手法が提案されている[6], [7]． 四つ目は，本研究で取り扱うオブジェクト間の関係性を考慮 した手法である．これは逆最近傍探索が該当し，さまざまな手 法が提案されている[8], [9]． Cheemaらは，空間ネットワーク内で逆最近傍探索の計算量

を削減する手法として，Swift And Cheap (SAC)法を提案し

ている[10]．SAC法では，複数のオブジェクトが移動している 状況で逆最近傍探索のクエリを発行する場合，オブジェクトご とに長方形領域を設定する．クエリとターゲットで長方形領域 を比較することで，タイムスタンプごとにすべてのオブジェク トの位置を正確に求めるコストを削減する． 本研究では，複数のクエリが複数のターゲットに対して同時 にクエリを発行する状況で，オブジェクト間の関係性を考慮し て逆最近傍探索を行う．このとき，各オブジェクトの正確な位 置を含む長方形領域を設定することで，新規オブジェクトが移 動してもオブジェクト間の関係性が変化しない移動可能領域を 算出する． 6. 2 影響圏を考慮した領域作成手法 現在，ユークリッド距離を用いた逆最近傍探索で影響圏を考 慮した領域作成手法として，多くの手法が提案されている．以 下の項で，逆最近傍探索における効率的な領域作成手法として， 図 8 2*farthest vertex 法 2*farthest vertex法，初期領域を使用した影響圏探索手法，お よび初期領域を使用しない影響圏探索手法の三つを紹介する． 6. 2. 1 2*farthest vertex法 2*farthest vertex 法[11], [12]では，ターゲットとなるオブ ジェクトは，空間ネットワーク内に存在するオブジェクトに対 して垂直二等分線を引き，これらの垂直二等分線で作成される 多角形を初期領域とする．初期領域の多角形を構成するすべて の頂点のうち，ターゲットからの距離がもっとも遠い頂点を選 択する．次に，ターゲットと選択した頂点間の距離の2倍を半 径とし，ターゲットの位置が中心となる円を作成する．クエリ は，作成した円の内部に存在するオブジェクトに対してのみ垂 直二等分線を引く．もし，初期領域が作成されない場合，単純 手法と同様に，空間ネットワークに存在するすべてのオブジェ クトとの垂直二等分線を引く． 2*farthest vertax法において，初期領域をもとに作成した円 を図8に示す．ターゲットtとオブジェクトpi (i = 1,· · · , 7) が空間ネットワーク内に存在し，tの初期領域を作成する．図 8では，p1, p2,およびp3に対して垂直二等分線をそれぞれ引 くことで，初期領域を作成する．オブジェクトp7は作成した 円の外部に存在するため，逆最近傍探索の領域作成に影響しな いオブジェクトであることが分かる． 6. 2. 2 初期領域を使用した影響圏探索手法 初期領域を使用した影響圏探索手法[11]では，従来手法と同 様に作成した初期領域について，初期領域を構成する多角形の 各頂点を中心とし，各頂点からターゲットまでの距離を半径と する円を作成する．この円を影響圏とする．影響圏の内部に存 在するオブジェクトにのみ垂直二等分線を引く．初期領域が作 成されない場合，単純手法と同様に，空間ネットワーク内に存 在するすべてのオブジェクトとの垂直二等分線を引く．初期領 域を使用する影響圏を用いた手法において，初期領域を作成し た後に影響圏を作成した例を図9に示す．図9では，ターゲッ トtとオブジェクトpi (i = 1,· · · , 7)が空間ネットワーク内に 存在し，tの初期領域を作成する．また，pi (i = 1,· · · , 7)に 対して垂直二等分線を引くことで，初期領域を作成する．図9 で示す三つの円は，各頂点に対してそれぞれ作成した影響圏で ある．オブジェクトp5, p6,およびp7は影響圏の外部に存在す るため，逆最近傍探索における領域作成に影響しないことが分

図 9 初期領域を使用した影響圏探索手法 図 10 初期領域を使用しない影響圏探索手法 かる． 6. 2. 3 初期領域を使用しない影響圏探索手法 初期領域を使用しない影響圏探索手法[11]では，ターゲット とオブジェクト間の垂直二等分線同士の交点が作成される場合， ターゲットから垂直二等分線に対して垂直な直線を引き，刈取 り領域を作成する．次に，ターゲットと垂直二等分線の交点を 中心として，ターゲットから交点までの距離を半径とする影響 圏の円を作成する．刈取り領域の内部かつ影響圏の外部に存在 するオブジェクトは逆最近傍探索の領域生成に関係せず，刈取 り領域の外部の点，および刈取り領域の内部かつ影響圏の内部 の点にのみ垂直二等分線を引く． 刈取り領域と影響圏を用いて，逆最近傍探索の領域を作成す る例を図10に示す．図10では，ターゲットtとオブジェクト pi (i = 1,· · · , 7)が空間ネットワーク内に存在し，オブジェク トp1およびp2に対して垂直二等分線をそれぞれ引く．破線は， 逆最近傍探索の領域を作成するオブジェクトから垂直二等分線 に対する垂線であり，塗りつぶされた領域は刈取り領域である． 刈取り領域の内部に存在するオブジェクトp4は影響圏の内部 に存在するため，クエリqとオブジェクトp4との間に垂直二 等分線を引く．次に，刈取り領域の外部に存在するオブジェク トのうち，ターゲットからの距離がもっとも近いオブジェクト p3に対して垂直二等分線を引き，刈取り領域と影響圏の範囲を それぞれ更新する．

7.

提 案 手 法

7. 1 概 要 空間ネットワークにおいて，ネットワーク距離を用いて探索 数kが複数となる場合に拡張したBRkNN手法を提案する． 提案手法では，ターゲットを母点としたネットワークボロノイ 図を作成した後，各ターゲットのkNNを三つのステップに分 けて探索し，条件を満たさないターゲット候補の除外(以下， 刈取り)を行う．ターゲットからの距離がクエリよりも短いオ ブジェクトをk個検出した場合，このターゲットはクエリの BRkNNではないため，除外する．すべてのターゲットに対す る探索が終了した段階で除外されなかったターゲットは，クエ リのBRkNNとなる． 7. 2 想 定 環 境 本手法を提案するにあたり，想定する環境を箇条書きで示す． • 空間ネットワークは二次元で構成する． • オブジェクト間の距離はネットワーク距離で表す． • k >_{= 1}とする． • オブジェクトのグループは二種類とする． 7. 3 探 索 手 順 k >_{= 2}の場合に対応した提案手法におけるターゲットの探索 手順を説明する．提案手法のアルゴリズムは，k = 1の場合の みに対応した既存手法[13]のアルゴリズムを拡張して作成した． 初めに，ターゲットを母点としたネットワークボロノイ図を 作成する．次に，すべてのターゲットに対して三つのステップ で刈取りを行いながら探索して，クエリのBRkNNとなるター ゲットを求める． 7. 3. 1 ネットワークボロノイ図の作成 初めに，n個のターゲット(p1, p2, ..., pn)を母点として，ネッ トワークボロノイ図を作成する．ネットワークボロノイ図の作 成は，論文[14]で用いられているアルゴリズムを使用する． 7. 3. 2 ステップ1 : ネットワーク距離を用いた刈取り クエリとターゲットpkとのネットワーク距離を測定した上 で，pkを母点とするボロノイ領域V P (pk)内に存在するクエ リと同じグループに所属するオブジェクトとのネットワーク距 離を比較する．pkとのネットワーク距離がクエリよりも短いオ ブジェクトがk個以上存在する場合，pkは，クエリのBRkNN とはならないため，候補から除外し，次のターゲットの処理に 移行する．pkとのネットワーク距離がクエリよりも短いオブ ジェクトがk個未満となる場合，ステップ2に移行する．以下 に，詳細な手順を示す． （1） pkを母点とするボロノイ領域内において，pkとクエ リ以外のすべてのクエリと同じグループsiとのユークリッド 距離(DE(pk, si))を求め，キューSQに格納し，DEの長さ をもとにSQの各要素を昇順でソートする． （2） SQに格納されている先頭の要素を取り出し，pkとク エリQとのネットワーク距離 (DN (pk, Q))と比較する．SQ が空の場合，ステップ2へ． （3） DE(pk, si) < DN (pk, Q)なら，DN (pk, si)を求め， DN (pk, Q)と比較する．DE(pk, si) >_{= DN (p}k, Q)なら，SQ

を空にし，ステップ 2へ． （4） DN (pk, si) < DN (pk, Q)の場合，kの値を1減ら す．この後，k = 0であれば，pkを候補から除外して，次の 候補となるターゲットの処理に移行する．また，k > 0または DN (pk, si) >_{= DN (p}k, Q)であれば，2. へ． 7. 3. 3 ステップ2 : ユークリッド距離を半径とする円を用 いた刈取り ステップ2では，クエリとpkとのユークリッド距離を半径， pkを中心とする円を作成し，円内の領域と重なるすべてのボ ロノイ領域に対して，ステップ1と同じ処理を行う．ステップ 2で探索するオブジェクトとpkとのユークリッド距離は，ク エリとpkとのユークリッド距離よりも短くなる可能性が高い． これは，二つのオブジェクト間のユークリッド距離が短い場合 は，ネットワーク距離も短くなる可能性が高いためである．ス テップ2を実行することで，ステップ3で候補となるオブジェ クトをすべて探索する場合に比べて探索時間を短縮できる．以 下に，詳細な手順を示す． （1） e = DE(pk, Q)を求め，中心pk，半径eの円を作成 する． （2） 円内の領域と重なるボロノイ領域V P (p)をすべて求 める． （3） 各V P (p)についてDE(pk, p)を求め，DE(pk, p)と V P (p)を一組にして，キューP Q′に格納する． （4） キューP Qを作成し，P Q′の要素をP Qに複製して， DE の長さをもとにP Qの各要素を昇順でソートする． （5） P Qが空であれば，ステップ3へ．そうでなければ， P Qに格納されている先頭の要素を取り出す． （6） 取り出した要素に対して，ステップ1を実行する． 7. 3. 4 ステップ3 : ネットワーク距離を半径とする円を用 いた刈取り クエリとpkとのネットワーク距離を半径，pkを中心とする 円を作成し，円内の領域と重なるボロノイ領域のうち，ステッ プ2で探索した領域以外の領域に対して，ステップ1と同じ 処理を行う．このとき，円の外側の領域にあるオブジェクトと pkとのユークリッド距離は，クエリとpkとのネットワーク距 離より長くなる．一般的に，二つのオブジェクト間の距離につ いて，ネットワーク距離はユークリッド距離より長くなるため， 円の外側の領域にあるオブジェクトとpkとのネットワーク距 離は，クエリとpkとのネットワーク距離より長くなる．した がって，ステップ3が終了した時点で，クエリよりpkに近い オブジェクトがk個未満である場合，pkはクエリのBRkNN となる．以下に，詳細な手順を示す． （1） e′= DN (pk, Q)を求め，中心pk，半径e′の円を作成 する． （2） 円内の領域と重なるボロノイ領域V P (p)をすべて求 める． （3） 各V P (p)に対応するDE(pk, p)を求め，DE(pk, p) とV P (p)を一組にして，キューP Q′′に格納する． （4） P Q′′にありP Q′にはないV P (p)の要素をP Qに格 納し，DEの長さをもとにP Qの各要素を昇順でソートする． C1 Q p₁ p p 2 3 s1 s2 s7 s8 s9 s12 s13 s14 s15 s11 s10 s4 s6 s5 s3 図 11 DE(p1, Q) を半径とする円 C1を作成した様子 C2 C1 Q p₁ p p 2 3 s1 s2 s7 s8 s9 s12 s13 s14 s15 s11 s10 s4 s6 s5 s3 図 12 DN (p1, Q) を半径とする円 C2を作成した様子 このとき，P Qが空であれば，pkはQのBRkNNとなり，探 索処理を終了する． （5） P Qに格納されている先頭の要素から順番に，ステッ プ1を実行する． 7. 4 導 入 例 図6を例にして，提案手法を実行する．s3をクエリQ，k = 2 とし，p1に対してステップ1から3を適用した．以下で，処 理手順を順番に説明する． （1） ステップ1で，ボロノイ領域V P (p1)内において，ク エリと同じグループでクエリを除くオブジェクトをすべて探索 する．V P (p1)内において，対象となるオブジェクトはs1, s2 であるため，この二つのオブジェクトとp1とのユークリッド 距離をそれぞれ求め，SQに格納し，DEの長さをもとにSQ の各要素を昇順でソートする．このとき，SQは以下のように 表される． SQ ={< s2, DE(p1, s2) >, < s1, DE(p1, s1) >} （2） p1 とQとのネットワーク距離DN (p1, Q)を求め， DE(p1, s2)と比較する．ステップ1の3.より，DE(p1, s2) < DN (p1, Q)であるため，DN (p1, s2)を求め，DN (p1, Q)と比 較する．このとき，DN (p1, s2) < DN (p1, Q)であるため，kの 値を1減らし，k = 1とする．次に，DE(p1, s1)とDN (p1, Q) を比較する．DE(p1, s1) > DN (p1, Q)であるため，ステップ 1の3.よりSQを空にし，ステップ2へ． （3） e = DE(p1, Q)を求め，中心p1，半径eの円C1を作

成する．図11に，DE(p1, Q)を半径とする円C1を作成した様 子を示す．次に，円C1内の領域と重なるボロノイ領域を求め， キューP Q′に格納する．このとき，円C1内の領域と重なるボ ロノイ領域は存在しないため，P Q′ は空となり，同時にキュー P Qも空となる．ステップ2の5. より，ステップ3へ． （4） e′= DN (p1, Q)を求め，中心p1，半径e′の円C2を 作成する．図12に，DN (p1, Q)を半径とする円C2を作成し た様子を示す．円C2 内の領域と重なるボロノイ領域となる V P (p3)に存在する各母点とp1とのユークリッド距離を求め， P Q′′に格納する．次に，P Q′′にありP Q′にはないV P (p)の 要素をP Qに格納する．このとき，P Qは以下のように表さ れる． P Q ={< V P (p3), DE(p1, p3) >} （5） P Qに格納されている先頭の要素V P (p3) を取り出 し，V P (p3)内に存在するターゲット以外のオブジェクトであ るs4, s5, s6, s10, s11, s14, s15とp1とのユークリッド距離をそ れぞれ求め，SQに格納し，DEの長さをもとにSQの各要素 を昇順でソートする．このとき，SQは以下のように表される． SQ = {< s4, DE(p1, s4) >, < s5, DE(p1, s5) >, < s10, DE(p1, s10) >, < s6, DE(p1, s6) >, < s11, DE(p1, s11) > , < s14, DE(p1, s14) >, < s15, DE(p1, s15) >} （6） DE(p1, s4) < DN (p1, Q)であるため，DN (p1, s4)を 求め，DN (p1, Q)と比較する．DN (p1, s4) > DN (p1, Q)であ るため，ステップ1の4. よりステップ1の2. へ． （7） DE(p1, s5) > DN (p1, Q)であるため，ステップ1の 3. より，ステップ2へ．また，ステップ2の5. より， P Q が空であるため，ステップ3へ．ステップ3の4. より，探索 処理を終了し，p1はQのBRkNNとなる．

8.

評

価

8. 1 概 要 提案手法の有用性を検証するため，計算機上でシミュレー ション評価を行った．比較する手法として，あるターゲットに対 して，クエリとの距離と，クエリと同じグループに所属するク エリ以外のオブジェクトとの距離の二つを順番に比較し，ター ゲットとクエリとの距離より短いオブジェクトがk個見つかっ た時点で次のターゲットの探索に移行する線形探索を用いる． 提案手法および線形探索のプログラムは，C言語で作成した． 8. 2 評 価 環 境 計算機シミュレーションによる評価環境を以下に示す． • 空間内のオブジェクト数は，100とする． • 空間の大きさは，縦1000，横1000の二次元領域とする． • 探索の実行時間を110回計測し，実行時間の上位5回 と下位5回を除く計100回の平均を用いて評価する． 8. 3 探索数の影響 探索数kの値を変化させた場合の探索時間の変化を図13に 示す．横軸は探索数k，縦軸は二色逆最近傍探索の実行時間で ある．比較評価として，提案手法と線形探索の二つを用いる． 探索数は，1から10とし，ターゲットの数は10個と50個の 二つの場合で，提案手法と線形探索それぞれについて，BRkNN 図 13 探索数と実行時間 図 14 ターゲット数と実行時間 の実行時間を算出した． 図13より，探索数が増加すると，距離の比較対象となるオブ ジェクト数が増加するため，提案手法と線形探索のどちらでも 実行時間は長大化する．特に，ターゲット数が同数の場合，ほ ぼすべての場合において，提案手法による探索の実行時間は線 形探索に比べて短いことが分かる．また，ターゲット数が50， 探索数kが9または10の場合，線形探索の実行時間は提案手 法に比べて短い．探索数とターゲット数がどちらも多い場合， 距離の比較対象となるオブジェクト数が多くなり，かつクエリ と同じグループのオブジェクト数が少なくなるため，提案手法 と線形探索で探索するオブジェクト数はほぼ同じになる．提案 手法では，距離を比較すべきオブジェクトか否かの判別処理を 行うため，この処理時間の影響で，線形探索に比べて実行時間 が長くなると考えられる． 8. 4 ターゲット数の影響 ターゲット数を変化させた場合の探索時間の変化を図14に 示す．横軸はターゲット数，縦軸は二色逆最近傍探索の実行時 間である．ターゲット数は，10から90まで10刻みとし，探 索数は1個と5個の場合で，提案手法と線形探索それぞれに ついてBRkNNの実行時間を算出した． 図14より，探索数kが同じ場合，提案手法の実行時間は線形 探索に比べて短いことが分かる．また，探索数が5，ターゲッ ト数が60以上の場合，提案手法と線形探索の実行時間の差は ほとんど無い．一方で，探索数が5でターゲット数が70以上 の場合，ターゲット数の増加にともない，実行時間は短くなる． これは，ターゲット数がクエリと同じグループのオブジェクト

数より多くなることで，提案手法と線形探索のそれぞれで距離 を比較するオブジェクト数がほぼ同じになるとともに，距離を 比較するオブジェクト数が少なくなるためであると考えられる．

9.

お わ り に

本研究では，ネットワーク距離を用いた空間ネットワーク上 のオブジェクト探索において，影響圏を考慮してオブジェクト の探索数が複数となる場合に拡張した二色逆最近傍探索手法を 提案した．提案手法は，ネットワークボロノイ図を作成した後， 各ターゲットのkNNを三つのステップに分けて探索し，条件 を満たさないターゲット候補の除外を行うことで，実行時間を 短縮する．評価の結果，空間の大きさが 縦 1000，横1000の 二次元空間でオブジェクト数が100の場合，提案手法における 実行時間は線形探索に比べて短縮できることが分かった． 今後の予定として，オブジェクトが空間ネットワーク上を動 的に移動する場合において，二色逆最近傍探索の実行時間を短 縮する手法を提案する． 文 献

[1] D. Taniar, and W. Rahayu, “A Taxonomy for Nearest Neighbour Queries in Spatial Databases,” Journal of Com-puter and System Sciences, vol.79, pp.1017-1039, 2013. [2] C. Xia, D. Hsu, and A. K. H. Tung, “A Fast Filter for

Obstructed Nearest Neighbor Queries,” Lecture Notes in Computer Science, vol.3112, pp.203-215, 2004.

[3] J. Zhang, D. Papadias, K. Mouratidis, and M. Zhu, “Spa-tial Queries in the Presence of Obstacles,” Lecture Notes in Computer Science, vol.2992, pp.366-384, 2004.

[4] M. R. Kolahdouzan, and C. Shahabi, “Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases,” The VLDB Journal, vol.30, pp.840-851, 2004.

[5] J. Han, M. Kamber, and J. Pei, “Data Mining: Concepts and Techniques 3rd edition,” The Morgan Kaufmann Series in Data Management Systems, Morgan Kaufmann Publish-ers, 2011.

[6] Y. Chen, and J. M. Patel, “Efficient Evaluation of All-Nearest-Neighbor Queries,” Proceedings of IEEE 23rd In-ternational Conference on Data Engineering (ICDE 2007), pp.1056-1065, 2007.

[7] J. Zhang, N. Mamoulis, D. Papadias, and Y. Tao, “All-Nearest-Neighbors Queries in Spatial Databases,” Proceed-ings of 16th International Conference on Scientific and Sta-tistical Database Management (SSDBM 2004), pp.297-306, 2004.

[8] D. Taniar, M. Safar, Q. T. Tran, J. W. Rahayu, and J. H. Park, “Spatial Network RNN Queries in GIS,” The Com-puter Journal, vol.54, Issue 4, pp.617-627, 2011.

[9] Q. T. Tran, D. Taniar, and M. Safar, “Reverse k Nearest Neighbor and Reverse Farthest Neighbor Search on Spatial Networks,” Lecture Notes in Computer Science, vol.5740, pp.353-372, 2009.

[10] M. A. Cheema, W. Zhang, X. Lin, Y. Zhang, and X. Li, “Continuous Reverse k Nearest Neighbors Queries in Eu-clidean Space and in Spatial Networks,” The VLDB Jour-nal, vol.21, pp.69-95, 2012.

[11] W. Wu, F. Yang, C. Y. Chan, and K. L. Tan, “FINCH: evaluating reverse k-Nearest-Neighbor queries on locational data,” Proceedings of VLDB Endowment, vol.1, Issue 1, pp.1056-1067, 2008.

[12] K. M. Adhinugraha, D. Taniar, and M. Indrawan,

“Find-ing reverse nearest neighbors by region,” Concurrency and Computation: Practice and Experience, vol.26, pp.1142-1156, 2014.

[13] Q. T. Tran, D. Taniar, and M. Safar, “Bichromatic reverse nearest-neighbor search in mobile system”, IEEE Systems Journal, vol.4, no.2, pp.230-242, 2010.

[14] 木部宏昭, 蒲原智也, 大西真晶, 上島紳一, “ネットワークボロノイ 図を用いた指定範囲を結ぶ経路の生成および評価”, 電子情報通 信学会第 18 回データ工学ワークショップ (DEWS2007), C8-5, 2007.