著者

吉原 潤 加藤 和彦 奈良崎 清彦

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. DE, データ工学 (ISSN:09135685)

巻号頁・発行日

vol.100, no.226, pp.41-48, 2000-07-19

---

suffix arrayはテキストの接尾辞のポインタを接尾辞の辞書順に並べたもので, 任意の部分文字列検索を高速に行うことができるが, 更新のオーバーヘッドが大きい.本論文ではsuffix arrayを効率的に更新する方式として, 我々が以前提案したインクリメンタルな更新方式を分散並列化をした方式を提案する.この方式ではsuffix arrayに含まれる接尾辞を辞書順のある範囲で分割し, 各ノードに担当区間を割り当てる.繰り返される更新に伴い各ノードの担当区間のサイズの不均衡が生じるため, 動的に担当区間の変更を行ない更新処理の負荷を均等化する.また, 単純に均等なサイズに分割して連続した区間をノードに割り当てた場合に検索要求の分布に偏りが生じることを示し, 検索要求の偏りを軽減する分割方法を提案した.