文献

J-GLOBAL ID：201302294211118995   整理番号：12A1812172

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

A Partial Match Retrieval Method on P2P Networks using Skip Graph and Suffix Array

著者 (4件)： 坂野遼平 (北海道大学大学院情報科学研究科(現在,日本電信電話株式会社NTT未来ねっと研究所)) ,  佐藤晴彦 (北海道大学大学院情報科学研究科) ,  小山聡 (北海道大学大学院情報科学研究科) ,  栗原正仁 (北海道大学大学院情報科学研究科)
資料名： コンピュータソフトウェア  (Computer Software)
巻： 29  号： 3  ページ： 3.164-3.180 (J-STAGE)  発行年： 2012年 
JST資料番号： Y0628A  ISSN： 0289-6540  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： インターネット ,  *情報検索 ,  文法 ,  オーバレイ【計算機】 ,  表 ,  インデクシング【計算機】
準シソーラス用語： Nグラム ,  ハッシュテーブル ,  ピーツーピーネットワーク ,  接尾辞 ,  *部分一致検索 ,  *文字列検索

分類 (1件)： 検索技術  (AC06020S)

タイトルに関連する用語 (4件)： P2Pネットワーク ,  接尾辞 ,  一致検索 ,  手法