DEIM Forum 2016 D7-5

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

大久保千織††

岡鼻雄飛††

伊藤 大晃††

千葉孟†† 岡山大学大学院自然科学研究科 〒 700–8530 岡山県岡山市北区津島中 3–1–1†† 岡山大学工学部情報系学科 〒 700–8530 岡山県岡山市北区津島中 3–1–1
E-mail: †gotoh@cs.okayama-u.ac.jp, chiba@mis.cs.okayama-u.ac.jp,††{okubo,okahana,ito}@mis.cs.okayama-u.ac.jp
あらまし

本研究では，空間ネットワークにおいて，二つのグループ間で逆最近傍探索を行う二色逆最近傍探索を議論する．既存の二色逆最近傍探索は，探索候補となるオブジェクトやクエリが動くたびにグループ間の位置関係を更新するため，オブジェクト数の増加に応じて計算量は大きくなる．そこで，影響圏と呼ばれる領域を各オブジェクトが設定し，領域単位でオブジェクトの位置情報を比較することで，計算量を削減できる．既存の二色逆最近傍探索では，地理情報を考慮した二つのオブジェクト間の距離であるネットワーク距離を用いた手法は，オブジェクトの探索
数が 1 の場合に限定されていた．本研究では，影響圏を考慮して，ネットワーク距離による探索数が複数となる場合に拡張した二色逆最近傍探索手法を提案する．
キーワード

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

1. は じ め に

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

ネットワーク上で移動端末による空間軸上の変化を表現できは，オブジェクトの探索数が 1 の場合に限定されていた．本研

る空間ネットワーク環境では，地理情報を扱うシステムとして

究では，影響圏を考慮して，ネットワーク距離による探索数がGeographic Information Systems (GIS) が広く用いられてい複数となる場合に拡張した二色逆最近傍探索手法を提案する．

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

System (GPS) を用いた位置情報サービスが注目されており，

2. 空間ネットワーク

さまざまな分野への応用が期待されている．空間ネットワーク

2. 1 概環境では，位置情報の問合せ元となるクエリオブジェクト（以空間ネットワークでは，多次元空間上で移動端末による空間

下，クエリ）が探索条件に応じて候補となる複数のターゲット

軸上の変化を表現できる．クエリは，空間ネットワーク上に存

オブジェクト（以下，ターゲット）を選択する．このとき，ク在するターゲットの位置情報を取得することで，さまざまな

エリの位置情報をもとに，クエリからの距離が近いターゲット

サービスに利用できる．

を探索する最近傍探索を用いることが有効であり，これまでに多くの探索手法が提案されてきた．
また，最近傍探索の考え方を用いて，クエリまでの距離が要

空間ネットワークにおいて，オブジェクト間の距離は，ユークリッド距離とネットワーク距離の二種類に分類される．以降の節で順番に説明する．

近いターゲットを探索する逆最近傍探索に対する注目が高

2. 2 ユークリッド距離まっている．逆最近傍探索は，同じグループに所属するクエリ

空間ネットワーク上に存在する二つのオブジェクトについと複数のターゲットとの関係性を探索する単色逆最近傍探索て，オブジェクト間の直線距離をユークリッド距離と呼ぶ．例(Monochromatic-RkNN) と，二種類のオブジェクトグループ

えば，空間ネットワーク内に 二つのオブジェクト A(x1 , y1 )，に分けて，あるグループのクエリと他方のグループに所属す

B(x2 , y2 ) が存在する場合，ユークリッド距離 d(A,B) は以下のる複数のターゲットとの関係性を探索する二色逆最近傍探索式で表される．

(Bichromatic-RkNN) に分類される．本研究では，二色逆最近
傍探索について考える．
最近傍探索を行う場合，問合せ元のクエリからすべてのターd(A.B) =√(x1 − x2 )2 + (y1 − y2 )2(1)

ゲットまでの距離情報を取得した上で，クエリから近い順番にユークリッド距離は，経路上に存在する障害物の有無に関わターゲットを求めると，計算量が膨大になり，探索時間は長大

らず，二つのオブジェクト間の最短距離を求めることができる．

化する．そこで，空間ネットワーク上で最近傍となるオブジェ

2. 3 ネットワーク距離

クトの位置情報を追加した領域（以下，影響圏）を設定する．

空間ネットワークに地理情報を適用する場合，二つのオブユーザは，自身の現在位置がどのターゲットの影響圏かを確認

ジェクト間で山や川といった自然物，および家やビルといったすることで最近傍となるターゲットを探索でき，最近傍探索に人工物を考慮する必要がある．このような空間ネットワーク上かかる時間を短縮できる．

で，ユーザがあるオブジェクトから別のオブジェクトへ移動す

A1

A6

A6
A2

A4

A2

B5

A1

A4
B4

B6

B1
B2

B3
A3

A5

A5
A3

図 1 最近傍探索 (k = 2)

A1

図3

A6

二色逆最近傍探索（グループ A がクエリの場合）

B5

A1

A6
A2

A2

A4

A4
B4

B6

B3
A3

B1
B2

A5

A5
A3

図 2 逆最近傍探索

図 4 二色逆最近傍探索（グループ B がクエリの場合）

る場合，二つのオブジェクト間の移動距離は，ユークリッド距管理されるようになり，人とのかかわりを間接的に意識する環

離よりも長くなる．このように，地理情報を考慮した二つのオ境が一般的になった．このため，多くのユーザは，自身の存在

ブジェクト間の距離をネットワーク距離と呼ぶ．本研究では，が他者および他のグループからどのように意識されているかに

空間ネットワーク上の地理情報を反映した重み付きグラフを用ついての情報を取得したい要求が高まっている．

いて，二つのオブジェクト間の距離をネットワーク距離で表す．

3. 探 索 手 法

3. 3 単色逆最近傍探索
単色逆最近傍 (Monochromatic-RkNN) 探索は，3. 2 節で述
べた一般的な逆最近傍探索である．クエリとターゲットは，同

3. 1 最近傍探索

じ種類のオブジェクトにおいて一対一で互いの位置関係を探索

最近傍 (k-Nearest Neighbor，以下，kNN) 探索は，空間ネッ

するため，クエリの探索対象は，空間ネットワーク上に存在す

トワーク上に複数のオブジェクトが存在する場合，問合せ元とるすべてのターゲットとなる．このとき，単色逆最近傍探索でなるクエリから距離が近い順番に k 個 (k >= 1) のターゲットを探索する方法である．図 1 は，k が 2 の場合における最近傍探は，クエリを自身の最近傍とするターゲットを探索する必要が索の例である．クエリが A4 の場合の探索結果は，A4 からの距
離が短い順番に，A2 と A6 となる．

ある．

3. 4 二色逆最近傍探索
二色逆最近傍 (Bichromatic-RkNN，以下，BRkNN) 探索は，

3. 2 逆最近傍探索

二つのグループで構成されたオブジェクト間で逆最近傍を探索

逆最近傍 (Reverse kNN，以下，RkNN ) 探索は，クエリにする．例えば，二つのコンビニエンスストアのグループ A，B

対して複数のターゲットがどのような位置関係であるかを算出がある営業エリア内でそれぞれ複数の店舗を営業している場合，して，最近傍探索と逆方向の関係を求める方法である．例えば，

グループ A に所属するオブジェクトがグループ B に所属する

図 2 において，A4 の R1NN は A6 である．

オブジェクトを対象にした RkNN の関係を図 3 に示す．また，

逆最近傍探索では，クエリから 1NN の関係にあるターゲッ

逆に，グループ B に所属するオブジェクトがグループ A に所

トは，必ずしもクエリから逆に 1NN の関係になるとは限らな属するオブジェクトを対象にした RkNN の関係を図 4 に示す．

い．例えば，図 2 の場合，A2 の R1NN となるオブジェクトの

このような関係は，あるコンビニエンスストアのグループがうち一つは A4 となる一方で，A2 の最近傍は A1 となるため，

次にオープンする新規店舗の場所を決める場合に利用できる．

A2 は A4 の R1NN ではない．

しかし，二色逆最近傍探索に関する研究は，グループ間でオブ

これまでの研究では，クエリの探索対象は，自身の現在位置

ジェクトの探索方法が複雑であるため，進んでいない．本研究からどのくらいの距離でどの程度存在するかが重要とされてきでは，グループ間でオブジェクト逆最近傍探索を行うため，二た．しかし近年，多くのユーザが携帯端末で自分の位置情報を

色逆最近傍探索を検討する．

母点

図5

ボロノイ図
図7

s1

p1
s4

s2

s6

s3

5. 影 響 圏
5. 1 概要

逆最近傍探索では，すべてのオブジェクトに対してクエリか

s7
s10
s8
p2

ユークリッド距離を用いた逆最近傍探索における影響圏

s5

s11

s9
s12

らの距離がもっとも近いターゲットを探索するため，オブジェ

p3
s13

s14

s15

クト数の増加に応じて計算量は膨大になる．そこで，オブジェ
クトに対して逆最近傍探索を行うため，オブジェクトの影響圏を作成する．影響圏は，空間ネットワーク上に存在するすべてのオブジェクトに対して，あるオブジェクトが自身を最近傍と図 6 ネットワークボロノイ図

判断する領域である．クエリは，自身の位置情報を含む影響圏をもつターゲットを最近傍として決定する．影響圏を作成す

4. ネットワークボロノイ図ることで，クエリの最近傍となるターゲットの探索時間を短縮する．

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

Network Voronoi Diagram (以下，ネットワークボロノイ図)
は，空間ネットワーク上でネットワーク距離を用いたボロノ

ターゲット t に対して，ユークリッド距離で逆最近傍探索の影響圏を作成する例を図 7 に示す．図 7 では，影響圏を作成するターゲット t とオブジェクト pi (i = 1, · · · , 7) が空間ネット
ワークに存在し，t の影響圏を作成する．クエリ q に対して最近傍探索を行う場合，t の影響圏の内部に q が存在するため，

q からもっとも近いオブジェクトは t であることが分かる．
影響圏は，ターゲット t と空間ネットワークに存在する各オ
ブジェクト間の垂直二等分線で作成される．図 7 の場合，影響
圏は t と pi (i = 1, · · · , 4) による垂直二等分線によって作成される．

5. 2 影響圏の作成手法
逆最近傍探索における単純な影響圏作成手法（以下，単純手

イ図である．図 6 に，二次元の空間ネットワーク上でネット

法）では，空間ネットワークに存在するすべてのオブジェクト

ワーク距離を用いたネットワークボロノイ図の例を示す．p1 ，は，クエリとの垂直二等分線を引く．図 7 のように，ターゲッ

p2 および p3 は母点となるオブジェクトであり，s1 , s2 , ..., s15
は母点以外のオブジェクトである．空間ネットワーク上におけるオブジェクト間の経路上に存在する四角形は，母点が構成

ト t とオブジェクト pi (i = 1, · · · , 7) が空間ネットワークに存在する場合，すべてのオブジェクト pi に対してターゲット t
からの距離が近い順に垂直二等分線を引き，影響圏を作成する．

する領域の境界を表す．図 6 の場合，オブジェクト s1 , s2 , s3

単純手法では，クエリは影響圏の作成に影響を与えないオブ

は，母点 p1 を自身の最近傍とするオブジェクトとなる．同様

ジェクトに対しても垂直二等分線を引くため，効率が悪い．図に，オブジェクト s7 , s8 , s9 , s12 , s13 は母点 p2 ，オブジェクト

s4 , s5 , s6 , s10 , s11 , s14 , s15 は母点 p3 を自身の最近傍とするオブジェクトとなる．

7 の場合，単純手法では，クエリと p5 , p6 , および p7 との間に引く 3 本の垂直二等分線は，影響圏の作成に影響しない．

6. 関 連 研 究
6. 1 逆最近傍探索
逆最近傍探索に関する研究はいくつか行われている．Taniar
らは，空間ネットワークにおける最近傍探索の重要性について述べている [1]．Taniar によると，最近傍探索手法は 4 種類に分類できる．一つ目は空間を考慮した手法であり，オブジェ
クト間のユークリッド距離の他に，道路ネットワークと呼ばれるオブジェクト間の道路距離をもとに構成されたネットワー
ク上で最近傍探索を行う．近年では，ユークリッド距離とネッ
トワーク距離を組み合わせた手法 [2], [3] や，Network Voronoi

図 8 2*farthest vertex 法

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

Cheema らは，空間ネットワーク内で逆最近傍探索の計算量を削減する手法として，Swift And Cheap (SAC) 法を提案している [10]．SAC 法では，複数のオブジェクトが移動している
状況で逆最近傍探索のクエリを発行する場合，オブジェクトごとに長方形領域を設定する．クエリとターゲットで長方形領域を比較することで，タイムスタンプごとにすべてのオブジェク
トの位置を正確に求めるコストを削減する．
本研究では，複数のクエリが複数のターゲットに対して同時にクエリを発行する状況で，オブジェクト間の関係性を考慮して逆最近傍探索を行う．このとき，各オブジェクトの正確な位置を含む長方形領域を設定することで，新規オブジェクトが移動してもオブジェクト間の関係性が変化しない移動可能領域を算出する．

6. 2 影響圏を考慮した領域作成手法
現在，ユークリッド距離を用いた逆最近傍探索で影響圏を考慮した領域作成手法として，多くの手法が提案されている．以
下の項で，逆最近傍探索における効率的な領域作成手法として，

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 は影響圏の外部に存在するため，逆最近傍探索における領域作成に影響しないことが分7. 提 案 手 法
7. 1 概要

空間ネットワークにおいて，ネットワーク距離を用いて探索
数 k が複数となる場合に拡張した BRkNN 手法を提案する．
提案手法では，ターゲットを母点としたネットワークボロノイ
図を作成した後，各ターゲットの kNN を三つのステップに分けて探索し，条件を満たさないターゲット候補の除外 (以下，刈取り) を行う．ターゲットからの距離がクエリよりも短いオ
ブジェクトを k 個検出した場合，このターゲットはクエリのBRkNN ではないため，除外する．すべてのターゲットに対す
図9

初期領域を使用した影響圏探索手法

る探索が終了した段階で除外されなかったターゲットは，クエ
リの BRkNN となる．

7. 2 想 定 環 境
本手法を提案するにあたり，想定する環境を箇条書きで示す．

•

空間ネットワークは二次元で構成する．

•

オブジェクト間の距離はネットワーク距離で表す．

•k>= 1 とする．

•

オブジェクトのグループは二種類とする．

7. 3 探 索 手 順k>= 2 の場合に対応した提案手法におけるターゲットの探索手順を説明する．提案手法のアルゴリズムは，k = 1 の場合のみに対応した既存手法 [13] のアルゴリズムを拡張して作成した．
初めに，ターゲットを母点としたネットワークボロノイ図を作成する．次に，すべてのターゲットに対して三つのステップ
図 10

初期領域を使用しない影響圏探索手法

で刈取りを行いながら探索して，クエリの BRkNN となるター
ゲットを求める．

かる．

6. 2. 3 初期領域を使用しない影響圏探索手法
初期領域を使用しない影響圏探索手法 [11] では，ターゲットとオブジェクト間の垂直二等分線同士の交点が作成される場合，ターゲットから垂直二等分線に対して垂直な直線を引き，刈取り領域を作成する．次に，ターゲットと垂直二等分線の交点を中心として，ターゲットから交点までの距離を半径とする影響
圏の円を作成する．刈取り領域の内部かつ影響圏の外部に存在するオブジェクトは逆最近傍探索の領域生成に関係せず，刈取り領域の外部の点，および刈取り領域の内部かつ影響圏の内部の点にのみ垂直二等分線を引く．
刈取り領域と影響圏を用いて，逆最近傍探索の領域を作成する例を図 10 に示す．図 10 では，ターゲット t とオブジェクト

pi (i = 1, · · · , 7) が空間ネットワーク内に存在し，オブジェク
ト p1 および p2 に対して垂直二等分線をそれぞれ引く．破線は，逆最近傍探索の領域を作成するオブジェクトから垂直二等分線
に対する垂線であり，塗りつぶされた領域は刈取り領域である．
刈取り領域の内部に存在するオブジェクト p4 は影響圏の内部に存在するため，クエリ q とオブジェクト p4 との間に垂直二等分線を引く．次に，刈取り領域の外部に存在するオブジェク
トのうち，ターゲットからの距離がもっとも近いオブジェクト

p3 に対して垂直二等分線を引き，刈取り領域と影響圏の範囲をそれぞれ更新する．

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 (pk , Q) なら，SQ

を空にし，ステップ 2 へ．
C1（ 4 ） DN (pk , si) < DN (pk , Q) の場合，k の値を 1 減ら
す．この後，k = 0 であれば，pk を候補から除外して，次のs1候補となるターゲットの処理に移行する．また，k > 0 またはQ

s2

DN (pk , si ) >= DN (pk , Q) であれば，2. へ．
いた刈取り

s6

s7
s10

ステップ 2 では，クエリと pk とのユークリッド距離を半径，s8

pk を中心とする円を作成し，円内の領域と重なるすべてのボ

s11

s9

p2

ロノイ領域に対して，ステップ 1 と同じ処理を行う．ステップ
エリと pk とのユークリッド距離よりも短くなる可能性が高い．

s4

s3

7. 3. 3 ステップ 2 : ユークリッド距離を半径とする円を用

2 で探索するオブジェクトと pk とのユークリッド距離は，ク

s5

p1

s12

p3
s13

s14

s15

図 11 DE(p1 , Q) を半径とする円 C1 を作成した様子

これは，二つのオブジェクト間のユークリッド距離が短い場合
C2

は，ネットワーク距離も短くなる可能性が高いためである．ス

C1

テップ 2 を実行することで，ステップ 3 で候補となるオブジェ
クトをすべて探索する場合に比べて探索時間を短縮できる．以s1

下に，詳細な手順を示す．

s5

p1
Q

s2

（ 1 ） e = DE(pk , Q) を求め，中心 pk ，半径 e の円を作成

s4

s6

s3

する．
（ 2 ） 円内の領域と重なるボロノイ領域 V P (p) をすべて求

s7
s10

める．

s8

（ 3 ） 各 V P (p) について DE(pk , p) を求め，DE(pk , p) と

p2

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 の各要素を昇順でソートする．

図 12

s11

s9
s12

p3
s13

s14

s15

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 は以下のように表さ

図 13

探索数と実行時間

れる．

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) であ

図 14

ターゲット数と実行時間

るため，ステップ 1 の 4. よりステップ 1 の 2. へ．
（ 7 ） DE(p1 , s5 ) > DN (p1 , Q) であるため，ステップ 1 のの実行時間を算出した．

3. より，ステップ 2 へ．また，ステップ 2 の 5. より， P Q

図 13 より，探索数が増加すると，距離の比較対象となるオブが空であるため，ステップ 3 へ．ステップ 3 の 4. より，探索ジェクト数が増加するため，提案手法と線形探索のどちらでも処理を終了し，p1 は Q の BRkNN となる．

実行時間は長大化する．特に，ターゲット数が同数の場合，ほぼすべての場合において，提案手法による探索の実行時間は線

8. 評

価

形探索に比べて短いことが分かる．また，ターゲット数が 50，

8. 1 概要

探索数 k が 9 または 10 の場合，線形探索の実行時間は提案手

提案手法の有用性を検証するため，計算機上でシミュレー法に比べて短い．探索数とターゲット数がどちらも多い場合，ション評価を行った．比較する手法として，あるターゲットに対距離の比較対象となるオブジェクト数が多くなり，かつクエリ

して，クエリとの距離と，クエリと同じグループに所属するクと同じグループのオブジェクト数が少なくなるため，提案手法

エリ以外のオブジェクトとの距離の二つを順番に比較し，ターと線形探索で探索するオブジェクト数はほぼ同じになる．提案

ゲットとクエリとの距離より短いオブジェクトが k 個見つかっ手法では，距離を比較すべきオブジェクトか否かの判別処理をた時点で次のターゲットの探索に移行する線形探索を用いる．

行うため，この処理時間の影響で，線形探索に比べて実行時間

提案手法および線形探索のプログラムは，C 言語で作成した．

が長くなると考えられる．

8. 2 評 価 環 境
計算機シミュレーションによる評価環境を以下に示す．

8. 4 ターゲット数の影響
ターゲット数を変化させた場合の探索時間の変化を図 14 に•空間内のオブジェクト数は，100 とする．

示す．横軸はターゲット数，縦軸は二色逆最近傍探索の実行時•

空間の大きさは，縦 1000，横 1000 の二次元領域とする．

間である．ターゲット数は，10 から 90 まで 10 刻みとし，探•探索の実行時間を 110 回計測し，実行時間の上位 5 回

索数は 1 個と 5 個の場合で，提案手法と線形探索それぞれにと下位 5 回を除く計 100 回の平均を用いて評価する．

8. 3 探索数の影響

ついて BRkNN の実行時間を算出した．
図 14 より，探索数 k が同じ場合，提案手法の実行時間は線形

探索数 k の値を変化させた場合の探索時間の変化を図 13 に探索に比べて短いことが分かる．また，探索数が 5，ターゲッ

示す．横軸は探索数 k ，縦軸は二色逆最近傍探索の実行時間でト数が 60 以上の場合，提案手法と線形探索の実行時間の差はある．比較評価として，提案手法と線形探索の二つを用いる．

ほとんど無い．一方で，探索数が 5 でターゲット数が 70 以上

探索数は，1 から 10 とし，ターゲットの数は 10 個と 50 個のの場合，ターゲット数の増加にともない，実行時間は短くなる．

二つの場合で，提案手法と線形探索それぞれについて，BRkNN

これは，ターゲット数がクエリと同じグループのオブジェクト

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

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

文

献[1] D. Taniar, and W. Rahayu, “A Taxonomy for Nearest
Neighbour Queries in Spatial Databases,” Journal of Computer 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, “Spatial 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 Publishers, 2011.
[6] Y. Chen, and J. M. Patel, “Eﬃcient Evaluation of AllNearest-Neighbor Queries,” Proceedings of IEEE 23rd International Conference on Data Engineering (ICDE 2007),
pp.1056-1065, 2007.
[7] J. Zhang, N. Mamoulis, D. Papadias, and Y. Tao, “AllNearest-Neighbors Queries in Spatial Databases,” Proceedings of 16th International Conference on Scientiﬁc and Statistical 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 Computer 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 Euclidean Space and in Spatial Networks,” The VLDB Journal, 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 locationaldata,” 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 andComputation: Practice and Experience, vol.26, pp.11421156, 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.