著者

古川 隆久 吉原 潤 京極 典子

出版者

横浜市立大学学術研究会

雑誌

横浜市立大学論叢 人文科学系列 (ISSN:09117717)

巻号頁・発行日

vol.54, no.1, pp.395-431, 2003

著者

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

出版者

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

雑誌

情報処理学会研究報告データベースシステム(DBS) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.69, pp.41-48, 2000-07-26

---

suffix arrayはテキストの接尾辞のポインタを接尾辞の辞書順に並べたもので,任意の部分文字列検索を高速に行うことができるが,更新のオーバーヘッドが大きい.本論文ではsuffix arrayを効率的に更新する方式として,我々が以前提案したインクリメンタルな更新方式を分散並列化をした方式を提案する.この方式ではsuffix arrayに含まれる接尾辞を辞書順のある範囲で分割し,各ノードに担当区間を割り当てる.繰り返される更新に伴い各ノードの担当区間のサイズの不均衡が生じるため,動的に担当区間の変更を行ない更新処理の負荷を均等化する.また,単純に均等なサイズに分割して連続した区間をノードに割り当てた場合に検索要求の分布に偏りが生じることを示し,検索要求の偏りを軽減する分割方法を提案した.A suffix array is a full-text index data structure which is efficient for retrieving any substring of text, but requires a lot of overhead for updating it. In this paper, we propose an efficient updating scheme of suffix arrays. In this scheme, a suffix array is split into some sections and each section is assigned to a node. When updating, the incremental updating scheme which we already proposed runs in parallel on each node. To balance the sizes of sections after repeated updating, boundaries of sections are changed dynamically. Furthremore we propose the spliting scheme of suffix arrays to balance the retrieval prosessing load.

著者

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

出版者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

高橋 慎 吉原 潤 加藤 和彦

出版者

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

雑誌

情報処理学会研究報告データベースシステム(DBS) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.70, pp.53-60, 2001-07-17

---

suffix arrayはテキストの接尾辞のポインタを辞書順に並べかえたもので,任意の部分文字列を高速に検索できるが,静的なデータ構造のため,更新のオーバーヘッドが大きい.我々は以前,インクリメンタルな更新方式を提案したが,この方式が残す問題の一つは,差分情報を用いて作成したsuffix arrayを一つにまとめる再構成処理のオーバーヘッドが大きいことである.本論文では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. 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.