論文

移動軌跡ストリームデータのためのインクリメンタルなヒストグラ
ムの管理手法An Incremental Histogram Management
Method for Moving Trajectory Stream
Data

町田 陽二 石川 佳治
北川 博之
Yoji MACHIDA Yoshiharu ISHIKAWA
Hiroyuki KITAGAWA
GPS や通信技術の発展に伴い，移動する多数のオブジェクトの
移動状況の追跡が容易になっている．こうした移動状況データを分析・予測に利用するには，ストリーム的に配信されてくる移動
状況データを効率よく要約する必要がある．そこで，我々はマル
コフ連鎖モデルに基づき移動データを要約する移動ヒストグラム
を動的に構築する手法の開発を進めている．提案手法ではヒスト
グラムを表現する物理的なデータ構造として木構造を採用し，移動パターンを複数の粒度で表現する．移動オブジェクトの移動軌跡が送られた際には，インクリメンタルにヒストグラムを更新する．また，本論文では，中間ノードにカウンタを設けた場合の処理時間を評価する．
With the recent progress of spatial information
technologies and communication technologies, it becomes easy to track trajectories of many moving objects in real-time. To use obtained moving object trajectories for the analysis and prediction, we need toaccumulate given trajectory streams in an efficientand accurate manner. For this purpose, we proposea mobility histogram construction method based on
the Markov chain model. The histogram is physically
represented as a tree structure and represents movement patterns in multiple granularities. When a new
trajectory sequence is obtained, it updates the histogram structure incrementally. We also evaluate processing time for a method in which middle-nodes contain counters.

1. はじめにGPS や通信技術の発展に伴い，移動する多数のオブジェクトの
移動状況の追跡が容易になっている．また，こうしたオブジェク
トの移動状況を蓄積するのに，時空間データベースがますます一般的になっている．
大量の移動オブジェクトの移動状況をリアルタイムに追跡し，分析・予測に役立てるには，ストリーム的に配信されてくる移動
状況データを効率よく要約することが求められる．さらに移動オ
ブジェクトの移動状況を要約することは，オブジェクトの移動状
況を蓄積した時空間データベースにおける問合せ処理でも有用である．
学生会員 筑波大学理工学研究科
y-machida@kde.cs.tsukuba.ac.jp
 正会員 筑波大学システム情報工学研究科，計算科学研究センター{ishikawa,kitagawa}@cs.tsukuba.ac.jp

1

DBSJ Letters Vol. 4, No. 2
ストリーム配信されるデータを継続的に集計し，コンパクトに移動状況を要約することは重要な研究課題である．そこで本研究グループは，移動データを要約する移動ヒストグラム（mobility
histogram）の概念を提案し，ストリーム的に配信されてくる移動状況データを効率よく集計するための動的なヒストグラム構築
手法の研究を進めている [11]．このアプローチでは，マルコフ連鎖モデルに基づいて移動パターンの移動統計量を集約する．移動
オブジェクトの移動軌跡が送られるたびに，インクリメンタルに
ヒストグラムの更新を行う．精度を落とさずに効率的な処理が実現できること，また，コンパクトにヒストグラムを表現できることが課題となる．我々のグループの過去の研究 [11] では，木構造に基づくヒストグラム構造のアイデアを提案した．この手法では，
移動軌跡データが少ない時点では少数のバケットからなる木構造に移動データを要約して管理する．移動データが追加されるにしたがって木構造を順次拡張し，指定された上限のサイズに達した
時点で，必要に応じて木の枝刈りなどを行う．
しかし，このアプローチは効率の面では優れていたものの，精度の面では不十分であった．初期の時点において移動軌跡データを要約して表現してしまうため，そこで発生した誤差が後々の段階まで波及してしまうという点がその理由であった．
そこで，本研究では，ヒストグラムに対する新たなデータ構造の提案を行う．提案手法では，初期段階からメモリを積極的に利用し，移動オブジェクトの移動状況を正確に反映することを目指す．
加えて [6] では，忘却 (forgetting) の概念の導入によるヒストグ
ラム構造の拡張を図った．忘却の概念により，時間につれて移動パターンが変化するような非定常的な移動状況への対応を行う手法である．また，忘却の概念を用いた木構造のヒストグラムのメ
ンテナンス処理において，メモリサイズの制限も考慮することにより，コンパクトなデータ構造の表現を試みた．本稿では，定常状態で中間ノードにカウンタを設けた場合の処理時間の評価を示
す．提案手法の一部である忘却の概念を取り入れた手法についての説明は割愛する．詳細については [6] を参照していただきたい．

2. 背景および関連研究
ヒストグラムは，データを要約するための一手法であり，デー
タベースの分野でも，特に問合せ最適化や近似問合せにおいて盛んに研究開発が進められている [5]．これまで特に単一属性に関するヒストグラム構築の研究が進められてきたが，近年では複数属性に対するヒストグラム構築に関する技術開発も着目されている[2, 8]．また，動的なヒストグラムの管理に関しても研究が進められている [4, 7]．
本研究で対象とするヒストグラムは，特殊な制約はあるが多次元のヒストグラムと分類される．与えられたデータに対して最適なヒストグラムを構築することは NP 完全に属する困難な問題であり [5]，近似的な構築法が求められる．また，本研究の目的とする移動軌跡データのリアルタイムの集積を実現するためには，インクリメンタルな更新に対応するために，特に効率性が求められる．
移動状況データをヒストグラム表現することで，大量の移動オ
ブジェクトの移動状況を効率よく分析予測することが可能になる．
例えば，移動オブジェクトがどこにいた可能性が高いのか，移動
オブジェクトが今後どこに行く可能性が高いのか，ある領域においてオブジェクトがどのように移動するのかなどは統計量をもとに推定できる．関連研究 [3, 10] と比較した本研究の他の特徴としては，ストリーム的な移動軌跡データのリアルタイム処理がある．静的なデータを集約するのではなく，大量のストリームデー
タを効率的に集約する点を特徴とする．

3. 移動パターンのモデリング
3. 1 Z-ordering
まず，準備として，本手法における移動パターンのモデリングのために用いる，2 次元平面の番号付け手法について述べる．この手法は 2 次元平面を 1 次元で順序付けする手法の一つである
Z-ordering[9] に基づいている．複数ある順序付けする手法の中でも，Z-ordering には順序付けの計算が容易でかつ，様々な分割にも扱えるというメリットがあるので，本研究でも利用している．
2 次元空間が各次元ごとに （ は分割レベルを表す）個ずつ，
 個のセルに分割されているとする．この分割のことをレ

日本データベース学会 Letters Vol. 4, No. 2

論文

DBSJ Letters Vol. 4, No. 2

ベル の分割と呼ぶ．各セルには，2 ビットのセル番号を付与する．セル番号の上付き数字で，空間分割レベルを表す．
このレベルの概念を用いることで空間分割の粒度を指定できる．
レベルの異なる分割を対比して，粗い分割の方を上位の空間分割，
細かい分割の方を下位の空間分割と呼ぶ．

3. 2 マルコフ連鎖モデル

時空間データ分析におけるマルコフ連鎖モデル（Markov chain
model）は，ある地域から別の地域へある期間内にどの程度の人
口が移動したなどの，移動オブジェクトの時空間的な移動傾向の把握に用いられる [12]．以下では，マルコフ連鎖モデルの概念について述べる．
図 1 は，上位空間と下位空間の場合について時刻 
でそれ
ぞれセル ，セル   にいたオブジェクトが，次の時刻 
でセル ，セル    に，そして  の時点でセル ，セル   に移動した状況を示している．






































































































































 
















VǼ ) 

4. 提案手法

4. 1 データ構造

4. 1. 1 基本的アイデア
入力として与えられる移動軌跡データにおいて，分割レベル 
でセルの番号付けがなされているとする． を最大空間分割レベルと呼ぶ．移動ヒストグラムは木構造で表現する．木の各ノード
は 0 個以上 4 個以下の子を有し，そのノードに対応する移動軌跡の数を集積するためのカウントも有する．
ここで，遷移シーケンス → →  を挿入することを想定する．，， はセル番号を表す．また， をステップ
0 のセル， をステップ 1 のセル， をステップ 2 のセルと呼ぶ．上記遷移シーケンスを木に挿入する場合を例にとって説明する．まず ，， をバイナリ表記して，まず， の上位 2ビットを取り出す．その内容が   ，  ，  ，   のいずれかであるかに応じて，対応する辺を辿り，子ノードへと達する．ただし，そのような辺がない場合には，新たに辺を作成する．さらに ， の順に上位 2 ビットを取り出し，その値に応じて同様に子ノードにアクセスする．以上のステッ
プは空間分割レベル 1 に対応する．

2













 
















































































































 













ࠬ࠹࠶ࡊ  ࠬ࠹࠶ࡊ 

ࠬ࠹࠶ࡊ 

ࡃࠗ࠽࡝⴫⃻
ࠬ࠹࠶ࡊ   ࠬ࠹࠶ࡊ  ࠬ࠹࠶ࡊ  

図 2: 木構造 ( →  →  ，
）Fig. 2: Tree structure ( →  →  ，)Z  ࠞ࠙ࡦ࠻ᢙ



















࡟ࡌ࡞ 









 
 

図1の   という移動の例は 2 次のマルコフ遷移である．このような遷移情報を集積しておけば，「      と遷移したオブジェクトが次にどのセルに移動する確率が高いか」，「      と移動したオブジェクトは，セル    の前にどこにいた可能性が高いか」といった質問に，確率の推定値をもとに答えることができる．また，ある領域においてオブジェクトがどのように移動するかといった移動パターンの分析などにも利用できる．
本稿で提案するヒストグラムは，指定された遷移の次数  に対し， 次のマルコフ遷移を表現する．ヒストグラムの構造についの場合を想定て，次節で説明する．なお，以下の説明では するが，アルゴリズムは他の  の値にも適用可能である．
 

࡟ࡌ࡞ 





図 1: マルコフ連鎖モデルの概念（2 次の場合）
Fig. 1: Concept of Markov chain model (when 
 

ⓨ㑆ಽഀ







 












TQQV


ⓨ㑆ಽഀ








VǼ 

VǼ





































次に， の次の 2 ビット， の次の 2 ビット， の次の 2ビットをそれぞれ取り出し同様の処理を行う．このステップは空間分割レベル 2 に対応する．このようなステップを繰り返し，2
ビットずつを処理した時点で末端ノードに至る．この末端ノードまで至る過程において，各ノードのカウントを 1 ずつインクリメの場合について， →  →   を追加
ントする．図 2 に する例を示す．
図 2 の点線はノードを辿るような遷移シーケンスが依然として到着していないことを表しており，実際にはそれ以下の部分木は存在しない．実線はノードを辿るような遷移シーケンスが過去に挿入されたことを表している．





 

ታ✢  ㄡߞߡ޿ࠆ
ὐ✢  ৻ᐲ߽ㄡߞߡ޿ߥ޿

4. 1. 2 追加アルゴリズム
追加処理のアルゴリズムでは，最大空間分割レベルが  であり，マルコフ遷移の次数が  であることを想定している．ヒスト
グラムの木構造の各ノードは，カウント値と子ノードへの 4 個のポインタを有する．初期段階では，木構造はルートノードただ 1
つからなる．
アルゴリズムの概要を説明する．まず，ノードへのポインタ を，ヒストグラムのルートである  で初期化する．次に，シフト量    を初期化する．続いて粗い分割から細かい分割へ辿る
のに，分割粒度を用いる．各分割粒度ごとに 0 番目のステップから  番目のステップという遷移シーケンスの遷移を進める．ノードを辿る過程でまだ割り当てられていないノードが存在した場合，ノードを新たに割り当てる．このような処理により，1 つの遷移
シーケンスの追加において辿る辺の数は      個となる．ヒストグラムの構造は主記憶上に置かれ，また，  の値は一般に小さいため，追加処理は高速に行える．
ここでヒストグラムのサイズについて考える．すべての移動パ
ターンについて遷移シーケンスが木構造に挿入されることを考えると，最大  のノードが必要になる．各ノードにおいて，カウンタが 4 バイト整数であり，4 個のポインタが 4 バイトであるとすると，各ノードのサイズは 20 バイトとなる．そのため，たとえば， ，の場合は最悪のヒストグラムのサイズは320MB となる．一方，
，と一段詳細度を上げると，最悪のサイズは 20GB となり膨大となる．
ただし，実際の移動オブジェクトの移動パターンには大幅な偏りが存在する．ある時点である位置に存在するオブジェクトが，次の時点で大きく離れた地点に移動することは現実的にはありえないことから，たとえば図 1 において          という遷移シーケンスは発生しえない．このため，実際の利用においては木構造のほんの一部のみが実体化されるため，実際に要求されるメモリ領域は上記よりは大幅に小さいと考えられる．
ヒストグラムの木構造に関しては，実装レベルで配列などを用いてよりコンパクトに表現することが考えられる．しかし，上記のアプローチは基本的にデータを追加していくだけであるため，データの追加に伴い木が巨大になる可能性は避けられない．また，過去の遷移シーケンスと最近の遷移シーケンスのカウントが全く同等の扱いになっているので，時間的に移動パターンが変化する
ような非定常的な状況に適用できない．[6] では，こうした問題に日本データベース学会 Letters Vol. 4, No. 2

論文

DBSJ Letters Vol. 4, No. 2

対し忘却の概念を導入することで解決を図っている．

4. 2 問合せ処理
次いで，ヒストグラムを用いて，移動軌跡のカウント数を求める問合せに答えるための問合せ処理方式について述べる．

4. 2. 1 基本的アイデア
まず，最大空間分割レベルが て処理の概要を説明する．

 4 行目：与えられた問合せをどこまで処理したかを表現するの場合について，例を用い

1. 移動軌跡の各セルのレベルが最大空間分割レベルと一致する
場合：たとえば， →  →   を考える．この場合が一般的で容易である．遷移シーケンスの挿入と同様に，各ステッ
プをバイナリ表記して各レベルごとに 2 ビットずつ辿っていき，目的のカウントを返す．
2. 移動軌跡の各セルのレベルが最大空間分割レベルよりも粗い場
合：例として → →   を考える．(1) と同様に，各ステッ
プをバイナリ表現にして，各レベルごとに 2 ビットずつ辿っていく．この場合は，空間分割レベル 1 の      の後，00, 01, 10, 11 → 00, 01, 10, 11 → 01 の      
通りの経路をすべて辿り各カウントを調べ，総和をとる必要がある．
3. 移動軌跡のセルのレベルが最大空間分割レベルよりも大きい
場合：たとえば， → →   を考える． → →  は，空間分割レベル 2 までの木では表現できないので，カウントを近似的に推定する必要がある．実際はカウントの推定式を定め，近似することが望ましいが，本稿では便宜上このような問合せに対して，カウント 0 を返すことにする．
4. 2. 2 問合せ処理のアルゴリズム
問合せ処理のアルゴリズムをアルゴリズム 1 に示す．このアルゴリズムは再帰的な関数 est count() を定義している．この関数
は 4 つの引数  ,  ,    ,   をとる． は処理対象のノードへのポインタ，   は現在処理対象の遷移ステップを表す．
     はそれぞれ問合せ移動シーケンス中の領域番号の配列
およびレベル番号の配列である．たとえば，       という遷移シーケンスが問合せとして与えられた場合，            であり，   
となる．
ある遷移シーケンスの出現回数の推定を求める問合せがユー
ザから与えられると，まず 2 つの配列   と    を構築し，
est count( ,  ,    , 0) という関数呼び出しを行う． はヒストグラムのルートを表し，0 はまず最初は 0 番目の遷移ス
テップに関する処理を行うことを意味する．

Algorithm 1 est count( , , ,  )1: input: 対象ノード, : 問合せの遷移シーケ
ンス, : 各遷移のレベル配列,  : 処理対象のス
テップ
2: if (
について  )
3:
問合せ処理を終え，目的のカウントを返す 
4: if (    )5:       ; //2 ビット抽出のシフト量6:
探索する子ノード番号 7:   --;8:
if (    ) //探索途中で辿る辺がない
9:
return    ;
10:
else
11:
次の遷移ステップを表す子ノードへ再帰処理 
12:
else
13:
4 つの子ノードに分岐し，計算結果を集計 3

アルゴリズムの概要を説明する．このカウント処理では，ルートから 1 ノードずつ辺を辿って，対象となるカウントを有するノードまで探索し，そのカウント値を返す．木の探索処理は再帰呼出しで実現する．ただし，場合によっては 1 つの問合せに対し複数の辺に分岐して探索を行う必要も生じることに注意する．
のに    配列の値で判別 4-11 行目： からその子に対し 1 つだけ辺を辿る処理– 8 行目の条件が偽：11 行目の再帰呼び出しを実行

 子に対してカウント処理を引き継ぐことを表す– 8 行目の条件が真：4.2.1 節の 3 の場合のように，問合せに対してヒストグラムの解像度が高くなく，近似的なカウント値を推定する必要がある場合の処理 ここではカウント 0 を返す
 13 行目：分岐処理が必要となり，4.2.1 節の 2 の場合に相当 4 つの辺に対し，est count() を 4 回再帰呼び出しし，その結果の和をとる

5. 実験
忘却を持たない定常状態のときで，中間のノードにカウンタを設ける場合の処理時間について評価を行う．
ヒストグラムの処理時間についてそれぞれ挿入処理，問合せ処理における様子を見ていく．

5. 1 実験データ
実験では Brinkoff により作成された移動オブジェクトデータ
生成ソフトウェアを用いる [1]．これは実際の市街地の道路ネット
ワーク上を自動車などが移動する際の移動の状況をシミュレーショ
ンするシステムであり，これによって生成された移動データを実験において使用する．今回扱うデータは，このシステムで提供されているドイツ Oldenburg 市の市の中心部（約    km）の道路ネットワークにおいて，パラメータを適宜設定して生成したものである．図 3 にこのシステムのインタフェース画面を示す．
以下の実験において，Pentium4 3.2GHz の CPU，１ GB のメモリを持つ PC を使用して実験を行った．加えて地図領域を     のセル領域に分割した場合を想定している．

5. 2 実験手法
移動オブジェクトデータ生成ソフトウェアより，二つのデータ（B）を用いてヒストグラムの構築時間，また問合せセット（A），
処理時間の実験を試みた．データセット (A) は 2 次のマルコフ遷
移をし，それぞれ空間分割レベル 10 の遷移シーケンスを 1000 件有する．データセット (B) はデータセット (A) 同様の遷移シーケ
ンスを 10000 件有する．

5. 2. 1 ヒストグラム構築時間
定常状態の挿入処理を行う．そこでデータセット（A）でヒス
トグラムを構築すると，ノードが 25549 個生成される．各ノー
ドには，カウンタに 4 バイト，各ポインタに 4 バイト，計 20 バ
イト使用している．これより，上記のデータセットで構築したヒストグラムのサイズには 500 ｋバイト必要となる．ヒストグラムの構築時間は 19 ミリ秒である．遷移シーケンスあたりの処理時
間は 0.019 ミリ秒である．同様にデータセット (B) ではノードが191136 個生成される．構築したヒストグラムのサイズには 4Mバイト必要となる．ヒストグラムの構築時間は 150 ミリ秒である．
遷移シーケンスあたりの処理時間は 0.015 ミリ秒である．各デー
タセットのヒストグラム構築時間を図 5 に示す．
5. 2. 2 問合せ処理時間
定常状態の問合せ処理を行う．複数の問合せパターン 100 個を与えた際の問合せ処理時間を調べた．問合せのパターンには 4.2.1
節のように (1) 移動軌跡の各セルのレベルが最大空間分割レベルと一致する場合（問合せ例：
      ），(2) 移動軌跡の各セルのレベルが最大空間分割レベルこの場合よりも粗い場合（問合せ例：       ，        ) を用いた．

日本データベース学会 Letters Vol. 4, No. 2

論文

DBSJ Letters Vol. 4, No. 2

        を問合せ例として分割された地図領域を図 4に示す．太枠は空間分割レベル 2 を，細枠は空間分割レベル 4 を表している．



















 



   について評価した．
今後の課題として，1) 末端のノードのみカウンタを有する場合の処理時間についての同様な評価実験，2) 定常的な場合と非定常的な場合の性能評価，3) メモリの回収具合を考慮した実装方式の検討が挙げられる．

[謝辞]
本 研 究 の 一 部 は ，日 本 学 術 振 興 会 科 学 研 究 費 基 盤 研 究(C)(2)(16500048) ，旭硝子財団研究助成，稲森財団研究助成，文部科学省科学研究費特定領域研究 (2)(16016205) 及び CREST 「自律連合型基盤システムの構築」による．

[文献][1] T. Brinkhoff. A framework for generating network based
moving objects. GeoInfomatica, No. 6(2), pp. 153–180,
2002.

図 3: 移動軌跡データの例
図 4: 地図領域における問合せ例
Fig. 3: Moving trajectory data
Fig. 4: Example query[2] N. Bruno, L. Gravano, and S. Chaudhuri. STHoles: A
multidimensional workload-aware histogram. In Proc.
SIGMOD, 2001.

いずれの問合せも全て 2 次のマルコフ遷移の遷移シーケンスで行った．問合せパターンごとの問合せ処理時間を図 6 に示す．

[3] Y. Choi and C. Chung. Selectivity estimation for spatiotemporal queries to moving objects. In Proc. ACM SIGMOD, pp. 440–451, 2002.




 ઙ

ࡅࠬ࠻ࠣ࡜ࡓ 
✚᭴▽ᤨ㑆
OU

 ઙ

ㆫ⒖ࠪ࡯ࠤࡦࠬ

 ઙ ઙᒰߚࠅߩಣℂᤨ㑆[5] Yannis Ioannidis. The history of histograms (abridged).
In Proc. VLDB, 2004.



OU






[6] 町田陽二, 石川佳治, 北川博之. 移動軌跡ストリームデータのための動的ヒストグラム構築手法. 電子情報通信学会データ
工学ワークショップ (DEWS 2005), March 2005.

࠺࡯࠲࠮࠶࠻

࠺࡯࠲࠮࠶࠻

図 5: ヒストグラムの構築時間
Fig. 5: Histogram construction time

✚໧วߖ



 ઙ

 ઙ ໧วߖಣℂᤨ㑆 

OU

 ઙ

 ઙ



ᒰߚࠅߩ




ಣℂᤨ㑆 
OU










[7] Y. Matias, J. S. Vitter, and M. Wang. Dynamic maintenance of wavelet-based histograms. In Proc. VLDB, pp.
101–111, 2000.





ᦨᄢⓨ㑆ಽഀᦨᄢⓨ㑆ಽഀ

࡟ࡌ࡞ߣ৻⥌

࡟ࡌ࡞߇☻޿= ଀ ψ ψ ‫ޓ‬㨉= ଀ ψ ψ ‫?ޓ‬ᦨᄢⓨ㑆ಽഀᦨᄢⓨ㑆ಽഀ
࡟ࡌ࡞߇☻޿= ଀ ψ ψ ‫ޓ‬㨉







= ଀ ψ ψ ‫?ޓ‬

図 6: 問合せ処理時間
Fig. 6: Query processing time
データセット (A) で構築したヒストグラムに各問合せパターンの平均処理時間は，(1)60 ミリ秒，(2)44 ミリ秒である．1 問合せ
当たりの処理時間は (1)0.60 ミリ秒，(2)0.44 ミリ秒である．1 問
合せあたりの問合せ結果は (1)0.36 回，(2)26 回のカウントである．同様にデータセット (B) では，(1)62 ミリ秒，(2)42 ミリ秒である．1 問合せ当たりの処理時間は (1)0.62 ミリ秒，(2)0.42 ミリ秒である．1 問合せあたりの問合せ結果は (1)0.72 回，(2)173 回のカウントである．
実験結果より，中間ノードにカウンタを有する場合のヒストグ
ラム構築時間はデータセットが 10 倍に増えても処理時間が 10 倍にはならなかった．それはデータ数が多ければ新規にノードを作成することも減り，上位レベルのノードを辿る可能性が高いと考えられ，処理時間が短縮している．また，問合せ処理時間においては，データセットが多くなっても処理時間に差がほとんどない．
すなわち同じ空間分割レベルでヒストグラムを構築していれば，問合せ処理に影響を及ぼさないことがいえる．

6. まとめ
本稿では，木構造による移動統計量の推定手法を提案し，定常状態において，中間のノードにカウンタを有する場合の処理時間

4[8] V. Poosala and Y. Ioannidis. Selectivity estimation without the attribute value independence assumption. In
Proc. VLDB, pp. 486–495, 1997.
[9] Shanshi Shekhar and Sanjay Chawla.
Databases. Prentice Hall, 2002.

࡟ࡌ࡞ߣ৻⥌
[4] P. Gibbons, Y. Matias, and V. Poosala. Fast incremental maintenance of approximate histograms. In Proc.
VLDB, pp. 466–475, 1997.

Spatial[10] Y. Tao, J. Sun, and D. Papadias. Selectivity estimation
for predictive spatio-temporal queries. In Proc. ICDE,
2003.
[11] 塚本祐一, 石川佳治, 北川博之. 移動軌跡ストリームからの移動統計量推定のための動的ヒストグラム構築手法について.
電子情報通信学会データ工学ワークショップ (DEWS 2004),
March 2004.
[12] G. J. G. Upton and B. Fingleton. Spatial Data Analysis by Example, Volume II: Categorical and Directional
Data. John Wiley & Sons, 1989.

町田 陽二 Yoji MACHIDA
筑波大学大学院理工学研究科在学中．時空間データベースの研究に従事．日本データベース学会学生会員．

石川 佳治 Yoshiharu ISHIKAWA
筑波大学大学院システム情報工学研究科，計算科学研究センター
助教授．データベース，データ工学，情報検索などに興味を持つ．
日本データベース学会，情報処理学会，電子情報通信学会，人工知能学会，ACM，IEEE CS 各会員．

北川 博之 Hiroyuki KITAGAWA
筑波大学大学院システム情報工学研究科，計算科学研究センター
教授．異種情報源統合，文書データベース，WWW の高度利用等の研究に従事．著者「データベースシステム」（昭晃堂）等．日本
データベース学会，情報処理学会，電子情報通信学会，日本ソフトウェア科学会，ACM，IEEE CS 各会員．

日本データベース学会 Letters Vol. 4, No. 2