単一ピアに複数キーを保持可能とするSkip Graph拡張の提案(pdf)単一ピアに複数キーを保持可能とする Skip Graph 拡張の提案 小西 佑治 † 吉田 幹 ∗ 寺西 裕一 †† 春本 要 ††† 下條 真司 †† † †† 大阪大学大学院情報科学研究科 ∗ 株式会社ビービーアール 大阪大学大学院工学研究科 大阪大学サイバーメディアセンター ††† 概要 範囲検索に対応可能な構造化オーバレイネットワークである Skip Graph では，キーとそれを保持するピアが 1 対 1 に対応するため，単一ピアに複数のリソースが存在する場合，それらを検索の対象とすることができ ない．本研究では，単一ピアに複数キーを保持可能とする Multi-key Skip Graph を提案する．Skip Graph を 複数キーに対応するために，単一ピアに仮想的に複数ピアを構成すると，実際のピア数に対してホップ数が 増大してしまう問題がある．そこで，単一ピア
