こんばんわ，新卒1年目の@9renpotoです．
趣味は料理，FPS，格ゲー，音ゲーです．
元々webの人ではなかった身でこの業界に飛び込み，自分の能力の低さを常々感じております．
私の中のマイイノベーション 2012
本エントリはtech.kayac.com Advent Calendar 2012 11日目の記事になります．
社会人になってイノベーションを起こせていないので，
本日は学生時代にお世話になったOrdered Key-Valueアルゴリズムの１つ 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さん素晴らしいお話です．お楽しみに!!
