範囲検索が可能なSkip Graph
P2Pの検索技術ならRFC4981で宣言したように、Skip Graphについての論文を適当に読んだのでまとめ。
既存のDHTの問題点
Chord・Pastry・CANといったDHTは、keyをハッシュしてスケーラビリティと負荷分散を実現
↓
ハッシュのせいでkeyの順序が崩れ、範囲検索が困難
Skip Graphなら範囲検索が可能
Keyをハッシュしないため、範囲検索が可能になるとのこと。
論文内の図などは、大阪大学工学部 電子情報エネルギー工学科 の小西さんが書かれたスライドを見るとよいと思う。
keyの探索アルゴリズムは以下のように行われる。
Algorithm 1: search for node n
upon receiving (searchOp, startNode,level): if n.key = searchKey then send (search0p, n) to startNode if n.key < searchKey then while level > 0 do if (nRlevel ).key < searehKey then send (search0p, startNode,level) to nRlevel break else level <- level-1 else while level > 0 do if (nLlevel).key > searchKey then send (search0p, startNode,level) to nLlevel break else level <- level-1 if level < 0 then send (search0p, n) to startNode
このアルゴリズムではkeyに一致したときと探索に失敗したときにstartNodeへsendするが、
範囲検索の場合はkeyが範囲内に一致したときにstartNodeへsendするようにアルゴリズムを変更すれば範囲検索ができる(?)
