P2Pネットワークにおけるスキップグラフと接尾辞配列を用いた部分一致検索手法

DOI
  • 坂野 遼平
    北海道大学大学院情報科学研究科(現在,日本電信電話株式会社NTT未来ねっと研究所)
  • 佐藤 晴彦
    北海道大学大学院情報科学研究科
  • 小山 聡
    北海道大学大学院情報科学研究科
  • 栗原 正仁
    北海道大学大学院情報科学研究科

書誌事項

タイトル別名
  • A Partial Match Retrieval Method on P2P Networks using Skip Graph and Suffix Array

抄録

構造化オーバレイは,大規模なノード群におけるノード同士の自律分散的な相互検索を実現する技術であり,特に分散ハッシュテーブルとしての活用で知られている.しかし,従来の構造化オーバレイでは完全一致検索以外の高度な検索機能を実現し難いことが弱点とされてきた.部分一致検索もそのひとつであり,今までにキーをn-gramに分割する等いくつかの手法が提案されてきたが,それら既存手法では部分文字列の出現頻度偏りに弱くノード毎の負荷が偏ってしまう等の問題があった.そこで本稿では,範囲検索が可能な構造化オーバレイであるSkip Graphに,文字列検索に適したデータ構造である接尾辞配列の概念を組み合わせた新しい部分一致検索手法を提案する.提案手法及び既存手法の双方についてシミュレーション実験を実施することで,提案手法がノード数Nに対しO(log N)の検索時間を達成しつつ,従来手法で問題となっていたノード負荷の偏りを解消する等多くの利点を持つことを確認した.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1390001204738560000
  • NII論文ID
    130004549275
  • DOI
    10.11309/jssst.29.3_164
  • ISSN
    02896540
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • CiNii Articles
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ