P2Pネットワークにおけるスキップグラフと接尾辞配列を用いた部分一致検索手法
スポンサーリンク
概要
- 論文の詳細を見る
構造化オーバレイは，大規模なノード群におけるノード同士の自律分散的な相互検索を実現する技術であり，特に分散ハッシュテーブルとしての活用で知られている．しかし，従来の構造化オーバレイでは完全一致検索以外の高度な検索機能を実現し難いことが弱点とされてきた．部分一致検索もそのひとつであり，今までにキーをn-gramに分割する等いくつかの手法が提案されてきたが，それら既存手法では部分文字列の出現頻度偏りに弱くノード毎の負荷が偏ってしまう等の問題があった．そこで本稿では，範囲検索が可能な構造化オーバレイであるSkip Graphに，文字列検索に適したデータ構造である接尾辞配列の概念を組み合わせた新しい部分一致検索手法を提案する．提案手法及び既存手法の双方についてシミュレーション実験を実施することで，提案手法がノード数Nに対しO(log N)の検索時間を達成しつつ，従来手法で問題となっていたノード負荷の偏りを解消する等多くの利点を持つことを確認した．
- 日本ソフトウェア科学会の論文
日本ソフトウェア科学会 | 論文
- LCDと透明弾性体の光弾性を用いたユーザインタフェース (特集 インタラクティブシステムとソフトウェア)
- Bluetoothによる位置検出
- COINSにおけるSIMD並列化(最新コンパイラ技術とCOINSによる実践)
- データ型を考慮した軽量なXML文書処理系の自動生成(ソフトウェア開発を支援する基盤技術)
- 計算と論理のための自然枠組NF/CAL(システム検証の科学技術)