DEIM Forum 2017 G1-2

時空間データ分析のための差分ヒストグラム構築手法
趙セイ†

石川 佳治†

杉浦 健人†

脇田佑希子†† 名古屋大学大学院情報科学研究科 〒 464–8603 愛知県名古屋市千種区不老町
E-mail: †{zhao,sugiura}@db.ss.is.nagoya-u.ac.jp, ††ishikawa@is.nagoya-u.ac.jp, †††wackie@nagoya-u.jp
あらまし

科学分野における観測データやシミュレーション結果のデータの分析においては，同じ対象物に関する複数のデータを比較して，どのような差異があるかを検出したいという要求がしばしば見られる．例えば，ある空間領域に対する異なる時間における観測データやシミュレーションデータの比較，異なったパラメータによる空間的なシ
ミュレーションの比較などが考えられる．そこで本論文では，時空間的な観測データやシミュレーションデータなどを蓄積する時空間データウェアハウスにおける差分演算について提案する．それに加えて，差分を分析するための要件を整理し，その実装に関するアプローチを示す．
キーワード

データウェアハウス, 差分演算, 時空間データベース, シミュレーションデータ

1. は じ め にさまざまな分野においてビッグデータが注目されている今日
では，データベースにおける大量のデータの高度な分析処理を行うためのデータアナリティクス（data analytics）について，研究が盛んに行われている [6]．時空間データベース（spatio-

temporal database）においても，行動データ，移動軌跡デー

図1

差分演算のイメージ

タ，科学分野のデータなどのさまざまな領域において大規模な時空間データの分析が求められている．我々の研究グルー
プでは，特に時空間的な大規模シミュレーションの結果を蓄積し，対話的な分析を可能とするための時空間データウェア
ハウス（spatio-temporal data warehouse）に関する研究を進めており，その考え方をシミュレーションデータウェアハウス
（simulation data warehouse）と呼んでいる．特に津波・震災
シミュレーションデータの分析に関して研究を進めている [5]．
本稿では，時空間データウェアハウスにおける基本的な分析
要求の一つとして考えられる差分（もしくは差異）（diﬀerence）に着目する．時空間的なデータでは，特に時間に関する変化をどのように検出するかが重要な要求の一つとして考えられる．
また，パラメータが異なるシミュレーションデータや観測状況が異なる観測データが与えられたとき，異なるデータ間にどのような違いがあるかを検出することも求められる．例として，
以下のような避難シミュレーションデータの分析の例を考える．

は，二つの時区間 T1 , T2 における集計値をそのまま用いるか，総数で割った正規化された集計値を用いるかという選択肢があり，これは対象データや応用に依存する．ここでは簡単のため，ユーザが前者の方式を選んだものとして進める．
図 1 の右図は，時区間 T1 , T2 における入力データに対し，T1の集計結果に対する T2 の集計結果の差分を近似的に表したイメージを示している．ヒートマップ表現を用い，赤い色が強い
領域ほど T2 の時区間において T1 時区間と比較して集計値が大きいことを示す．一方，青い色が強いほど，逆の傾向があることを意味する．また，大まかな差分の傾向を表現するため，差分のトレンドが同じようなセルが隣接する場合にはそれらをまとめて一つのセルとして表現する．ここでは四分木（quadtree）のような空間分割を想定し，セルの辺の大きさが 2 のべき乗の長さになるようにしている．
このような出力結果の提示により，ユーザは，二つの時区間対象となるシミュレーションの空間領域において，時における変化を容易に把握することができる．しかし，差分演

区間 T1 = [8 : 00, 9 : 00] および T2 = [20 : 00, 21 : 00]

算としてどのようなものを考えればいいかは明らかではなく，における避難者の数の分布について，顕著な差異があ

対象のデータの性質や応用目的に依存してさまざまなものが考る領域を報告せよ．

えられる．一方で，大量のデータの中から顕著な変化を検出す
ることは容易ではなく，最新のデータベースシステム技術を効

この分析例では，時間帯 T1 と T2 において，避難者の数の分
布にどのような違いがあるかを求めている．
差分演算のイメージを図 1 に示す．例えば，左図と中図はそ
れぞれ時区間 T1 と T2 における集計結果を表している．各セルの濃淡は集計値の大きさ（その時間帯にそのセルに属する移動ユーザの人数）に対応している．なお，実際の利用において果的に活用した効率的なアルゴリズムの開発が必要となる．このような背景に基づき，本研究では:（ 1 ） 時空間データウェアハウスから差分・差異を検出するための汎用的な演算を定義して，ヒストグラムに基づく手段を用いて時空間データの顕著な差分を検出することを目指す．

（ 2 ） 大規模配列データの管理および問合せに特化した配列

す．また，空間領域がセル b にカバーされる差分配列の要素の指向型 DBMS である SciDB [2], [3], [4] を活用して差分演算を集合を実装する．SciDB に時空間シミュレーションデータが分析用に蓄積されているものとし，必要に応じてそれに対して差分演算が適用されるというのが想定シナリオである．

cov(b) = {e | e ∈ Adiﬀ ∧ contain(area(b), area(e))} (1)で示す．ただし，area は XY 平面における領域を返す関数で，本論文の構成は以下の通りである．2 章では差分演算の定義

contain は前者が後者を包含するときに真になる関数である．

について述べる．3 章は提案手法の説明である．節 3. 1 と節 3. 2

最良な差分ヒストグラムは誤差が最小なもので定義される．

は差分ヒストグラムの構築手法について述べ，節 3. 3 では，大

ここでは，二乗誤差を用いて誤差の尺度とする．すなわち，差規模なデータを取り扱うとき計算コストを減らすため，要約情分ヒストグラム H の誤差を報に基づく差分誤差の推定手法を提案する．4 章で SciDB における実装について述べて，5 章は評価実験である．最後に，6Error(H) =∑ ∑(e(v) − δ(ta , tb ))2(2)b∈H e∈cov(b)章でまとめと今後の課題について議論する．

で定義する．つまり，差分配列 Adiﬀ における要素の属性値

2. 問題の定義

e(v) と差分ヒストグラムのセルの値の差の二乗である．

ここでは，本研究で想定する典型的な時空間データについて

3. 提 案 手 法

述べる．2 次元のユークリッド空間を細粒度で何分割するかというパラメータ n が与えられるものとし，空間を 2n × 2n 分

最良な多次元ヒストグラムを構築する問題は NP 困難と証明割する．一方で，時間の間隔 τ が与えられており，時間は等間されている [1]．それで，本研究では，近似的な方針として，四隔の時区間に分けられる．

分木の構造に基づき，ボトムアップに統合を行い差分ヒストグ［定義 1］ 時空間配列 Ast (X, Y, T, Atr) は次元と属性で構成

ラムを構築する．主に二つの手法が考えられる．まず，貪欲的される．次元については，具体的には，2n × 2n 空間グリッな統合手法は，ボトムアップに誤差が最小となる統合可能なセドにマッピングされる空間次元 X, Y ，と等間隔の時区間でル群を見つけて，ヒストグラムのサイズの制約（B ）を満たす

構 成される時間次元 T と なる．なお，X = {1, 2, ..., 2 },まで統合を行うものである．一方で，閾値に基づく統合手法は，

Y = {1, 2, ..., 2n }, T = {1, 2, ..., T /τ }. 時空間配列において，

閾値を用いて，誤差が閾値以下のセルを統合し，ボトムアップ

各要素 ei,j,k （xi ∈ X, yj ∈ Y , tk ∈ T ）は次元によって位置にヒストグラムを構築する手法である．両者について，以下で付けられて，属性の集合 Atr を有する．本研究では，属性につ具体的に説明する．

n

いては，数値データの集計値を対象として想定する．例えば，

なお，差分ヒストグラムの構築においては，差分配列を直接避難のシミュレーションデータにおいて，属性は避難の人数のの入力とする考え方をとることもできるが，大規模なデータを集計値となる．

取り扱う際には，最初に配列データをスキャンして差分配列を具体的な集計値の計算方法としては，まず，その時区間およ計算するコストが高いという問題がある．一方で，必ずしも差び対象セルに関するレコード数をカウントすることが考えられ分配列を先に計算せずに，差分ヒストグラムを構築しながら必る．選択肢として，分布のパターンを見たいなら，全レコード

要となる差分を計算する手法も考える．よって本研究では，統数で割った頻度分布とすることも考えられる．また，他の種類

計情報に基づく手法も提案する．グリッド構造に対して事前にの対象データに関しては，AVG や MAX などの集計関数の利集計・計算した統計情報にアクセスして差分誤差の区間を推定

用も考えられる．

することによって，条件を満たさないセルをフィルタリングす

時空間配列データを分析するため，時間に関する変化を検出ることができる．これによって，必要のない配列データをチェッすることや空間上の大幅な分布を把握することは，重要な要求

クするコストを減らして，差分を計算しなくても条件を満たすの一つとして考えられる．そこで本研究では，差分・差異を検セルを見つけることもできる．

出するための汎用的な演算を定義する．

3. 1 ヒストグラム構築手法 1：貪欲的な統合手法［定義 2］ 与 え ら れ た 時 空 間 配 列 Ast に お い て ，時 区 間

ヒストグラム構築手法 1 として，貪欲な統合手法に基づくアta と tb に お け る 属 性 v の 集 計 結 果 の 差 分 を 差 分 配 列

ルゴリズムについて考える．基本方針は，隣接したセルをボト

Adiﬀ (X, Y, δ(ta , tb )) と呼ぶ．差分の定義（差，比例など）はムアップに統合していくというものである．このアルゴリズム

分析のシナリオによって変わっているが，ここでは，時区間 ta

をアルゴリズム 1 に示す．

と tb の集計値の差を考慮する．

入力の Adiﬀ は，対象となる差分配列である．入力のもう一［定義 3］ 差 分 演 算 Dif f (Ast , ta , tb , v, B) は ，差 分 配 列

つは，差分ヒストグラムのセルの総数 B である．B = 1 の場

Adiﬀ (X, Y, δ(ta , tb )) を最良な差分ヒストグラム H で表現する．

合は一切分割しないため処理は自明であるので，このアルゴリ

差分ヒストグラム H = {b1 , b2 , ..., bB } は対象となる空間領域

ズムでは B > 1 の場合を扱う．また，差分ヒストグラムでは(X, Y ) をカバーする B 個のセルで構成される．各セル b ∈ H

視覚的な提示を想定しているため，結果となる差分ヒストグラ

は {x, y, δ(ta , tb )} （x ∈ X, y ∈ Y ）を含め，空間セル (x, y)

ムの細粒度のセルの大きさは元の配列データの細粒度の大きさにおける時区間 ta と tb の属性の集計値の差分 δ(ta , tb ) を表である必要はない．そこで，ユーザあるいはシステム側で対応

逆に，m が小さいほど結果の精度は高くなるが，あまりに小さ

Algorithm 1: Greedy-based Merging
Input: Adiﬀ : 差分配列, B：差分ヒストグラムのセルの総数, m：

グラムに残る可能性がある．

初期レイヤのパラメータ

一方，処理の過程で何度も呼ばれる誤差の計算については，

Result: H: 差分ヒストグラムのセル集合
1

H ← merge(Adiﬀ , 2m , 2m ) ;2

curL ← 0 ;3while H.size > B do// 差分ヒストグラムを初期化

実際のデータの集計が必要となることから，大規模なデータに// ヒストグラムのレイヤを初期化

対して支配的な影響を与えうる．これについては，後述のようにデータベースシステムの集計機能を活用することや，計算済

4

if curL == copt .layer then5

CL ← merge(H, 2, 2) ;6

curL + +;// 候補セルリスト生成

end

8

copt ← get min error(CL)9H ← copt ∪ (H \ children(copt )) ;CL ← CL \ copt ;

11

end

12

return H;

みの値を保持するなどの工夫で実際のコストを削減できる．具
体的には，各レイヤで計算済みの統計情報を保持して，上のレイヤのセルの誤差を計算する際に再利用される．つまり，以下

7

10

い設定では，視覚的には有効ではない小さいセルが差分ヒスト;// 誤差が最小なセルを抽出// ヒストグラムを更新// 候補リストを更新の式を用いて，一個下のレイヤにおけるセルの統計情報（例，
平均値など）を用いて，新たに生成される候補セルの誤差を計
算できる．

n=

∑

nj

(4)

j

∑
するパラメータ m を与えることを想定する．差分配列が 2 次m=

元の空間上の N × N のグリッドとしたとき，差分ヒストグラ
ムの細粒度をN× 2Nm
2m

E(c) =の空間グリッドと設定する．

mj nj
n

∑
j

本手法では，まずパラメータ m を用いて，2m × 2m のグ
リッドサイズで差分ヒストグラムを初期化し，すべてのグリッ

j

Ej +

(5)

∑

m2j nj − m2 n(6)jm，n，E(c) はそれぞれセル c の平均値，含まれている細粒

ドセルを一時的な結果 H に入れる (1 行目)．例えば，図 2(a)度のセルの数と誤差である．mj ，nj ，Ej はそれぞれセル c のでは，m が 0 と指定された場合の初期ヒストグラムは入力とす

子のセル cj (j = 1, 2, . . .) の平均値，含まれている細粒度のセる差分配列のデータと一致する．対応するレイヤ curL を 0 に

ルの数と誤差である．例えば，図 2(c) では，左下のセルの誤差する．1 行目と 5 行目に出てくる merge() 関数では，指定さを計算するとき，カバーしている領域に存在する細粒度のセルでセルを統をチェックする必要はなく，一個下のレイヤ（図 2(b)）で保持合して，対応する配列の属性を集計する．ここでは，差分値をされた統計情報と式 (4),(5),(6) を用いて計算できる．これらに表す属性の平均をとって集計を行う．merge() 関数によって，よって，ボトムアップに誤差を計算しながら統合を行うことがヒストグラムの初期化と候補セルリストの生成を行う．ボトム

できる．

れた配列の領域に対してグリッドサイズ 2

m

×2

m

アップに統合を行うので，新たに結果に入れたセルは一番上の

3. 1. 2 差分ヒストグラムの構築例

レイヤに属する限り，新たな候補セルを生成する（4-7 行目）．

差分配列と B = 10 が与えられたときの，差分ヒストグラム

差分ヒストグラムのセル数が B より大きくなくなるまで，貪

の構築例を図 2 に示す．パラメータ m が 0 の場合，初期ヒス

欲的に誤差が最小となるセルをヒストグラムに入れる（8-10 行

トグラムは与えられた差分配列と一致する．図 (b) に示したよ

目）．8 行目の get min error(CL) は，与えられた候補セルリ

うに，一回目の統合では誤差が最小（0）となるセルを差分ヒ

スト CL において，誤差の値が最小となるセルを返す関数であストグラムに入れる．そして，差分ヒストグラムのセル数が B

る．9 行目の children(copt ) は，セル copt の領域にカバーされ以下となるまで，この方針で統合を行う．ボトムアップに統合

る子のセルからなる集合を返す関数である．これらによって，を行いながら，計算済みの統計情報を保持して，式 (6) によっ

ヒストグラムを更新する．

てセルの誤差を計算できる．結果となるヒストグラムを図 2(c)に示す．

3. 1. 1 計算量の分析と効率化
このアルゴリズムでは，while ループを 1 回実行するたびに，

3. 2 ヒストグラム構築手法 2：閾値に基づく統合手法

4 個のセルが統合されて 1 個のセルになることから，結果的にヒストグラム構築手法 1 では，候補セル数が多い場合，計算3 個のセルが減少することになる．H.size の初期値が C であるため，C − 3p >= B を満たす最大の p が繰り返しの回数となコストも高くなる．そこで，閾値に基づく手法も提案する．基り，p の値は

⌊

p=

C −B
3

⌋

本的なアイデアは次のようになる．統合を行うとセルの誤差が大きくなるが，分布が比較的に均一である（誤差が小さい）セルを統合すると，結果の誤差も一般に小さくなる．ここでは，(3)

B − 1 番目に大きい誤差値 E B−1 を閾値として用いる．統合ので与えられる．なお，C の大きさはパラメータ m の設定に依

方針は，四分木の構造に基づき，誤差が E B−1 より小さい 4 つ

存しており，可視化の際の応答性と結果の精度のバランスを考の兄弟のセルを統合して，対応する親セルを結果に入れるとい慮する必要がある．m が大きいほど計算コストが少なくなり，うものである．このアルゴリズムを 2 に示す．

可視化処理における応答が良くなるが，結果の精度が低くなる．

手法の流れはアルゴリズム 1 と類似し，以下のように三つの指示するパラメータである．結果に入れた候補セルが一番上のレイヤに属する限り，新たな候補セルリストを生成する（4-7行目，13-15 行目）．候補セルの誤差については，節 3. 1. 1 に述べたように，式 (6) に基づき，子のセルの統計情報を用いて親セルの誤差を計算する．
候補セルリストにおいて，10 行目の条件を満たすセルを結果に入れる．つまり，候補セル c の 4 つの子のセルの誤差が閾値
より低い場合，c をヒストグラム結果に入れて，すべての子のセルを結果から削除する．図 3 の例では，一回目の統合処理において，左下の 4 つのセルの誤差が閾値（200）より小さいので，統合を行って，親のセルを結果に入れる．このアルゴリズ
ムでは，閾値は定数ではなく可変であり，閾値を更新しながら，条件を満たすセルを見つけてヒストグラムを構築する．

•
図2

実行例１：貪欲的な統合手法（B = 10）ステップ 3：セル数が B 以上であるならば，ステップ 2を繰り返す．統合できるセルが存在しない場合，閾値を緩めて，[E B−2 , E B−3 , ..., E 1 ] の区間で調整することが考えられる．図3 では，一回目の統合結果に対して，閾値 E B−1 は 200 である

Algorithm 2: Threshold-based Merging
Input: Adiﬀ : 差分配列, B：差分ヒストグラムのセルの総数, m：ので，条件を満たす統合は存在しない．しかし，ヒストグラムのサイズの制約 B を満たすため，閾値を調整して 300 とする

初期レイヤのパラメータと，図 3(c) の結果ヒストグラムが得られる．

Result: H: 差分ヒストグラムのセル集合
1

H ← merge(Adiﬀ , 2m , 2m );2curL ← 0, trd ← 0, triggerM = 0;

行える．ただし，実際の計算においては，1 回の繰り返しの中

3

while H.size > B do

で複数の統合処理を実施できるので，繰返し数を減らすことが実行処理の回数については，アルゴリズム 1 と同様の分析がif triggerM == 1 then

45

CL ← merge(H, 2, 2) ;6

curL + +, triggerM = 0;

7

end

8

trd ← get trd(CL)9for c ∈ CL do;// 候補セルリスト生成

できる．アルゴリズム 1 の場合と同様，パラメータ m の設定については，計算コストと結果の精度のトレードオフが存在する．

// 閾値を計算

if ∀cchild ∈ children(c), Error(cchild ) < trd then1011

H ← {c} ∪ (H \ children(c)) ; // ヒストグラム更新

12

CL ← CL \ {c} ;13

if c.layer == curL then// 候補リスト更新

triggerM = 1

14

end

15

end

16

end

17
18

end

19

return H;

ステップとなる．

•

ステップ 1：初期化（1,2 行目）

図3

実行例２：閾値に基づく統合手法（B = 10）指定された初期レイヤのパラメータ m を用いて対象領域を
N
× 2Nm
2m

のグリッドに分けて，すべてのグリッドセルを差分

3. 3 改善手法：要約情報に基づくアプローチ

ヒストグラム H に入れる．m = 0 の場合全てのセルの誤差は

上記の二つの差分ヒストグラム構築手法では，差分配列を入

0 となり，統合の必要はないため，m >= 1 を想定する．図 2 で力としてヒストグラムを構築するが，I/O コストと計算量が高示した例と同じ差分配列と B が与えられたとき，初期ヒスト

いことは問題となる．そこで，本節では，事前に計しておいたグラムは図 3(a) に示す 4 × 4 のグリッドとなる．

要約情報に基づいて，差分ヒストグラムを構築するアプローチ•

ステップ 2：統合（3-17 行目）

merge() 関数を用いて，候補結果となるセルリスト CL を生成する．4 行目に出てくる triggerM は統合を行うかどうかをを提案する．

3. 3. 1 要約情報に基づく誤差推定

3. 3. 2 要約情報に基づくヒストグラムの構築手法［定義 4］ 要約情報 S(Ast , t, m) は対象となる空間領域をグ

配列データの要約情報を事前に計算しておけば，差分ヒスト

リッドに分けて，与えたれた時間帯 t （t ∈ T ）で各グリッド

グラムを構築するときには全ての配列データにアクセスして差セル内の配列データを集計して（例：sum），対応する統計情分配列を計算する必要はなく，要約情報によって最適解となる報を保持する．グリッドのレイヤはパラメータ m によって決可能性のないセルをフィルタリングすることはできる．本手法

まる．つまり，S(Ast , t, m) の解像度は 2Nm × 2Nm となる．各は節 3. 1 と節 3. 2 で記述した差分ヒストグラムの構築手法に拡

要約情報セル sc では，平均値，最大・最小値，セル数と二乗誤張できる．ここでは，貪欲的な方針に基づいて，手法の概観を差を格納する．例えば，図 4 では，配列 ATa と ATb はそれぞ

アルゴリズム 3 に示す．

れ右図の 2 × 2 解像度の要約情報に対応する．

Algorithm 3: Statistic-based approach
Input: 要約情報 STa , STb , 差分ヒストグラムのセル総数 B, 初
期レイヤのパラメータ mResult: 差分ヒストグラムのセル集合 H
1

H ← apply(join(STa (m), STb (m), Adiﬀ ), delta, vb − va ) ; //要約情報を用いて初期ヒストグラムを生成

2

CL ← get error interval(STa (m − 1), STb (m − 1)) ; // 候補セ3

while H.size > B do

ルリスト生成4

copt←∅ ; CR ← CL ;5ubmin ← ∞ ; // 貪欲的なアプローチ：誤差の上限値を初期化
for c ∈ CL do
if Elb (c) >= ubmin then

67

CR ← CR \ {c} ; // 貪欲的なアプローチ：誤差の下8

限値は最小な上限値より高いセルをフィルタリング

図 4 要約情報の例

end

9

与 え ら れ た 配 列 ATa と ATb の 要 約 情 報 に よって ，対応 す る 差 分 ヒ ス ト グ ラ ム の 誤 差 の 区 間 を 推 定 で き る ．式(2) により，差分ヒストグラムのセル bi の誤差は E(bi ) =∑[(vb (c) − va (c)) − (mb − ma )]2 で計算される．なお，c∈bielse if Eub (c) < ubmin then10ubmin ← Eub (c);

11

13

end

14

copt ← copt ∪ get opt(CR);15間 Ta と Tb の 属 性 の 平 均 値 で あ る ．ま た ，配 列 ATa と

16

end

(va (c) − ma )2 と式

17

return H;

Eb (bi ) =

∑

c∈bi

// 検証：実際の誤差値を計算

し，条件を満たすセルを結果に入れる性 値 で あ り，ma と mb は そ れ ぞ れ セ ル bi に お け る 時∑// 上限値を更新

end

12

va (c) と vb (c) は そ れ ぞ れ セ ル c の 時 間 Ta と Tb の 属

ATb のセルの誤差は式 Ea (bi ) =// CR：候補結果リスト

update H, CL;(vb (c) − mb ) で計算される．これらによって
2c∈bi

E(bi ) の式を書き換えると，次の式となる．
E(bi ) = Ea (bi ) + Eb (bi ) + 2ma mb n −∑まず，入力の要約情報 STa と STb を用いて初期ヒストグラム

va (c)vb (c) (7)

ここでは，式の後ろの要素∑c∈bi

H を生成する．本研究では，配列指向型 DBMS である SciDB
で実装を行うため，SciDB のビルトイン演算を用いて初期ヒストc∈biva (c)vb (c) を var で示す．

グラムを構築する．つまり，1 行目に出てくる SciDB のビルトイ

さらに，要約情報に保持される属性値の最大値，最小値，平均ン演算 apply(join(STa (m), STb (m), array D), delta, vb −va )値など統計情報によって， var の下限値と上限値は次の式：を用いている．join 演算を使って配列 STa (m) と STb (m) を統

varlb = max(min(va (c)) × mb n, min(vb (c)) × ma n)(8)varub = min(max(va (c)) × mb n, max(vb (c)) × ma n) (9)合して，apply 演算で属性値の差 vb − va を新たな属性 deltaに入れる．

2 行目の get error interval(STa (m − 1), STb (m − 1)) は初期
ヒストグラムの一個上のレイヤのセルを候補セルリストに入れで推定される．そして，セル bi の誤差の区間は以下の式で計て，式 (10) と式 (11) を用いて対応する差分誤差の区間を計算

算される．

する．次に，得られた差分誤差の区間によって，チェックする
必要のないセルをフィルタリングする．

Elb (bi ) = Ea (bi ) + Eb (bi ) + 2ma mb n − varub(10)

Eub (bi ) = Ea (bi ) + Eb (bi ) + 2ma mb n − varlb

(11)

•

フィルタリング手法１（貪欲的なアプローチ）（6-13 行目）：誤差の下限値が最小の上限値よりも高いセルをフィルタリングする．誤差がセル c の誤差の下限値よりも小さいセルが存在するので，セル c は最小の誤差ではないことが分かる．そのため，セル c の実際の誤差をチェックする必要はなく，候補
結果リスト CR から削除する．

•

4. SciDB における実装

フィルタリング手法２（閾値に基づくアプローチ）：B −1

本研究では，配列指向型 DBMS である SciDB を活用してに番目大きい誤差を閾値として，誤差が閾値より小さいセルを差分演算を実装する．SciDB では，大規模な配列データは複統合する方針であるので，B − 1 番目に大きい誤差の上限値

数のチャンクに分けられて，分散して SciDB クラスタに格納

ubB−1
max を使ってフィルタリングを行う．フィルタリング手法２される．SciDB クラスタは複数のインスタンスで構成されては次のアイデアに基づく：セル c の誤差の上限値は ubB−1
max よおり，インスタンスごとに複数のチャンクが格納される．このりも小さい場合，セル c の誤差は必ず閾値より小さいことが分ようなデータ構造によって，SciDB は並列分散処理を行う [3]．

かるため，実際の誤差を計算する必要はない．

問合せ処理の過程では，あるインスタンスがコーディネータ

フィルタリングを行って得られた候補結果リストに対して， （coordinator）として動作し，問合せプランを生成してほかの検証を行う（14 行目）．具体的な配列データにアクセスして実ワーカインスタンスに割り当てる．次に，ワーカインスタンス

際の差分誤差を計算して，条件を満たすセルを結果に入れる．

は関連するチャンクデータを処理して中間的な結果を生成する．

3. 3. 3 要約情報に基づく手法の実行例

最後に，コーディネータはワーカインスタンスの結果を統合し貪欲的な手法を例として，要約情報に基づくヒストグラム構て，最後の結果を出す．

築の過程を図 5 に示す．図 5(a) は図 4 の要約情報によって推SciDB では，さまざまなビルトイン演算が提供されている一定された差分誤差の区間であり，図 5(b) は実際の配列データ

方，特定な要求に対応するためのユーザ定義演算（UDOs）もにアクセスして計算された差分の誤差値となる．アルゴリズム

サポートされている．SciDB のプラグイン仕組みを用いることの実行例を図 5(c) に示す．

で，差分演算を UDO として実装する．差分演算は C++言語
で記述する．
上記の SciDB の機能を活用して，本論文で提案したヒストグラム構築手法を実装する．チャンクは SciDB における最小の I/O 単位であるため，ボトムアップに統合を行うときにチャンクを単位として処理が行われる．チャンクごとにローカルな最適解を見つけて，最後にこれらのローカルな最適解をまとめて，グローバルな解を計算する．

5. 評 価 実 験
5. 1 対象となるデータセット
本研究で使っているデータセットは，大規模地震の発生時の，高知市における人流の避難シミュレーションデータである．このデータは東京大学関本研究室からの提供による．今回実験で用いるサンプル人流は，地震発生後に約 4 万人の人が避難する
図 5 実行例３：要約情報を用いた貪欲的な手法

状況を，パーソントリップデータに基づいてシミュレーション
している．

最初に，4 つの要約情報のセル {sc1 , sc2 , sc3 , sc4 } は候補セ

シミュレーションデータは (id, time, x, y) という形式のレ

ルリスト CL に入っている．セル sc1 をスキャンすると，ubmin

コードの集まりである．id はユーザ ID，time は時刻， x, y

は 0 となる（10,11 行目）．次に，フィルタリング手法１によっは時刻 time におけるユーザの位置である．シミュレーションて，sc2 , sc3 , sc4 をフィルタリングすると，最適解 copt は sc1

データは，シミュレーション後には変化しない静的なデータでとなる（7,8 行目）．2 回目のループでは，sc4 はフィルタリン

ある．本研究が目的とするデータウェハウス的な問合せ処理にグ手法１により候補結果リストから削除されるので，sc2 と sc3

おいては，静的なデータであることの利点を生かし，前処理をを比較する必要がある．そのため，実際の誤差を計算して，誤行うことで対話的処理を効率化することが一般的である．そこ差が最小となる sc3 を結果に入れる．3 回目のループでは，同で，今回のデータについては，空間的には 4, 096 × 4, 096 のレ様に sc4 をフィルタリングして，sc2 を結果に入れる．ここでベルの最大粒度の分割を行う．この空間の細粒度の分割に基づ

ヒストグラムのセル数の制約（B = 7）を満たしたので，アルき，各セル内で 1 分ごとにその中の避難者数を集計する．前処

ゴリズムを終了する．

理の結果得られた集計データを SciDB にロードし，これを差この例では，実際に配列データにアクセスして差分と対応する誤差を計算したのは E2 と E3 のみとなる．E1 と E4 は要分演算の問合せ処理の対象とした．また，対象となる配列デー
タ Kouchi eva のデータスキーマを以下に示す．

約情報に基づき誤差の区間を推定できるので，提案したフィル
タリング手法によって，誤差を実際に計算することなく判断でKouchi_eva<Num:double>

きる．

[X=0:*,4096,0,Y=0:*,2048,0,T=0:*,256,0]配列 Kouchi eva では，座標 X,Y と時間 T という三つの次元があり，属性 N um は対応するセルの避難人数の総数である．

6. まとめと今後の課題
本稿では，時空間データの高度な分析機能を実現するため，差分演算に着目し，差分ヒストグラムの構築手法と効率化の手法を提案した．また，効率性と有効性を考慮した評価実験と，配列指向型 DBMS の機能をフルに活用した実装技術について
も開発を行う予定である．
本論文で示した差分演算では，2 つの時区間 T1 , T2 がユーザにより指定されることを想定していた．しかし，このようなアプローチは，事前にユーザが着目すべき時区間についてすでにアイデアを有しているときにしか使えないことから，より多くのケースに対応することが必要である．さらに今後の課題としては，差分演算のセマンティクスの拡張が考えられる．今回は単純に差の大小のみに着目したが，増加傾向にあるか，減少傾向にあるか，また増加・減少の速さはどの程度かといった情報に着目した差分演算も開発したいと考えている．このような差分を考える場合，どのように可視化するかもポイントとなることから，可視化手法についても検討を行う．

謝辞本研究の一部は，科研費（16H01722, 26540043) ，CREST「大規模・高分解能数値シミュレーションの連携とデータ同化による革新的地震・津波減災ビッグデータ解析基盤の創出」，および文部科学省「実社会ビッグデータ利活用のためのデータ統合・解析技術の研究開発」による. 避難シミュレーションデータ
を提供いただいた東京大学関本研究室に感謝します．

文

献[1] S. Muthukrishnan, V. Poosala, and T. Suel. On rectangularpartitionings in two dimensions: Algorithms, complexity,
and applications. In C. Beeri and P. Buneman, editors,
ICDT, volume 1540 of Lecture Notes in Computer Science,
pages 236–256. Springer, 1999.
[2] Paradigm4: Creators of SciDB a computational DBMS.
http://www.paradigm4.com/.
[3] M. Stonebraker, P. Brown, A. Poliakov, and S. Raman. The
architecture of SciDB. In SSDBM, volume 6809 of LNCS,
pages 1–16, 2011.
[4] M. Stonebraker, P. Brown, D. Zhang, and J. Becla. SciDB:
A database management system for applications with complex analytics. IEEE Computational Science & Engineering, 15(3):54–62, 2013.
[5] J. Zhao, K. Sugiura, Y. Wang, and Y. Ishikawa. Simulation data warehouse for integration and analysis of disaster
information. Journal of Disaster Research, 11(2):255–264,
2016.
[6] 石川佳治. 大規模データアナリティクスに関する研究動向と展
望. 電子情報通信学会論文誌 D, J97-D(4):718–728, 2014 年 4月.