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

• Item type: SIG Technical Reports(1)
• 公開日: 2001-07-17
• タイトル: インクリメンタルな更新機構を持つ全文検索インデックスの分散並列処理方式
• タイトル / 言語: en
• タイトル: Distributed Parallel Processing Scheme of a Full - Text Index Structure with Incremental Updating
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 筑波大学大学院 理工学研究科
• 著者所属: 筑波大学大学院 理工学研究科（2001年3月まで）
• 著者所属: 筑波大学電子・情報工学系
• 著者所属(英): en
• 著者所属(英): Master's Program in Science and Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Master's Program in Science and Engineering, University of Tsukuba (Until 2001 March)
• 著者所属(英): en
• 著者所属(英): Institute of Information Science and Electronics, University of Tsukuba
• 著者名: 高橋, 慎; 吉原, 潤; 加藤, 和彦
• 著者名(英): Makoto, Takahashi; Jun, Yoshiwara; Kazuhiko, Kato
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: suffix arrayはテキストの接尾辞のポインタを辞書順に並べかえたもので，任意の部分文字列を高速に検索できるが，静的なデータ構造のため，更新のオーバーヘッドが大きい．我々は以前，インクリメンタルな更新方式を提案したが，この方式が残す問題の一つは，差分情報を用いて作成したsuffix arrayを一つにまとめる再構成処理のオーバーヘッドが大きいことである．本論文では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. One of the remaining problems is the overheads to reconstruct large suffix arrays. Frequency of the reconstruction operation is reduced in the incremental updating scheme, but 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 reconstruction overheads are reduced and throughput for the retrieval operations is increased. We show some experimental results performed to evaluate the proposed scheme.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2001, 号 70(2001-DBS-125), p. 53-60, 発行日 2001-07-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会