著者

高橋 慎 加藤 和彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.44, no.11, pp.268-276, 2003-08-15

---

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.