DEIM Forum 2017 E3-5

不確実データベースにおける MaxRS クエリ処理手法
中山 侑紀†

天方 大地†

原隆浩†† 大阪大学大学院情報科学研究科マルチメディア工学専攻 〒 565–0871 大阪府吹田市山田丘 1–5
E-mail: †{nakayama.yuki,amagata.daichi,hara}@ist.osaka-u.ac.jp
あらまし

本稿では，不確実データベースにおける MaxRS（Maximizing Range Sum）クエリについて考える．不確実データベースは，複数のインスタンスおよびその生起確率の組で表現されるデータで構成されるデータベースである．MaxRS クエリは，スコアをもつ空間データの集合およびユーザが指定した長方形の大きさが与えられたとき，その長方形に包含されるデータのスコアの和が最大となる長方形の位置を検索するものである．これまでに，不確実データベースを想定した MaxRS 検索に関する研究が存在しないため，本稿で，Probabilistic MaxRS（P-MaxRS）ク
エリを新たに定義する．P-MaxRS クエリは，MaxRS となる確率が 0 でない位置およびその確率の組の集合を取得するものであるが，既存研究の MaxRS クエリ処理アルゴリズムを単純に適用した場合，非効率的である．そこで，

P-MaxRS クエリの解となる位置を限定し，その後，限定した位置が MaxRS となる確率を効率的に計算するアルゴリ
ズムを提案する．実データおよび人工データを用いた実験により，提案アルゴリズムの有効性を示す．
キーワード

不確実データベース，空間データ，MaxRS クエリ

1. は じ め に
近年，GPS などの位置情報取得技術の発展や位置情報サー
ビスの普及に伴い，空間データベースへの関心が高まっている．
また，スマートフォンなどのモバイル端末が普及したことにより，空間データが爆発的に増加しているため，大量のデータか
ら重要な情報を検索するクエリ処理に関する研究が盛んに行われている [10]，[12]．空間データベースに対するクエリ処理の 1

図 1 MaxRS クエリの一例

つとして，MaxRS（Maximizing Range Sum）クエリが提案されている [5]．MaxRS クエリは，スコアを持つ空間データのる範囲内に存在する観光地の評価点の和が最も高い場所を検索

集合およびユーザが指定した長方形の大きさが与えられたとき，できる．つまり，このシステムでは，観光客が最も満足できる

その長方形に包含されるデータのスコアの和が最大となる長方と考えられる場所を提示できる．

形の位置を検索するものである．以下の例を用いて，MaxRS
クエリを説明する．

例 1.2 以外のアプリケーション例として，センサネットワークがある．例えば，道路上に設置したセンサにより，交通量を測

例 1.1．図 1 は MaxRS クエリの一例を表している．最も外側

定している場合を考える．MaxRS クエリは，最も交通量が多の太線の長方形は空間データの存在範囲を表しており，点線おい位置を検索できる．この検索結果は，交通量が多い場所にレ

よび実線の長方形，および黒点は，それぞれユーザが指定したストラン等を出店したい企業にとって有用である．

大きさの長方形，および空間データを表している．簡単化のため，空間データのスコアは全て 1 とする．この例では，黒点を最も多く包含している実線の長方形の位置が MaxRS クエリの解（の一つ）である．

上記のように有用なアプリケーションが存在するため，これまでに MaxRS クエリに関する研究は数多く行われている [2]，[3]，[5]，[6]，[8]，[11]，[14]．しかし，これらの研究は，データの不確実性を考慮していない．例えば，例 1.2 の場合，観光

MaxRS クエリは，長方形の大きさを指定するだけで重要な位地は様々な人により評価されており，それらを同時に考えたと置を検索できるため，多くのアプリケーションにとって有用でき，ある観光地の評価点は，複数の値とその値の生起確率の組ある．以下に，MaxRS クエリのアプリケーション例を示す．

で表現される．そこで，本稿では不確実性が存在するデータに

例 1.2．観光客にとって魅力的な観光場所を提示するシステム

対する MaxRS（Probabilistic MaxRS，P-MaxRS）クエリのを考える．空間データとして，観光地の位置およびその観光地

効率的な処理方法を提案する．P-MaxRS クエリは，MaxRS との評価点で構成されるデータを想定する．一般的に，観光客がなる確率が 0 でない位置とその確率の組を検索するクエリであある一定期間（例えば，一日）に移動できる範囲は限られている．単純には，空間データの取り得る値の組合せ全てに対して，

るため，その範囲を MaxRS クエリで指定する長方形の大きさ

既存の MaxRS クエリ処理アルゴリズムを適用することによっとする．このとき，MaxRS クエリにより，観光客が移動できて P-MaxRS クエリを処理できる．しかし，空間データの取り得る値の組合せの数は，データ数に対して指数的に増加するたで定義する．

め，データ数が多い場合，非効率的である．そこで，P-MaxRS
クエリの解となる位置（データ集合）を限定した後，限定したPr[M axRSq = Rq ] =Pr(W) · δ(M axRSqW = Rq )W∈Ω

データ集合が MaxRS となる確率を効率的に計算するアルゴリ
ズムを提案する．また，実データおよび人工データを用いた実∑δ(M axRSqW = Rq ) =験から，提案アルゴリズムがクエリ処理時間を削減できていることを確認した．

f W (R) =以下では，2. で P-MaxRS クエリを定義し，提案アルゴリズ

 1,

if Rq = argmax f W (R) 0,otherwise∑

ルゴリズムについて述べる．4. で実データおよび人工データを関連研究について述べ，最後に，6. で本稿をまとめる．

2. 事 前 準 備

ui,j .sui ∈R,ui,j ∈W

ムで利用する既存アルゴリズムを説明する．また，3. で提案ア用いた実験により，提案アルゴリズムの性能を評価する．5. で

R∈Rq

(1)
f W (R) は，ある Possible World W における，オブジェクト
集合 R 内の全てのオブジェクトのスコアの和である．よって，δ(M axRSqW = Rq ) は，W において，オブジェクト集
合 Rq が MaxRS であるなら 1，MaxRS でないなら 0 とな

本稿では，不確実データベースにおける MaxRS クエリについて考える．まず，本稿で考えるデータモデルおよび問題を詳細に定義し，その後，提案アルゴリズムで利用する既存研究のアルゴリズムを紹介する．

る関数である．ここで，本稿では，任意の Possible WorldW において，MaxRS となるオブジェクト集合と同じスコアをもつオブジェクト集合は存在しないものとする．よって，∑
q
Rq ∈Rq Pr[M axRSq = R ] = 1 である．しかし，上記のようなオブジェクト集合が存在する場合でも，同じスコアであるオ

2. 1 データモデル
不確実データベース．不確実データベース U は，n 個の不確
実オブジェクトで構成される（U = {u1 , u2 , · · · , un }）．以降，
曖昧性が生じない限り，不確実オブジェクトを単にオブジェク
トと記述する．オブジェクト ui は，m 個のインスタンスで構

ブジェクト集合のうちのいずれか 1 つのみを MaxRS とするこ∑とで， Rq ∈Rq Pr[M axRSq = Rq ] = 1 は成り立つ．

MaxRS 確率を用いて，以下に Probabilistic MaxRS（PMaxRS）クエリを定義する．

成される（ui = {ui,1 , ui,2 , · · · , ui,m }）．また，インスタンス

定義 2.1（P-MaxRS クエリ）．不確実データベース U および

ui,j は，二次元の位置，スコア，および生起確率で構成される

長方形の大きさを指定したクエリ q が与えられる．このとき，P-（ui,j = ⟨loc, s, p⟩）．本稿では，オブジェクトの位置は決定的であMaxRS クエリの解は，Rq 中で MaxRS 確率が 0 でないオブジェると想定する（ui .loc = ui,1 .loc = ui,2 .loc = · · · = ui,m .loc）．

クト集合およびその MaxRS 確率の組 ⟨R, Pr[M axRSq = R]⟩

また，オブジェクト ui のインスタンス中に同じスコアは存在の集合 AN S である．

しない（ui,1 .s =| ui,2 .s =| ··· =| ui,m .s）．さらに，インスタン

ユーザの要求によっては，P-MaxRS クエリの解を取得した

スのスコアは自然数（ui,j .s ∈ N）とし，各オブジェクトを構∑成するインスタンスの生起確率の和は 1（ ui,j ∈ui ui,j .p = 1）

後，MaxRS 確率が閾値以上であるオブジェクト集合や MaxRSと想定する．このような不確実データベースの定義は，属性レもできる．

確率が上位 k 番目までのオブジェクト集合のみを取得すること

ベルモデルと呼ばれ，不確実データベースの分野では一般的で

2. 3 既存研究のアルゴリズム

ある [1]．また，本稿では，全ての属性値が決定的であるオブ

文献 [9] において，RI（Rectangle Intersection）クエリを効

ジェクトで構成されるデータベースを，単にデータベースと記率的に処理するアルゴリズムが提案されている．RI クエリは，述し，不確実データベースと区別する．

大きさが等しい長方形集合が与えられたとき，最も多くの長方

Possible World．ある Possible World W は，不確実データ

形が重なっている領域を求めるものである．また，オブジェク

ベース U 中の各オブジェクトからインスタンスを 1 つずつ選ト集合を長方形集合に変換し，長方形の重みを考慮した RI ク

択したものである．つまり，ある Possible World W ∈ Ω は，

エリ処理を行うことで，MaxRS クエリの解を求められる [5]．

W = {u1,α , u2,β , · · · , un,γ } である．ここで，Ω は，U から生

図 2 より，RI クエリの解である影の付いた領域（図 2(b)）が成される全ての Possible World の集合である．また，W の生∏起確率を Pr(W) = ui,j ∈W ui,j .p とする．以上の定義より，∑|Ω| = mn ，および W∈Ω Pr(W) = 1 である．

MaxRS クエリの解の長方形の中心（× 印）を包含しているこ

2. 2 問 題 定 義とが分かる．また，文献 [1] において，不確実データベースにおける ALL SUM クエリを効率的に処理するアルゴリズムが提案されている．ALL SUM クエリは，スコアをもつ不確実オブ

MaxRS 確率．不確実データベース U ，および長方形の大き

ジェクト集合が与えられたとき，取り得る全てのスコアの和おさを指定したクエリ q が与えられる．クエリ q で指定された大よびその確率の組を求めるクエリである．提案アルゴリズムにきさの長方形に包含される（ただし，長方形の回転は考慮しな

おいて，文献 [9] で提案されているアルゴリズム（以降，PS），い）オブジェクトの集合を Rq をする．考えられる全ての Rq

および文献 [1] で提案されているアルゴリズム（DP PSUM2）の集合を R としたとき，R ∈ R の MaxRS 確率を以下の式を利用するため，本節でこれらのアルゴリズムについて簡単に

q

q

q

説明する．

表 1 不確実オブジェクト集合 U の例

‫ݑ‬ଵ

‫ݑ‬ଶ

ܾ

‫ݑ‬ଷ

‫ݑ‬ସ
ܽ

‫଺ݑ‬

‫ݑ‬ହ

(a) MaxRS クエリ

$

‫ݑ‬ଵ
‫ݑ‬ଶ

‫ݑ‬ସ

& '
%
‫ݑ‬ଷ (

‫଺ݑ‬
)

‫ݑ‬ହ

オブジェクト インスタンス（⟨ スコア, 確率 ⟩）

* +

V‫ظ‬L

(b) RI クエリ

図 2 MaxRS クエリの変換例

ͳPS．PS は，平面走査法を基にしたアルゴリズムである．まず，͵

オブジェクト集合と長方形の大きさが与えられたとき，与えられたオブジェクト集合中の各オブジェクトの位置を中心とする与えられた大きさの長方形集合に変換する．また，その長方形集合を RI クエリの入力とする．その後，水平線を y 座標の最ʹu1

u1,1 = ⟨1, 0.5⟩, u1,2 = ⟨2, 0.5⟩

u2

u2,1 = ⟨2, 0.3⟩, u2,2 = ⟨3, 0.7⟩

u3

u3,1 = ⟨1, 0.2⟩, u3,2 = ⟨2, 0.8⟩

ͳ ሺ ‫ݑ‬ଵ ሻʹ ሺ ‫ݑ‬ଵ ǡ ‫ݑ‬ଶ ሻ

Ͳ

ͲǤͳͷ

Ͳ

ͲǤ͵ͷ

Ͳ

Ͳ

ͲǤͷ
ͲǤͷ

Ͷ

Ͳ

͸

Ͳ

ͷ

͹

Ͳ
Ͳ

͵ ሺ ‫ݑ‬ଵ ǡ ‫ݑ‬ଶ ǡ ‫ݑ‬ଷ ሻͲǤͷͲ図 3 DP PSUM2 の計算例

Ͳ
Ͳ

Ͳ

ͲǤͲ͵

ͲǤʹʹ

ͲǤͶ͹

ͲǤʹͺ

小値から最大値まで走査することにより，RI クエリを処理する．具体的には，（i）水平線が長方形の下辺に達したとき，およ

例 2.1．表 1 は不確実オブジェクト集合 U を表している．まび（ii）水平線が長方形の上辺に達したときにそれぞれ以下のた，図 3 は，DP PSUM2 により U に対する ALL SUM クエ

操作を行う．
（i）下辺から構成されるインターバルを 2 分木にリを処理する計算過程（ps(s, i)）を表している．まず，u1 の挿入し，2 分木内のインターバルのスコアを更新する．さらに，みを考慮した不確実オブジェクト集合 U = {u1 } の取り得

これまでのスコアの最大値を超える場合，そのインターバルをるスコアおよび確率を計算する．その結果が ps(1, 1) = 0.5

途中解とする．
（ii）上辺から構成されるインターバルを 2 分木

お よ び ps(2, 1) = 0.5 で あ る ．次 に ，不 確 実 オ ブ ジェク トから削除する．

集合に u2 を追加する（U = {u1 , u2 }）．このとき，ps(·, 1)

図 2(b) を用いて，インターバルのスコアの更新を説明する．

を 利 用 し て ，ps(·, 2) を 計 算 す る ．具 体 的 に は ，u2 を 追

図 2(b) は，水平線が u4 を変換した長方形の下辺に達したとき

加 す る こ と に よって ，ps(3, 2) = ps(1, 1) · u2,1 .p = 0.15，を示している．全ての長方形の重みを 1 としたとき，インターps(4, 2) = ps(1, 1) · u2,2 .p + ps(2, 1) · u2,1 .p = 0.5，ま た

バル AB，BC，CD，DE，EF，FG，および GH のスコアはそps(5, 2) = ps(2, 1) · u2,2 .p = 0.35 となる．u3 を追加したとれぞれ 1，2，1，2，3，2，および 1 である．よって，インターきも同様の計算を行うことにより，図 3 の結果が得られる．こバル EF を途中解とする．以上より，水平線が y 座標の最大値のとき，ALL SUM クエリの解は，s および ps(s, 3) の組のリに達したとき，最大のスコアを持つインターバルが解と分かる．

ストである．

PS は，オブジェクト数が n のとき，2 分木に対してインター

DP PSUM2 は，1 つのオブジェクトを追加したとき，取りバルの挿入および削除をそれぞれ n 回行う．そのため，計算量

得るスコアの数（Ns ）× インスタンス数（m）回の計算を行う．

は O(n log n) である．

また，n 個のオブジェクトを逐次的に追加するため，計算量は

DP PSUM2．DP PSUM2 は動的計画法を基にしたアルゴリ

O(Ns · m · n) である．

ズムである．不確実オブジェクト集合 U = {u1 , u2 , · · · , un } が与えられたとする．このとき，逐次的にオブジェクトを追加し，そのスコアの和および確率を計算する．以下に，この計算方法

本章では，P-MaxRS クエリを効率的に処理するアルゴリズ
ムについて説明する．まず，提案アルゴリズムの概要についてを示す．

{
ps(s, 1) =ps(s, i) =3. 提案アルゴリズム

m∑u1,j .p, if ∃j such that u1,j .s = s0, otherwise

述べ，その後，提案アルゴリズムを詳細に説明する．

(2)

3. 1 提案アルゴリズムの概要
まず，（I）P-MaxRS クエリの解となるオブジェクト集合を取得する．2. 2 節で定義した Rq は MaxRS 確率が 0 であるオブ

ps(s − ui,k .s, i − 1) · ui,k .p, if i > 1

(3)

k=1

ジェクト集合を含んでいる．そこで，PS および PS を拡張したアルゴリズムにより，MaxRS 確率が 0 であるオブジェクト

ps(s, i) は，i 個のオブジェクト u1 , u2 , · · · , ui で構成されるオ集合を除外する．ここで除外されずに残ったオブジェクト集合

ブジェクト集合のスコアの和が s である確率を表す．まず，式の集合を AR とする．図 4 は，AR の例である．長方形およ(2) により，オブジェクト u1 のみを考慮したときの取り得るス

び黒点は，それぞれ AR 中のオブジェクト集合 Ri および Ri

コアおよび確率を計算する．その後，式 (3) により，ps(·, i − 1)

中のオブジェクトを表しており，白点は AR に含まれないオブを参照して，オブジェクト ui を追加したときのスコアの和とジェクトを表している．その後，（II）AR 中の各オブジェクト

確率 ps(·, i) を計算する．表 1 および図 3 を用いて，具体的に集合の MaxRS 確率を計算する．一般的には，図 4 のように，説明する．

1 つのオブジェクトが複数のオブジェクト集合に含まれる場合

ܴଵ

ܴଷ

ܴଶ

ܴହ

ܴସ

ܴ଺

図 4 オブジェクト集合の集合 AR の例

ܴଵ

‫ݑ‬ଵ

‫ݑ‬ସ

‫ݑ‬ଷ

ܴଶ

‫ݑ‬ଶ

Output: オブジェクト集合の集合 AR
Omin = ∅，Omax = ∅，I = ∅2

for ∀ui ∈ U do3

I ←PS(Omin )5

lbscore = I.score

6for ∀ui ∈ U do

7

Omax = Omax ∪ ⟨ui .loc, ui .M axScore⟩8

AR ← PSextend (Omax , lbscore )9return AR

‫ݑ‬ସ

ܴଷ

(b) 共有オブジェクトが存在する
場合オブジェクト集合 U ′ の例

表 2 図 5(b) 中のオブジェクト
オブジェクト インスタンス（⟨ スコア, 確率 ⟩）Omin = Omin ∪ ⟨ui .loc, ui .M inScore⟩

4

‫ݑ‬ଶ

ܴଶ

い場合

Algorithm 1: CalculateAR(U , q)

1

‫ݑ‬ଵ

‫ݑ‬ଷ

(a) 共有オブジェクトが存在しな

図5

Input: 不確実データ集合 U ，長方形の大きさ q = (a, b)ܴଵu1⟨5, 1.0⟩

u2⟨9, 0.5⟩, ⟨4, 0.5⟩

u3⟨6, 1.0⟩

u4⟨7, 1.0⟩

表3

図 5(b) の DP PSUM2 の結果

オブジェクト集合 取り得るスコアと確率（⟨ スコア, 確率 ⟩）R1⟨14, 0.5⟩, ⟨9, 0.5⟩

R2⟨15, 0.5⟩, ⟨10, 0.5⟩

R3⟨16, 0.5⟩, ⟨11, 0.5⟩

アルゴリズム（PSextend ）を実行する（8 行）．PSextend は，PSがある．この場合，DP PSUM2 をそのまま適用できない．そと同様に平面走査を実行し，途中解のスコアが lbscore 以上でこで，提案アルゴリズムでは，AR をオブジェクトを共有してあるオブジェクト集合を全て取得する．ただし，R ⊂ R′ であいるオブジェクト集合同士の集合（独立集合）に分割し，各オるオブジェクト集合 R は AR に含めない．そのため，PSextend

ブジェクト集合が属する独立集合中での MaxRS 確率（ローカでは，AR 中に R ⊂ R′ となるオブジェクト集合 R′ が存在し

ル MaxRS 確率）を計算する．その後，ローカル MaxRS 確率

ない場合に，オブジェクト集合 R を AR に含める．

を基に，各オブジェクト集合のスコアを比較することにより，

3. 3 各オブジェクト集合の MaxRS 確率の計算

各オブジェクト集合の MaxRS 確率を計算する．単純には，独式 (1) より，単純には，オブジェクト集合 U ′ = ∪R（R ∈ AR）

立集合に含まれるオブジェクトから生成される Possible World（図 4 の黒点）から生成される Possible World 毎に PS アルゴ

毎に MaxRS となるオブジェクト集合を計算することでローカリズムを実行することで，各オブジェクト集合の MaxRS 確率

ル MaxRS 確率を求められる．しかし，Possible World の数は，を計算できる．しかし，Possible World の数は m|U | である

独立集合に含まれる全てのオブジェクトの数に対して指数的にため，|U ′ | が大きい場合，非効率的である．そこで，オブジェ増加する．そこで，部分的に DP PSUM2 を適用することによクト集合が取り得るスコアの和（以降，オブジェクト集合のス

り，計算しなければならない Possible World の数を削減する．

コア）を比較することにより，各オブジェクト集合の MaxRS′

3. 2 解となるオブジェクト集合の取得確率を計算する．複数のオブジェクト集合に共通しているオブ

アルゴリズム 1 に，P-MaxRS クエリの解となるオブジェク

ジェクト（共有オブジェクト）が存在しない場合（図 5(a)），

ト集合を取得するアルゴリズムを示す．まず，オブジェクト集

AR 中の各オブジェクト集合 R に DP PSUM2 を適用し，R合が MaxRS となる場合に必要なスコア（lbscore ）を取得する．

のスコアとその確率を計算する．その後，それらのスコアを比

そのために，各オブジェクトのスコアを取り得るスコアの最小較することにより，R の MaxRS 確率を計算できる．一方，共値（M inScore）として，PS を実行する（1–4 行）．各オブジェ

有オブジェクトが存在する場合（図 5(b)），上述した方法ではクトのスコアは 1 つ（最小値）であるため，PS をそのまま実MaxRS 確率を計算できない．

行できる．また，PS の解のスコアを lbscore とする（5 行）．こ図 5(b)，表 2，および表 3 により，これを説明する．図 5(b)のとき，lbscore は，PS の解であるオブジェクト集合のスコア

中のオブジェクトは，表 2 中のインスタンスで構成されているの和の最小値である．そのため，オブジェクト集合のスコアのものとする．簡単化のため，共有オブジェクト u2 以外のオブ和の最大値が lbscore より小さい場合，そのオブジェクト集合のジェクトのインスタンスは 1 つとする．このとき，各オブジェ

MaxRS 確率は 0 である．よって，オブジェクト集合のスコア

クト集合に DP PSUM2 を適用した結果が表 3 である．表 3 よの和の最大値が lbscore 以上となるオブジェクト集合の集合 ARり，オブジェクト集合のスコアを比較したとき，全てのオブジェを取得する．まず，各オブジェクトのスコアを取り得るスコア

クト集合は MaxRS である場合が存在する．例えば，R1 のスの最大値（M axScore）とする（6–7 行）．その後，PS の拡張

コアが 14，R2 のスコアが 10，R3 のスコアが 11 のとき，R1ܴଵ

Algorithm 2: DivideARintoIP(AR)Input: ARܴଷ

Output: 独立集合の集合 IP
1IP1 ← R1 ∈ AR

2

IP ← IP1

3

for ∀Ri ∈ AR \ R1 do

4

newF lag = 1

5

for ∀IP ∈ IP do

6

if ∃Rj ∈ IP |Ri ∩ Rj =| ∅ then7

IP = IP ∪ Ri

8

newF lag = 0

9

break

10

if newF lag = 1 then11

IPnew ← Ri

12

IP = IP ∪ IPnew

13

return IPܴଶ

図6確率と定義する．R のスコア S(R) が s である場合の R のLMaxRS 確率は以下の式で求められる．
Pr[LM axRSq = R, S(R) = s] =∑Pr(W) · δ(LM axRSqW = R) · δ(S(R) = s)W∈ΩIPδ(LM axRSqW = R) ={が MaxRS である．しかし，R1 のスコアが 14 である Possible

独立集合の一例

δ(S(R) = s) =World を考えた場合，u1 ，u2 ，u3 ，および u4 のスコアは，そ 1,

if R = argmax f W (R′ )otherwise0,R′ ∈IP1,

if s = f W (R)0,otherwise

れぞれ 5，9，6，および 7 である．そのため，スコアが 16 であ

ここで，ΩIP は，オブジェクト集合 UIP = ∪R（R ∈ IP ）（図る R3 が MaxRS となり，R1 は MaxRS でない．

6 の全ての黒点）から生成される全ての Possible World の集合

このように，全ての Possible World の集合 Ω 中に存在しないインスタンスの組合せを考えているため，各オブジェクト
集合に DP PSUM2 を適用し，スコアを比較する方法は，オブジェクト集合の MaxRS 確率を正確に計算できない．そのため，である．
オブジェクト集合の MaxRS 確率．オブジェクト集合のロー
カル MaxRS 確率を用いて，オブジェクト集合 Ri ∈ IPa のMaxRS 確率を以下の式で計算する．

共有オブジェクトが存在する場合，Possible World を考慮しなければならない．そこで，提案アルゴリズムでは，Possible

World の基となるオブジェクト数を削減する．まず，独立集合を定義する．

Pr[M axRSq = Ri ] =∑{Pr[LM axRSq = Ri , S(Ri ) = s]s>=lbscore∏

定義 3.1（独立集合）．AR 中の全てのオブジェクト集合を重複しないように以下の 2 つの条件を満たす集合 IP1 , IP2 , · · · へ

(

∑

∑

Pr[LM axRSq = Rj , S(Rj ) = s′ ])}IPb ∈IP\IPa Rj ∈IPb s′ <s

分割する．

∀Ri ∈ IPa , ∃Rj ∈ IPa \ Ri , Ri ∩ Rj =| ∅∀Ri ∈ IPa , ∀IPb ∈ IP \ IPa , ∀Rj ∈ IPb , Ri ∩ Rj = ∅ここで，IP = {IP1 , IP2 , · · · } である．このようなオブジェク
ト集合の集合 IPa を独立集合と呼ぶ．

(4)
∑

∑
Rj ∈IPbs′ <s Pr[LM axRSq= Rj , S(Rj ) = s′ ] は，Ri ∈/IPb である独立集合 IPb 中の任意のオブジェクト集合がスコア
s′ (< s) でローカル MaxRS となる確率の和を意味している．
オブジェクト集合のローカル MaxRS 確率の計算．単純には，
オブジェクト集合 UIP から生成される全ての Possible World

アルゴリズム 2 に，AR を独立集合に分割するアルゴリズム

において，独立集合 IP 内で MaxRS となるオブジェクト集合を示す．まず，初期化処理として，オブジェクト集合 1 つで構を計算することで，オブジェクト集合のローカル MaxRS 確

成される IP1 を IP に挿入する（1–2 行）．次に，各オブジェ

率を求められる．しかし，Possible World の数は，|UIP | にクト集合 Ri を，共有オブジェクトをもつオブジェクト集合 Rj

対して，指数的に増加する．そこで，提案アルゴリズムでは，が属する独立集合に追加する（6–9 行）．Ri が既に存在する独DP PSUM2 を部分的に利用することで，Possible World の基

立集合に挿入されなかった場合，自身を新たな独立集合とし，となるオブジェクト数を削減する．UIP 中で DP PSUM2 を適

IP に追加する（10–12 行）．図 4 の AR は，アルゴリズム 2

用できるオブジェクトは，（i）1 つのオブジェクト集合のみに含により，IP1 = {R1 , R2 , R3 }，IP2 = {R4 }，IP3 = {R5 , R6 }まれるオブジェクト（図 6 の影付き部の黒点），および（ii）全に分割される．次に，オブジェクト集合のローカル MaxRS 確てのオブジェクト集合で共有されているオブジェクト（図 6 の率について考える．

斜線部の黒点）である．
（i）および（ii）に DP PSUM2 を適用

ローカル MaxRS 確率．オブジェクト集合 R が属する独立集合

し，IP 中のオブジェクト集合のローカル MaxRS 確率を計算

IP において MaxRS となる確率をローカル MaxRS（LMaxRS）

するアルゴリズムをアルゴリズム 3 に示す．ここで，アルゴリ

Algorithm 3: CalculateLocalMaxRS(IP )Algorithm 4: Proposed algorithm

Input: 独立集合 IP

Input: 不確実データ集合 U ，長方形の大きさ q = (a, b)

1

Uα = {u|∃Ri , Rj ∈ IP, u ∈ (Ri ∩ Rj )}2for ∀R ∈ IP do

Output: P-MaxRS の解 AN S
1

CalculateAR(U, q)

3UR̂ = R \ (R ∩ Uα )2

DivideARintoIP(AR)4ΨR̂ = DP PSUM2 (UR̂ )3

for ∀IP ∈ IP do

56Ψβ = DP PSUM2 (Uβ )7Uγ = Uα \ Uβ8

4

Uβ = {u|u ∈ ∩R∈IP R}

5for ∀W ∈ ΩUγ do// ΩUγ は Uγ から生成される全てのPossible World の集合
9

if |IP | = 1 then // IP 中の唯一のオブジェクト集合を Ri
とする．

6
7

ΨLM.
← DP PSUM2 (Ri )Rielse if |IP | = 2 then
共通オブジェクト集合および各オブジェクト集合のみに含まれるオブジェクトの集合の 3 つの部分に DP PSUM2

for ∀R ∈ IP do

10

スコア f W (R) を計算を適用し，オブジェクト集合のローカル MaxRS 確率を計

11

ΨW
R =∅

算

12

for ∀ψR̂ ∈ ΨR̂ do⟨f W (R) + ψR̂ .score, ψR̂ .prob⟩ を ΨW
R に挿入

13

14

for ∀Ri ∈ IP doprob = Pr[LM axRSq = Ri , S(R) = ψi .score|W]

16

9

10

for ∀ψi ∈ ΨW
Ri do

15

8

if prob =| 0 thenCalculateLocalMaxRS(IP )for ∀Ri ∈ AR do

11

式 (4) により，Pr[M axRSq = Ri ] を計算

12

AN S = AN S ∪ ⟨Ri , Pr[M axRSq = Ri ]⟩（式 (5) により計算）
17

else

13

return AN S

for ∀ψβ ∈ Ψβ do

18⟨ψi .score+ψβ .score, prob·ψβ .prob·Pr(W)⟩19

を ΨLM.
に挿入
R
i

Pr[LM axRSq = Ri , S(R) = ψi .score|W] =∏∑ψi .prob(ψj .prob)(5)

Rj ∈IP \Ri ψj ∈ΨW ,ψj .score<ψi .scoreRj

ズム 3 において，全ての Ψ はスコアと確率のタプルから構成される．
まず，共有オブジェクトの集合 Uα を計算する（1 行）．次に，DP PSUM2 を用いて，1 つのオブジェクト集合 R のみに含まれるオブジェクトの集合 UR̂ の取り得るスコアの和とその確率 ΨR̂ を計算する（2–4 行）．次に，IP 中の全てのオブジェ
クト集合の共通要素であるオブジェクトの集合 Uβ を計算する（5 行）．そして，DP PSUM2 を用いて，Uβ の取り得るスコアの和とその確率 Ψβ を計算する（6 行）．その後，スコアを計算していないオブジェクト集合 Uγ から生成される各 Possible

World W について考える．まず，W において，各オブジェク
ト集合が Uβ 以外のオブジェクト集合で取り得るスコアの和と確率をスコア f W (R) および先に計算した ΨR̂ により計算する（9–13 行）．タプル ⟨score, prob⟩ を ΨW
R に挿入とは，既に同じスコアをもつタプルが ΨW
R に存在する場合は，そのタプルの確率を ψ.prob = ψ.prob + prob とし，同じスコアをもつタプルが存在しない場合は，⟨score, prob⟩ をそのまま ΨW
R に挿入する操作である（以降，“Ψ に挿入” はこの操作を示す）．次に，

ΨW
Ri を利用し，W において，オブジェクト集合 Ri がスコア
ψi .score のときに独立集合 IP 中で MaxRS である確率を以下の式により計算する（16 行）．

この確率が 0 でない場合，W において，オブジェクト集合 Ri は

ψi であるときに MaxRS である．よって，Uβ および Possible
World の確率 Pr(W) を考慮して計算したローカル MaxRS スコ
アおよびローカル MaxRS 確率を ΨLM.
．
Ri に挿入する（18–19 行）
このアルゴリズムで計算した ΨLM.
Ri は，Ri がローカル MaxRSとなるスコアおよびその確率のタプルのリストである．各オ
ブジェクト集合毎の UR̂ および Uβ が取り得るスコアの和を先に計算しても，ΩIP 中の Possible World を過不足なく計算できる．そのため，アルゴリズム 3 により，オブジェクト集合のローカル MaxRS 確率を正確に計算できる．また，単純手法において Possible World の基となるオブジェクトの数は |UIP | であるのに対して，提案アルゴリズムでは，Possible World の基となるオブジェクトの数を |Uγ | に削減している．
以上より，アルゴリズム 1，アルゴリズム 2，アルゴリズム 3，
および式 (4) を用いて，各オブジェクト集合の MaxRS 確率を正確に計算できる．P-MaxRS クエリを処理する提案アルゴリズ
ムをアルゴリズム 4 に示す．まず，アルゴリズム 1 およびアルゴリズム 2 により，AR を計算し，AR を独立集合に分割する（1–2 行）．次に，独立集合毎に，各オブジェクト集合のローカル

MaxRS 確率を計算する（3–9 行）．このとき，独立集合中のオ
ブジェクト集合の数が 1 または 2 の場合，Possible World 毎の計算をせずに各オブジェクト集合のローカル MaxRS 確率を計算できる（4–7 行）．それ以外の場合は，アルゴリズム 3 により，各オブジェクト集合のローカル MaxRS 確率を計算する（8–9行）．最後に，式 (4) により，各オブジェクト集合 Ri の MaxRS

確率 Pr[M axRSq = Ri ] を計算し，⟨Ri , Pr[M axRSq = Ri ]⟩本章では，評価実験の結果を紹介する．提案アルゴリズム

ฎ⌮᫬㛫 [sec]4. 評 価 実 験の有効性を確認するため，CalculateLocalMaxRS 内で，Pos-

BASELINE+

PROPOSEDBASELINE㻝㻜㻜㻜㻜ฎ⌮᫬㛫 [sec]BASELINE㻝㻜㻜㻜を AN S に挿入する（10–12 行）．

㻝㻜㻜
㻝㻜
㻝

BASELINE+

PROPOSED

㻝㻜㻜㻜
㻝㻜㻜

㻝㻜
㻝

㻡

㻢

㻣

㻤

㻥

㻝㻜

㻡 㻢 㻣 㻤 㻥 㻝㻜 㻝㻝 㻝㻞 㻝㻟 㻝㻠 㻝㻡ṇ᪉ᙧࡢ୍㎶ࡢ㛗ࡉ [ൈ ͳͲଷ ]sible World の基となるオブジェクト集合を UIP としたもの

ṇ᪉ᙧࡢ୍㎶ࡢ㛗ࡉ [ൈ ͳͲସ ](a) CAR の結果（BASELINE），および Uα としたもの（BASELINE+）と比較した．評価結果を示すグラフ中では，提案アルゴリズムを(b) NE の結果

図 7 実データにおける正方形の一辺の長さ L の影響

PROPOSED と表す．全てのアルゴリズムは C++で実装されており，実験は 3.00GHz Xeon E5-2687W v4 および 512GB
定

NE（注 2））および人工データを用いて行った．CAR および NE
は，それぞれカリフォルニア州およびアメリカ北東部の道路

㻝㻜㻜
㻝㻜
㻝

乱数により生成した．また，実データおよび人工データにおいて，インスタンスのスコアおよびその生起確率は，以下の方法
で人工的に付与した．各オブジェクト毎に，[1,200] の一様分布から決定した整数値を平均とし，分散を 20 とした正規分布を与え，この正規分布に従い [1,200] の整数値となるスコアをもつインスタンスを 2 つ生成した．また，各オブジェクト中のイ
ンスタンスの生起確率の合計が 1 となるように，インスタンスの生起確率をランダムに与えた．
評価環境．本実験では，クエリで指定する長方形を一辺の長さが L である正方形とした．実データによる実験では，各オブジェクトのインスタンスをランダムに変化させたデータセット

50 組を作成し，人工データによる実験では，各オブジェクトの位置およびインスタンスをランダムに変化させたデータセット

50 組を作成した．このように作成したデータセット 50 組に対し，クエリを発行してから P-MaxRS クエリの解 AN S を求めるまでの処理時間の平均値を調べた．評価結果を示すグラフ中において欠けている点は，開始後 30 時間経過しても終了しなかったものである．

4. 2 評 価 結 果
実データによる実験結果．各実データに対して，それぞれ正方形の一辺の長さ L を変化させたときの結果を図 7 に示す．この図において，図 7(a) および図 7(b) はそれぞれ CAR およびNE の結果を表す．
図 7 より，全ての手法において，L が大きくなると処理時間が大きくなることが分かる．L が大きくなると，1 つの正方形

㻢

㻣

㻤

㻥

㻝㻜

ṇ᪉ᙧࡢ୍㎶ࡢ㛗ࡉ [ൈ ͳͲହ](a) 正方形の一辺の長さ L の影響

BASELINE+

PROPOSED

㻠

㻢

㻝㻜㻜㻜
㻝㻜㻜
㻝㻜
㻟

㻡

࢜ࣈࢪ࢙ࢡࢺᩘ [ൈ ͳͲ଺ ]㻣(b) オブジェクト数 |U | の影響

図 8 人工データの評価結果

位置を取得し，x 軸方向および y 軸方向の値を，それぞれ [0,は，各オブジェクトの位置を，[0, 1000000000]2 の範囲の一様

BASELINE
㻝㻜㻜㻜㻜

㻝
㻡

実データを用いた実験では，実データから各オブジェクトの1000000000] の範囲で正規化した．人工データを用いた実験でPROPOSED

㻝㻜㻜㻜

ネットワークから取得した空間データであり，実データのオ
ブジェクト数は，それぞれ 2,249,727 および 1,524,453 である．

BASELINE+ฎ⌮᫬㛫 [sec]4. 1 設データセット．本実験は，2 種類の実データ（CAR（注 1） および

BASELINE㻝㻜㻜㻜㻜ฎ⌮᫬㛫 [sec]RAM で構成される PC 上で行った．

中のオブジェクトの数が大きくなり，1 つの独立集合に含まれるオブジェクトの数が大きくなる傾向がある．そのため，ロー
カル MaxRS 確率の計算時に生成する Possible World の数が大きくなる．PROPOSED は，ローカル MaxRS 確率の計算時に生成する Possible World の数を削減しているため，L が大きい場合でも他の手法と比べて処理時間が小さい．
人工データによる実験結果．人工データによる実験結果を図 8に示す．この図において，図 8(a) は，正方形の一辺の長さ Lを変化させた時の結果，図 8(b) は，オブジェクト数 |U | を変化させた時の結果を示す．|U | = 5000000 および L = 800000
をデフォルト値とし，正方形の一辺の長さの影響を調べる時は，

L を [500000, 1000000] の範囲で変化させ，オブジェクト数の影響を調べる時は，|U | を [3000000, 7000000] の範囲で変化させた．
図 7(a) の結果より，L が大きい時，PROPOSED の処理時間が最も小さいことが分かる．BASELINE および BASELINE+
は L = 1000000 の時の結果がないが，少なくとも 30 時間経過しているため，BASELINE および BASELINE ＋の処理時間
は PROPOSED よりも大きい．これは，L が大きい時，1 つの独立集合に含まれるオブジェクト数が大きいためである．提案手法では，限られた部分に存在するオブジェクトのみから

Possible World を生成しているため，この影響が小さい．しかし，L = 1000000 の時，PROPOSED の処理時間も大きくなる．これは，Uγ に属するオブジェクト数が大きくなる場合，提案手法の処理時間が増加することを示している．
図 7(b) の結果は，オブジェクト数が大きい時，PROPOSEDの処理時間が最も小さいことを示している．一方，BASELINE
および BASELINE+の処理時間は非常に大きい．これより，提（注 1）：http://chorochronos.datastories.org/?q=node/59（注 2）：http://www.dis.uniroma1.it/challenge9/download.shtml

案手法は計算すべき Possible World の数を削減し，効率的に各オブジェクト集合の MaxRS 確率を計算できていることが分

実データおよび人工データを用いた実験から，提案アルゴリズ

かる．

ムの有効性を確認した．

5. 関 連 研 究

提案アルゴリズムは，Possible World の基となるオブジェク
ト数に対して，指数的に計算時間が増加する．そこで，さらにMaxRS クエリ．MaxRS クエリを効率的に処理する様々なア

処理時間を削減するために，精度を保証した近似解を計算する

ルゴリズムが提案されている [2]，[3]，[5]，[6]，[8]，[9]，[11]，[14]．

アルゴリズムを設計することを検討している．

文献 [9] では，全てのデータをメモリ上に配置できる環境において，文献 [5]，[6] では，全てのデータをメモリ上に配置できない環境において，処理時間の削減を目的とした厳密な解を計算

謝辞本 研 究 の 一 部 は ，文 部 科 学 省 研 究 費 補 助 金・基 盤 研 究するアルゴリズムが提案されている．文献 [14] では，インデッ(A)(JP26240013) および JST 国際科学技術共同研究推進事

クスを構築することにより，さらに処理時間を削減するアルゴ

業（戦略的国際共同研究プログラム）の研究助成によるものでリズムが提案されている．また，文献 [11] では，MaxRS クエある．ここに記して謝意を表す．

リの解のスコアの精度を保証した近似解を計算するアルゴリズ
ムが提案されている．文献 [3] では，MaxRS クエリで与えられる長方形の回転を考慮したアルゴリズムが提案されている．
文献 [2] では，ストリーム環境において MaxRS を効率的にモニタリングするアルゴリズムが提案されている．文献 [8] では，分散環境であるアドホックネットワークにおいて，トラヒックの削減を目的としたアルゴリズムが提案されている．これらの研究は，データのスコアが確定的であるデータベースを想定しており，これらの研究で提案されているアルゴリズムを不確実
データベースに適用することは困難である．
不確実データベース．不確実データベースの分野において，様々なクエリおよびそれを効率的に処理するアルゴリズムが提案されている [4]，[7]，[13]．文献 [7] および文献 [4] は，それぞれ不確
実データベースにおける Top-k クエリおよび k 最近傍クエリを考えている．文献 [7] は，Top-k となる確率が閾値以上であるデータを取得するクエリを効率的に処理するアルゴリズムを提案している．また，文献 [4] は，k 個のデータ集合がクエリ
ポイントの k 最近傍となる確率が閾値以上であるデータ集合の集合を取得するクエリを効率的に処理するアルゴリズムを提案している．これら以外にも，Top-k 検索および k 最近傍検索に関して，様々なセマンティックのクエリが研究されている．また，文献 [13] では，Bichromatic Reverse Nearest Neighbor の数の期待値が高い k 個のデータポイントを取得するクエリを効率的に処理するアルゴリズムを提案している．これらの研究は，本稿で想定する問題とは異なるため，これらの研究で提案されているアルゴリズムを P-MaxRS クエリ処理に適用することはできない．

6. お わ り に
本稿では，不確実データベースにおける MaxRS クエリを効率的に処理するアルゴリズムを提案した．実環境では，センサ
データなどの値が確率的に表されるデータが存在するため，不確実データベースにおけるクエリ処理アルゴリズムを考えることは有用である．提案アルゴリズムは，平面走査法を用いて，P-MaxRS クエリの解となるオブジェクト集合を限定し，部分的に DP PSUM2 を利用して，計算しなければならない Possible

World の数を削減することにより，処理時間を削減する．また，

文

献[1] Akbarinia, R., Valduriez, P. and Verger, G.: Eﬃcient Evaluation of SUM Queries over Probabilistic Data, TKDE,
Vol. 25, No. 4, pp. 764–775 (2013).
[2] Amagata, D. and Hara, T.: Monitoring MaxRS in Spatial
Data Streams, EDBT, pp. 317–328 (2016).
[3] Chen, Z., Liu, Y., Wong, R. C.-W., Xiong, J., Cheng, X.
and Chen, P.: Rotating MaxRS queries, Information Sciences, Vol. 305, pp. 110–129 (2015).
[4] Cheng, R., Chen, L., Chen, J. and Xie, X.: Evaluating
Probability Threshold k-Nearest-Neighbor Queries over Uncertain Data, EDBT, pp. 672–683 (2009).
[5] Choi, D.-W., Chung, C.-W. and Tao, Y.: A Scalable Algorithm for Maximizing Range Sum in Spatial Databases,
PVLDB, Vol. 5, No. 11, pp. 1088–1099 (2012).
[6] Choi, D.-W., Chung, C.-W. and Tao, Y.: Maximizing Range
Sum in External Memory, ACM TODS, Vol. 39, No. 3, p. 21(2014).
[7] Hua, M., Pei, J., Zhang, W. and Lin, X.: Ranking Queries
on Uncertain Data: A Probabilistic Threshold Approach,
SIGMOD, pp. 673–686 (2008).
[8] Nakayama, Y., Amagata, D. and Hara, T.: An Eﬃcient
Method for Identifying MaxRS Location in Mobile Ad Hoc
Networks, DEXA, pp. 37–51 (2016).
[9] Nandy, S. C. and Bhattacharya, B. B.: A Unified Algorithm for Finding Maximum and Minimum Object Enclosing Rectangles and Cuboids, Computers & Mathematics
with Applications, Vol. 29, No. 8, pp. 45–61 (1995).
[10] Qi, J., Zhang, R., Kulik, L., Lin, D. and Xue, Y.: The MinDist Location Selection Query, ICDE, pp. 366–377 (2012).
[11] Tao, Y., Hu, X., Choi, D.-W. and Chung, C.-W.: Approximate MaxRS in Spatial Databases, PVLDB, Vol. 6, No. 13,
pp. 1546–1557 (2013).
[12] Wong, R. C.-W., Özsu, M. T., Yu, P. S., Fu, A. W.-C.
and Liu, L.: Eﬃcient Method for Maximizing Bichromatic
Reverse Nearest Neighbor, PVLDB, Vol. 2, No. 1, pp. 1126–
1137 (2009).
[13] Zhan, L., Zhang, Y., Zhang, W. and Lin, X.: Finding Top
k Most Influential Spatial Facilities over Uncertain Objects,
TKDE, Vol. 27, No. 12, pp. 3289–3303 (2015).
[14] Zhou, X., Wang, W. and Xu, J.: General Purpose IndexBased Method for Eﬃcient MaxRS Query, DEXA, pp. 20–
36 (2016).