#11 「Skip tree graphでモテたい」tech.kayac.com Advent Calendar 2012

こんばんわ,新卒1年目の@9renpotoです.

趣味は料理,FPS,格ゲー,音ゲーです.
元々webの人ではなかった身でこの業界に飛び込み,自分の能力の低さを常々感じております.

私の中のマイイノベーション 2012

本エントリはtech.kayac.com Advent Calendar 2012 11日目の記事になります.

社会人になってイノベーションを起こせていないので,
本日は学生時代にお世話になったOrdered Key-Valueアルゴリズムの1つ skip tree graph の拡張について書きます.

※この記事ではskip graphの説明を省いています.

Skip tree graph は Skip graphをベースとして,
Ordered Key-Valueの利点である範囲検索を効率よく行う仕組みを持っています.


Skip tree graphは上記のようなデータ構造を持っています.
簡単にではありますが,その構造について説明してきます.


Skip tree graphではSkip graph同様,
各ノードがKey(四角の中に表記)およびmemership vecterというw進数 の乱数(赤枠の中に表記)を保持しています.
(上記の図では3進数を使用)


Skip tree graphには複数の階層(レベル)があり,各ノードの持つmembership vectorの上位 i 桁同士が一致する ノードが同じ双方向連結リストに属しています.また,レベル 0 においてはすべてのノードが双方向連結リストを構成しています.


Skip tree graphはSkip graphのデータ構造に加え,Conjugate nodes(以下CNと表記)を保持しています. レベルLにおいて,ノードPの左ノードをQとするとき,PのレベルLでのCNは,レベルL−1におけるPとQの間に存在するすべてのノードへのポインタです.
上記図においてはKey60がレベル1において保持するCNはKey30,Key40,Key50です.


Skip tree graphはCNを用いて目的のノード検索を行います.
検索は最上位レベルから行い,CNの中で最も左方向で一番近いKeyを持つノードに対して検索クエリを転送します.
検索クエリを受取ったノードは,さらに自分のもつCNの中から最も左方向で近いKeyを持つノードに対して検索クエリを転送します.これらを繰り返すことによって目的のノードに到達します.


Skip tree graphでは構造を作成・維持するためにノード参加の際にSkip graphよりも多くのメッセージを必要とします.
(上記図内の赤い矢印がSkip graphには不必要であったメッセージ[1])


Skip tree graph では membership vectorの基数 w を増加させた場合,検索効率が向上するものの,
上記[1]でも述べたように,データ構造を構築するために多くのメッセージが必要となってしまいます.


提案手法では,Skip tree graphの参加・検索の際に利用されるメッセージを用いてCNを学習させます.
上記の図はノード検索時のメッセージを利用したCN学習の例です.


これによって,既存の手法でノード参加時に必要となっていたメッセージ数が提案手法により削減できていることが確認できました.


また各ノードが平均2回検索することで,既存のデータ構造で実現できる検索効率に近づけることが確認できました.

分散処理最高!

分散処理でワクワクするところは,stabilizeだと思います.
耐故障性に優れ,スケーラブルなデータ構造が構築できます.

P2Pは本当に面白いアルゴリズムなので一発当てたいです.

終わりに

説明非常に分かりにくく,大変申し訳ありません.
間違ってるよ,こうしたら良いよといった意見を絶賛募集しています.

資料

今回の記事で取り上げなかった内容

  • Skip graphの詳細
  • 範囲検索
  • DDLLの詳細
  • 近隣ノード集合の維持・新旧判定
  • ノードの同時参加・同時削除の場合
  • churn rateが高い場合
  • stabilize
  • メッセージあたりの必要バイト数
  • membership vecterの基数 w と近隣ノード集合数 n の関係,および最適な値

明日は

@shin1roseiさん素晴らしいお話です.お楽しみに!!