第 2 章 関連研究
3.3 実装
3.3.1 空間データ提供システム
提案手法に基づく空間データ提供システムを，Java言語 (JDK1.2)を用いて実装 した．
本システムは，TCPコネクションを介して空間データを提供するサーバとして動 作し，探索プロセスとデータ転送プロセスは，それぞれスレッド(java.lang.Thread) として実装した．これらのスレッドは並行に動作し，バッファを用いて検索結果を 共有する．探索用のスレッドは中間結果を保持するためのバッファを持ち，転送用 のスレッドはこのバッファから送信すべきデータを取得する．
3.3.2 データ構造
本実験では，サンプルデータとして，国土地理院[GSI]発行の「数値地図2500(空 間データ基盤)」[JMC]を使用した．この数値地図には，街区，行政区，道路情報 など様々な地図データが含まれ，図葉と呼ばれる矩形領域ごとに，それぞれのデー タがファイルとして保存されている．各図葉は，縦1500 メートル(m)，横2000 メートル(m) の矩形領域である．座標表現は，緯度経度ではなく，平面直角座標
系1[JMC 98, 村井02]で示され，単位は メートル (m) である．たとえば，平面直
角座標IX 系は，東経139 度 50分，北緯 36度 0分で表現される点を原点，横方 向(左 → 右)を x 軸，縦方向(下 → 上)を y 軸とする座標系である．本実験で用 いた数値地図2500(空間データ基盤)「神奈川-3」「神奈川-4」2の地図データは，平 面直角座標 IX 系 での座標で表現されている．
この数値地図2500(空間データ基盤) に収録されているデータファイルから，図 葉ごとに，線データおよびポリゴンデータを含むデータファイルをそれぞれ新た に生成し，空間データベースとして構成する．そして，この空間データベースの空 間インデックスとしてR-tree[Guttman 84]を実装した．R-treeでは，葉ノードの エントリがデータレコードを特定するためのid情報を含むので，このid情報とし てファイル名とファイルポインタをインデックスの構築時に記録する．ファイルポ インタはファイルの先頭からのバイト数である．データファイルへのアクセスは，
このファイルポインタを引数として，java.io.RandomAccessFileクラスのseek()メ ソッドを用いて行う．なお，この空間インデックスはデータの種類ごとに作成する ものとする．
3.3.3 問合せ領域の分割
式(3.7)のように，各分割領域riは拡大領域Riを用いて表現できるので，問合
せ領域をどのように分割するかは，拡大領域をどのように表現するかによって決定 される．本論文では，拡大領域Riの計算式を定義することによって，領域の分割 方法を定める．具体的には，図3.11に示すように，ある基準点と領域分割の幅に 基づき問合せ領域を分割するものとする．
矩形問合せQrectについては，その問合せ領域を次のパラメータに基づき分割す る (図 3.11 (a))．
• 領域分割の基準点：(xbase, ybase)
• x軸方向の分割幅：dx+(≥0), dx−(≤0)
• y軸方向の分割幅：dy+(≥0), dy−(≤0)
1日本には，19個の平面直角座標系が存在する．
2日本測地系から世界測地系への移行に伴い，現在の刊行区分とは異なっている．
x
y
dradius
(b) circular query
( x , y ) center center
x
y
dx+
dx-dy- dy+
(a) rectangle query
( x , y )base base
図 3.11: 基準点と分割幅を指定した時の問合せ領域の分割：(a)矩形問合せQrect，
(b)距離に基づく範囲問合せQcircle
これらの分割パラメータを利用して，拡大領域Ri(1≤i≤k)を式(3.10)に示すよ うに計算する．
Ri = hmax(xbase+dx−×i, xmin), max(ybase+dy−×i, ymin),
min(xbase+dx+×i, xmax), min(ybase+dy+×i, ymax)i (3.10)
min(a, b)は，aとbとを比較し最小値を返す関数であり，max(a, b)は，最大値
を返す関数である．
一方，距離に基づく範囲問合せQcircleについては，半径方向の分割幅(dradius)を 用いて，その問合せ領域を分割する(図 3.11 (b))．領域分割の基準点は円の中心
(xcenter, ycenter)とし，拡大領域Riを式(3.11)に示すように計算する．
Ri =
( hxcenter, ycenter, dradius×ii 1≤i < k の時
hxcenter, ycenter, radiusi i=kの時 (3.11)
これらの式によって計算される拡大領域Riは，式(3.5)，(3.6)に示す条件を満た し，ある点を基準としてデータ収集領域を拡大させていくことができる．
なお本研究では，これらの領域分割のためのパラメータは，クライアントがサー バに送信するクエリに検索範囲とともに指定されるものとする．すなわち，ユー ザの要求に応じた領域分割を行うためのパラメータがクライアント側で指定され，
サーバは，その分割パラメータに基づき領域分割を行い，その探索結果を逐次的に クライアントに提供する．たとえば，ユーザの周辺の地図データをユーザに近い位 置から表示する場合には，式(3.11)に示す分割パラメータを利用し，基準点として ユーザの位置を指定すればよい．また，ユーザの移動あるいは地図のスクロールと いった動作に合わせて地図データを取得する場合には，式(3.10)に示す分割パラ メータを利用し，移動方向に応じた分割幅の指定が可能である．
3.3.4 検索結果のタグ付け
図3.12に，本実装で用いたXML表現のためのDTD (Document Type
Defini-tion)を示す．線データおよびポリゴンデータは，それぞれ <line>タグおよび
<polygon>タグによって記述される．図3.13に，図3.12に示したDTDに基づく 空間データの記述例を示す．
<!ELEMENT spatial-data (line|polygon)*>
<!ELEMENT line (id?,((x,y),(x,y)))>
<!ELEMENT polygon (id?,((x,y),(x,y),(x,y)+))>
<!ELEMNET x (#PCDATA)>
<!ELEMENT y (#PCDATA)>
図 3.12: 空間データ表現のためのDTD
<spatial-data>
<line>
<x>-50997.8</x><y>-16011.8</y>
<x>-50996.8</x><y>-16008.8</y>
</line>
<line>...</line>
...
</spatial-data>
図 3.13: XMLによる空間データの記述例
3.3.5 地図描画アプリケーション
3.3.1節の空間データ提供システムをサーバとするクライアントとして，地図描
画プログラムを作成した．この地図描画クライアントは，起動時にサーバとのTCP コネクションを確立し，そのコネクションを介してサーバに対してデータ要求を行 い，サーバからの検索結果を受信する．描画クライアントは，XMLによって表現 された検索結果から空間データを抽出し，そのデータに基づき地図の描画を行う．
なお，XMLパーサとしては，SAX (Simple API for XML)を利用した．