DHTでデータベースを検索したりする研究

PIER

PIER [22, 23, 24] はインターネット規模で動作する大規模分散クエリー・エンジンであり、特に現在のStructured P2P の弱点とされている高度なクエリーを可能にする点で注目されている。

(http://dspace.info.gscc.osaka-cu.ac.jp/~fujita/RESEARCH/LC2006/main.pdf Chord/DHashを活用したデータベースの分散化)

PIERはDHTを利用してネットワーク上のノードが持つデータベースを検索するシステムである．
- 各ノード上にあるデータは全て共通のグローバルスキーマで定義されていることを想定する．
  - これはネットワーク監視システムのようにデータの標準フォーマットがある程度定まっているものや，P2P 上の各ノードが同じアプリケーションを利用することを想定しているからである．
具体的な検索方法は
- まずノードが持つテーブルの各タップルについて，テーブル名，属性名，属性値をまとめてハッシュ化したものをキー，テーブル名，タップル番号，所持ノードのIP アドレスといったタップルの所在情報（もしくはタップルそのもの）を値としてその組をDHT に分散させておく．
  - 例えばIP アドレスが123.45.67.89 であるノードのリレーション社員(ID，名前，出身地) に(012，佐藤有美，奈良) という挿入タップルがある時，以下のキーと値を分散ハッシュテーブルに登録する．
  - key = hash(" 社員; ID; 012")，
  - value = (" 123.45.67.89; 社員; 012")
  - key = hash(" 社員; 名前; 佐藤")，
  - value = (" 123.45.67.89; 社員; 012")
  - key = hash(" 社員; 出身地; 奈良")，
  - value = (" 123.45.67.89; 社員; 012")
PIER の問合せ処理では，
- DHT による選択演算に加え，
- 等結合のための基本アルゴリズムに対称ハッシュ結合とフェッチ結合を提案し，またいくつかの最適化手法を提案している．
前述の社員テーブルと給与(ID，社員ID，給与) テーブルを「社員.id=給与.id」という条件で対称ハッシュ結合で結合する場合，
- 結合した後の中間テーブルをNq とし，結合する属性値を用いてハッシュ値をDHT に登録する．
  - この時，結合する社員テーブルのタップルと給与テーブルのタップルは同じkey 値を持つため同じノードで管理される．
  - そこで各ノードは各々のハッシュテーブルにある同一のハッシュ値のタップルを結合して問合せを発行したノードへ返すことにより結合結果が求められる．

(http://www.ieice.or.jp/iss/de/DEWS/DEWS2007/pdf/d1-9.pdf P2Pを利用した地球物理データのネットワーク横断検索・共有システムの実現に向けて)

PIER は
- DHTを利用してネットワーク上のノードが持つデータベースを検索するシステムである．
- 各ノード上にあるデータは全て共通のグローバルスキーマで定義されていると想定している．
ノードが持つテーブルの各タップルについて，テーブル名，属性名，属性値をまとめてハッシュ化したものをキー，テーブル名，タップル番号，所持ノードのIP アドレスといったタップルの所在情報（もしくはタップルそのもの）を値としてその組をDHT に分散させることにより，DHT による選択演算を実現する．
- またPIER の問合せ処理では，結合など関係代数演算に必要な各演算処理を定義している．

(http://siio.jp/pdf/grad/2006/2006grad47.pdf P2P を利用した地球流体データアーカイブサーバ横断検索の試み)

RDFPeers

Cai 等のRDFPeers は，
- RDF トリプル[7] の主語，述語，目的語を，それぞれのDHT に格納することにより，RDF トリプルのための検索機構を提案している[8]．
- 具体的には，分散ハッシュ表を用いてRDF トリプルの格納および検索を実現する分散RDF データベースで，主語，述語，目的語のそれぞれをキーとし，RDF トリプルをその値として分散ハッシュ表に格納する手法である．
- すなわち，一つのトリプルを格納するには3 回の探索が必要で，逆に，主語，述語，目的語のいずれかが決定できれば，それをキーとすることで，その要素を含むトリプルを検索できる．

(http://www.cs.tsukuba.ac.jp/H18Syuron/200521012.pdf 構造型P2PネットワークにおけるXMLデータの検索に関する研究)

Resource Description Framework9)（RDF）ドキュメントを対象にし，RDF triple をDHTで分散させて保持するシステムを構築している．
- ここでは，triple 内のAND 検索時におけるトラフィック量を削減するために，triple 内のそれぞれのキーワードと共に，triple そのものも登録している．
- triple 内の要素は3 つしか存在しないので，AndSearch データ量は少量に抑えられているが，全文検索等，DHTのキーと成る要素がコンテンツに大量に含まれているときは，AndSearch データ量が膨大になってしまう．

(http://honiden-lab.ex.nii.ac.jp/archives/jaws2005-sei.pdf 分散ハッシュテーブルにおけるAND検索時のトラフィック量削減)

Resource Description Framework (RDF) [5] は
- メタデータ記述のための枠組みであり，柔軟で高度な表現能力を提供するものとして大きな期待が寄せられている．
- RDF は様々な応用分野で広く利用され始めており，そのデータはネットワーク上に散在して増加している．
  - そのため，分散した大量のRDF データに対して効率的に検索することが重要となってきた．
分散ハッシュ表によるRDF トリプル検索を提供しているが，RDF トリプルの結合演算を考慮した設計になっていない．
提案索引をRDFPeers [1] の索引として利用することとした．
- これによって，検索時のlookup の回数を減少させることができる．
- なお，RDFPeers で提案索引を利用する場合も，RDFPeersのための分散ハッシュ表と提案索引のためのRDFCube DHT の二つの分散ハッシュ表を用いることになる．
- 検索の流れを述べる．
  - 1) 与えられた問合せトリプルが写像されるセルの集合を決定し，
  - 2) それらのビット集合を取得する．
  - 3) そのビット集合の論理積を行なう．ここまでは，前節の場合とまったく同じである．最後に，
  - 4) 問合せトリプルの定数である一つの要素をキーとしてRDFPeers の分散ハッシュ表に対してlookup 検索を行う．この処理は従来のRDFPeers の問合せ処理である．従来のRDFPeers 問合せ処理では，この値を解の候補としてそのまま問合せが発行されたノードに転送する．しかし，
  - 5) 本索引を用いる場合，これらの解候補から，論理積の結果のビットが1 であるセル内に写像されるトリプルのみになるようにフィルタリングして，その結果をノードに転送する．これにより，結合演算を含む問合せの時に，解候補を転送前に減少させることができ，不要なデータ転送量を減少させることができる．

(http://www.dbsj.org/Japanese/DBSJLetters/vol4/no4/matono.pdf RDFCube:分散RDFデータ)

GridVine

Gridvine: Building internet-scale semantic overlay networks (2004)
GridVine: an infrastructure for peer information management (2007)

セマンティックオーバレイネットワーク
- コンテンツの意味的な関連に基づくピアによって形成される．クエリーを適切なSONs に伝送することにより，検索式を満たすファイルをより高速に発見し，無関係なコンンテンツを持つノードの負荷を軽減する．

(http://www.ai-gakkai.or.jp/jsai/conf/2007/data/pdf/100025.pdf )

SONs ではピアの保持しているコンテンツを考慮し，コンテンツのカテゴリ別にネットワークを形成する．
- 具体的にはピアを，保持しているコンテンツの種類を基に，あらかじめ用意されている意味的なカテゴリに分類する．
- その上で，ピアが，カテゴリごとにネットワークを形成し，ユーザはコンテンツ，クエリを，同じカテゴリのピアへ投入する．
各カテゴリのピア数，コンテンツの種類数が少ない時は非常に効率が良い．
- そのため，流通するコンテンツが明確にカテゴリに分けられるときは有効な手段といえるが，カテゴリを事前に用意しておく必要があり，また，各カテゴリに対応する，ピアの数，コンテンツの数が多いと効果が期待できない．

(http://www.ieice.or.jp/iss/de/DEWS/DEWS2007/pdf/b9-8.pdf Webコンテンツの偏在性に着目したP2Pコンテンツ流通システム)- SONs ではピアのもつ情報を考慮し，情報のジャンル別にネットワークを形成する．

- SONs では情報のファイル名とその情報に対応するジャンル名を格納するデータベースが存在する．
- このデータベースを参照することにより，情報に対応するジャンルを一意に決定することができる．
  - なおジャンルはroot，style，substyle の順に階層化されており，それぞれSON が形成される．
- ピアが情報を検索する際にはまず，検索する情報の属するジャンルを決定し，そのジャンルと一致するsubstyle のSON，style のSON，root のSON の順に，検索に該当する情報が見つかるまでクエリが転送され，それぞれのSON 内ではフラッディングされる．
この手法は，扱う情報をジャンル毎に明確に分類でき，各SON に参加するピア数が小規模である場合には，検索精度は向上し，トラフィック量を抑えることできる．
- しかし，ジャンルに分類できないような情報を扱う場合にはこの手法を適用できない．

(http://www.ieice.org/~de/DEWS/DEWS2006/doc/2B-o3.pdf 応答転送状況に基づいたP2Pネットワークのトポロジ再構築アルゴリズムの評価)

peer data management infrastructure
- スケーラブル
- 異種混合
  - PIERはグローバルなスキーマだけど

(http://lca2srv30.epfl.ch/aberer/PAPERS/Internet%20Computing08.pdf GridVine: an infrastructure for peer information management)

その他

Piazza

Piazza [20, 21] は、データベースのストレージをP2P により分散化するPeer Data ManagementSystem (PDMS) を提案している。

(http://dspace.info.gscc.osaka-cu.ac.jp/~fujita/RESEARCH/LC2006/main.pdf Chord/DHashを活用したデータベースの分散化)

PeerDB

PeerDB [25, 26] は小規模データベースをP2P により分散化する試みであるが、セマンティックス的調停のためにセントラル・ディレクトリ・サーバーを使用している。

(http://dspace.info.gscc.osaka-cu.ac.jp/~fujita/RESEARCH/LC2006/main.pdf Chord/DHashを活用したデータベースの分散化)

P-Grid

P-Grid[10] では，ピア同士が自発的に木構造を形成する．
- 全てのピアは保持しているデータを基に，検索に最適化された場所に配置される．
- ピアの配置場所は全て木構造の葉の部分となる．
- 検索に最適化されているため，検索の際に発生する検索要求メッセージを大幅に減らすことが可能[11] である．

(http://infonet.cse.kyutech.ac.jp/paper/2003/DaisukeMaruta-200402-Master.pdf P2Pネットワークにおけるストレージ負荷分散実現のための複製配置手法)

P-Grid ではデータの配置場所が各データのハッシュ値に応じて決定される．
- そのため各データを保持するピアのグループ内でFull-Replication が行われる．
- P-Grid でのデータ更新はChen 等[14] によって行われている．
- この方法ではLazy Group Replication でのデータ更新を行う．
  - 各ピアはそのピアが保持すべきデータに対する更新情報の検索と更新を行ったピアがそのグループに所属するピアにその更新情報を伝播させる2 フェーズでデータ更新の処理を行う．

(http://www.nii.ac.jp/graduate/thesis/pdf/yamada_Dr_thesis.pdf 適応的ピア発見による非構造Peer-to-Peerシステムの効率的な問い合わせ処理に関する研究)

P-Grid は，
- 仮想的な二分木をネットワーク上に構成し，二分木のルートからのパス情報を用いることで検索の効率化を計る．
各ノードは二分木のリーフ部分に配置される．
- ルートからノードまでのパス情報はバイナリで表現されており，ノードはパス情報の各プレフィックスに対応するノードをルーティング情報として保持している．
一方，データオブジェクトを一意に決定するオブジェクトID も同様にバイナリで表現されている．
- オブジェクトID による問合せが任意のノードから開始されると，オブジェクトID とノードのパスとが完全に合致しているかどうかを判断する．
- 完全に合致していれば，検索対象オブジェクトを当該ノードが持つこととなり，問合せ結果として開始ノードに返す．
- 完全に合致していなければ，ルーティング情報からオブジェクトID のプレフィックスと合致するノードへ問合せをフォワードする．
- この処理を繰り返すことによって検索が行われる．
  - 検索に必要なメッセージ数はO（log（N））である．

(http://www.jaist.ac.jp/DEWS2003/download/dews2003/8-C/8-C-03.pdf P2P環境におけるシグネチャを用いたオブジェクト検索)