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

• 高橋, 慎

• 加藤, 和彦

書誌事項

タイトル別名

• インクリメンタル ナ コウシン キコウ オ ソナエタ ゼンブン ケンサク インデックス ノ ブンサン ヘイレツ ショリ ホウシキ
• Distributed Parallel Processing Scheme of a Full - Text Index Structure with Incremental Updating

抄録

Suffix arrayはテキストの接尾辞のポインタを辞書順に並べ替えたもので，任意の部分文字列を高速に検索できるが，静的なデータ構造のため，更新時のオーバヘッドが大きい．我々は以前，この問題を解決するインクリメンタルな更新方式を提案したが，この方式が残す問題点の1つは，インクリメンタルに追加される情報を用いて作成したsuffix arrayを既存の大きなsuffix arrayに結合する統合処理に依然大きな時間を要することである．本論文では繰返し的な更新処理や検索処理を高速に行うために，インクリメンタルな更新方式を分散並列化した方式を提案する．また，実装を用いた実験結果により，提案方式が更新処理の高速化と検索処理の性能向上に有効であることを示す．

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.

収録刊行物

• 情報処理学会論文誌コンピューティングシステム（ACS）

  情報処理学会論文誌コンピューティングシステム（ACS） 44 (SIG11(ACS3)), 268-276, 2003-08-15

  東京 : 情報処理学会

キーワード

• 並列処理アルゴリズムと評価

詳細情報

• CRID: 1050564287846660992
• NII論文ID: 110002711993
• NII書誌ID: AA11833852
• ISSN: 18827829
• ISSN: 03875806
• NDL書誌ID: 6697537
• Web Site: http://id.nii.ac.jp/1001/00018551/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I6697537
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles