P2Pネットワークにおけるスキップグラフと接尾辞配列を用いた部分一致検索手法
書誌事項
- タイトル別名
-
- A Partial Match Retrieval Method on P2P Networks using Skip Graph and Suffix Array
抄録
構造化オーバレイは，大規模なノード群におけるノード同士の自律分散的な相互検索を実現する技術であり，特に分散ハッシュテーブルとしての活用で知られている．しかし，従来の構造化オーバレイでは完全一致検索以外の高度な検索機能を実現し難いことが弱点とされてきた．部分一致検索もそのひとつであり，今までにキーをn-gramに分割する等いくつかの手法が提案されてきたが，それら既存手法では部分文字列の出現頻度偏りに弱くノード毎の負荷が偏ってしまう等の問題があった．そこで本稿では，範囲検索が可能な構造化オーバレイであるSkip Graphに，文字列検索に適したデータ構造である接尾辞配列の概念を組み合わせた新しい部分一致検索手法を提案する．提案手法及び既存手法の双方についてシミュレーション実験を実施することで，提案手法がノード数Nに対しO(log N)の検索時間を達成しつつ，従来手法で問題となっていたノード負荷の偏りを解消する等多くの利点を持つことを確認した．
収録刊行物
-
- コンピュータ ソフトウェア
-
コンピュータ ソフトウェア 29 (3), 3_164-3_180, 2012
日本ソフトウェア科学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001204738560000
-
- NII論文ID
- 130004549275
-
- ISSN
- 02896540
-
- 本文言語コード
- ja
-
- データソース種別
-
- JaLC
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可