対話的な絞込み操作を考慮した P2P による Gfdnavi の横断検索
齋藤 真衣（指導教員：渡辺 知恵美）

1

はじめにサーバとして利用する場合は DHT に登録しなければ他から横断検索されることはない. また DHT 登録時にアクセス制御を考慮し，一部でのリソース共有を実現する.

近年の地球観測と計算機の進展による大気や水質などの数値データの爆発的増加に伴い科学者個人が管理するデータも増加し，気軽に自分の計算機に蓄積されたデータを検索したり，同様の研究をする科学者にデータを公開したりしたいという要求が高まってきた. そこで我々はリレーショナルデータベース (RDB) を用いた地球流体データアーカイブサーバを比較的容易に作成することができる Gfdnavi を開発している. 本稿では Gfdnavi における横断検索について述べる．

2.3

先行研究

2

前提知識

先行研究 [2] では，2 段階の処理を経て問合せを実行した．まずユーザが指定する空間条件とキーワードをキー，その条件を満たすノードを値として DHT に登録して，該当データを所持するノードを DHT で特定する．また各 Gfdnavi サーバには SQL を受け付けその結果を返す
Web サービスを起動しておき，該当ノードに対し SQLを発行する．

2.1

DHT(Distributed Hash Table)

3

Gfdnavi ではメタデータ variable に対する属性が定義されており，ユーザは各属性リストから条件を指定して検索を進める. 本研究では Gfdnavi に新しく加わる「探索的検索インタフェース (以下 Gfdexplorer と呼ぶ)」を，横断検索時も利用できることを目的とする．既存 Gfdnavi
では空間属性に対してのみ探索的検索ができるが，時間,キーワード属性に対しても探索的検索が行えるよう現在Gfdexplorer が開発されている．Gfdexplorer ではデータの属性値をもとにグルーピングをし，表示されたリストからユーザが選んだ一つを条件に問い合わせ，データを絞り込んで結果を出力する.
DHT での検索のために考えるべきことは何をキーと値にするかである．Gfdexplorer では検索対象のデータセッ
トの概要情報 (主要キーワード属性名と各々のキーワー
ド属性のとり得る主要な値，空間属性，時間属性) がリストアップされており，そのいずれかをクリックするとその値で絞込み検索が実行され，結果データセットの概要情報が表示される．そこで横断検索では概要情報に表示されている全ての要素をキーとし，各キーをクリックした時に表示されるキーワードリスト，結果データセッ
ト情報，さらに絞込みのためのビット配列を値とする.

Gfdnavi の横断検索では分散ハッシュテーブル (DHT)を採用している．DHT はハッシュ関数で算出したキーとそれに対応する値の組を格納したハッシュテーブルをネットワークに参加したノードで分散して管理し，その分散されたハッシュテーブルを辿って効率的に検索する手法である．ノードがネットワークに参加すると一意なID が付与され，ノードの公開データ情報 (メタデータ) がハッシュ関数を用いて生成される．メタデータは「データを特定するもの」をキー，「該当するデータもしくはその所在地」を値とする組である．各ノードは自分の ID と同じ，もしくは近隣のキー値のハッシュテーブル，ネッ
トワーク上の幾つかの他ノードの所在情報 (スキップリスト) を管理する．検索時は検索データのハッシュ値を算出し，所在を知るノードのうち探しているハッシュ値に最も近い値の ID を持つノードへ探索依頼を送る．DHT
では (キー，値) のペアを指定して DHT に登録する put，キーを指定してそれに対応する値を返す get がある．
2.2

Gfdnavi における横断検索

Gfdnavi で想定される状況

Gfdnavi はスタンドアロン型の科学データ分析ツールとして利用できるが，同じインタフェースのまま Web コンテンツとして一般に公開することもできる. さらに横断検索導入により，Web サーバとしては公開せず P2P で仲間うちで利用することも想定される. 図 1 に Gfdnaviで想定される状況を示す. リソースを一般公開する場

4

DHT のデータ構造と処理

4.1

キーワード属性リストの表示と絞込み

Gfdexplorer ではユーザがリストから条件を指定すると，それを満たすリストとその件数を返すが，横断検索で問題となるのは複数条件による絞込みを行う場合である. そこで各 variable が条件を満たすか満たさないかを1 と 0 だけのビット値で表したビット配列を用いる. まずユーザが検索条件に指定し得る属性名，その属性値それぞれに対して variable の数だけビット列を用意し，各ビットは各 variable id に順に対応させる. ここで絞込み結果をもとにキーワード属性のリストとその件数を求める必要があり，その該当件数取得の流れを図 3 に示す.
ある属性のビット列，キーワードリストをクライアント側が所持し，そのリストから共通する属性について絞り込むこととする. リストとその件数から複数条件による絞込み結果を見積もることはできるが，実件数は求められない. この場合クライアント側のビット列をキーにDHT に問い合わせ，条件を加えたビット列をもとに該当件数を計算する必要があるが，クライアント側でビット

図 1: 想定される状況
合，Web サーバを起動し DHT に登録することで全ての Gfdnavi から横断検索が可能になり，単体の Gfdnavi

5満たすものとし，各ビット列を参照する (図 4). まず緯度経度ごとにビットの論理和をとって該当 variable を求め，次に緯度経度共に条件を満たす variable を論理積で求めると空間絞込みができる. 時間属性においても年，月，日毎にビットで絞り込む.

5

Gfdnavi は Ruby on Rails を拡張し，データカイブサーバ構築を支援するパッケージである．横断検索部では P2P
ネットワークルーティング及び分散ハッシュテーブルの管理・制御に Java によって実装された OverlayWeaverを利用するため，Ruby から Java のクラスを呼び出すラ
イブラリ RJB(Ruby Java Bridge) を用いてデータ検索部との連携を図る．

図 2: キーワード属性における絞込み検索

5.1

DHT への登録・DHT を用いた検索

まず検索対象データセットからユーザが検索条件に指定する DHT のキーと，それに対応する値を生成する．ここで DHT に登録する値のうちブラウザ上で表示される
結果リストはこの段階では複数の情報をまとめて格納している型であるため，これを文字列に変換してからキーと値の組が DHT へ登録される．
次に横断検索時には step1 として検索条件の属性名がパラメータとして取得され，DHT のキーが生成される．
そこで Ruby で実装されている横断検索モジュールからRJB で OverlayWeaver を呼び出し，キーに対応する値を get する．取得された値は検索結果として表示できるように変換される．step2 では step1 の表示結果に対して該当件数を取得したい場合，該当件数を求める処理が行われる.

図 3: 該当件数取得の流れ列をすべて取得してくるのはコストが高い. そこで我々は，ビット列を置いてあるノードで該当件数処理をする
getcount 関数を以下のように定義する.
int getcount(key,bitmap)
検索条件とクライアントが所持するビット列をキーとし，次の絞込み条件を満たすビット列をもとに該当件数を値として返すものとする.

4.2

実装

5.2

暗号化によるアクセス制御

Gfdnavi では一部のユーザのみにデータを公開したい状況が想定されるため，データ共有のためのグループを設定し，グループ単位のアクセス制御を実現する．まずグループごとに鍵を用意し，データの所在を示す DHTの値を暗号化する．DHT のキーにグループ名も加え, グループに属していれば値を復号化して検索結果が表示される. またデータそのものの取得には，データ所有ノードにログインするアカウントを要する．

オブジェクト・空間属性・時間属性

結果データセット情報を表示させるには variable id をキー，オブジェクトの id を値として DHT に登録し，オブジェクトの基本情報を取得できるようにする. 各属性について検索を進めるとビット配列から該当 variable idが割り出されるので，ビットの位置情報をキーとし，基本情報，ノード id，名前，パス，description を値として登録する. 空間属性においては緯度経度をそれぞれ 10度ずつに切り分け，各々ビット列を用意する. ユーザが6まとめと今後の課題

Gfdnavi で扱うデータは膨大であり，クライアントサーバ方式ではサーバを設けるコストや帯域の圧迫の問題がある．そこで Gfdnavi の横断検索を P2P で実現しようと考えた．今後は Gfdnavi への組込みに向け，ネットワーク上に分散するデータ量の増加等の問題に関して更なる考察を進めていきたい.

参考文献[1] 地球流体電脳倶楽部: http://www.gfd-dennou.org/[2] 佐藤麻美, 渡辺知恵美： P2P を利用した地球物理データのネットワーク横断検索・共有システムの実現に向けて,
第 18 回データ工学ワークショップ (DEWS2007),D1-9.
[3] R. Huebsch, J. Hellerstein, N. Lanham, B. T. Loo, S.
Shenker, and I. Stoica.:
Querying the Internet withPIER, In Proc. the 29th International Conference on
Very Large Data Bases, pp. 321–332, September 2003.
[4] 齋藤真衣, 堀之内武, 渡辺知恵美： 対話的な絞込み操作を考慮した P2P による地球流体データアーカイブサーバの横断検索, 第 19 回データ工学ワークショップ (DEWS2008).(投稿中)

図 4: 空間属性における絞込み
指定した空間の緯度経度の範囲を一部でも含めば条件を6