インクリメンタルな更新機構を備えた全文検索インデックスの分散並列処理方式

• Item type: Trans(1)
• 公開日: 2003-08-15
• タイトル: インクリメンタルな更新機構を備えた全文検索インデックスの分散並列処理方式
• タイトル / 言語: en
• タイトル: Distributed Parallel Processing Scheme of a Full - Text Index Structure with Incremental Updating
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 並列処理アルゴリズムと評価
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学大学院修士課程理工学研究科
• 著者所属: 筑波大学電子・情報工学系
• 著者所属(英): en
• 著者所属(英): Master's Program in Science and Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Institute of Information Science and Electronics, University of Tsukuba
• 著者名: 高橋, 慎; 加藤, 和彦
• 著者名(英): Makoto, Takahashi; Kazuhiko, Kato
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Suffix arrayはテキストの接尾辞のポインタを辞書順に並べ替えたもので，任意の部分文字列を高速に検索できるが，静的なデータ構造のため，更新時のオーバヘッドが大きい．我々は以前，この問題を解決するインクリメンタルな更新方式を提案したが，この方式が残す問題点の1つは，インクリメンタルに追加される情報を用いて作成したsuffix arrayを既存の大きなsuffix arrayに結合する統合処理に依然大きな時間を要することである．本論文では繰返し的な更新処理や検索処理を高速に行うために，インクリメンタルな更新方式を分散並列化した方式を提案する．また，実装を用いた実験結果により，提案方式が更新処理の高速化と検索処理の性能向上に有効であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Suffix array is a full-text index structure efficient to retrieve any substring of the indexed text, but requires significant overheads to update. Previously we proposed an incremental updating scheme for suffix arrays to solve this problem. One of the remaining problems is the overheads to integrate adding suffix array and existing large suffix array in update operation. Frequency of the integrate operation is reduced in the incremental updating scheme, but it still requires considerable overheads. This paper presents a scheme to incorporate parallel and distributed processing into the incremental updating scheme. In the scheme, decomposed suffix arrays are distributed to several machines, so that the integration overheads are reduced and throughput for the retrieval operations is increased. We show some experimental results conducted to evaluate the proposed scheme.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 44, 号 SIG11(ACS3), p. 268-276, 発行日 2003-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会