Multi-key Skip Graph の仕組みを学ぶ - higepon blog「単一ピアに複数キーを保持可能とするSkip Graph拡張の提案」という論文で提案されている Multi-key Skip Graph を学ぶ。 大変苦労して読み解いたので、以下にまとめた事は間違っている可能性が高いので注意。 誤りがありましたらぜひご指摘ください。 背景 Skip Graph は 1 ノードに 1 (key, value) を保持する事が前提のアルゴリズム。 これでは効率の良い Key-value storage として使えないので 1 ノードに複数の (key, value) を保持できる Multi-key Skip Graph アルゴリズムを導入したい。 Multi-key Skip Graph 論文の解説を補うまとめ。 2 つの大事なポイントがある 1. 物理ピア毎に membership vector が発行される これにより各レベルでの検索が同一物理ピアで行
