- 著者
-
安積 裕樹
川副 真治
安部 潤一郎
有村 博紀
有川 節夫
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
- 巻号頁・発行日
- vol.42, no.14, pp.14-24, 2001-12-15
本稿では,分散記憶型並列計算機上での効率の良い全文索引構築法について考察する.接尾辞配列は,最近提案された高機能全文索引であり,情報検索や遺伝子情報などに広い応用を持つ.本稿では,分散記憶型並列計算機上での効率の良い接尾辞配列構築法を提案する.Baeza-Yates-Gonnet-Sinder(BGS )アルゴリズムは,最も広く使われている外部記憶上の構築アルゴリズムである.このBGSアルゴリズムを並列化し,効率の良い並列構築アルゴリズムを与える.このアルゴリズムは,並列計算機時間と通信量に関して,BGS の最適な並列化になっており,従来からあるBGS の並列版のRiberio-Kitajima-Ziviani (RKZ )アルゴリズムに比べてより高速である.In this paper,we study efficient parallel construction of full-text indexing structures for large text data.The suffix array is a compact full-text indexing structure that is useful in information retrieval and bio-informatics.We propose an efficient parallel algorithm for constructing suffix arrays on distributed memory parallel computers.This algorithm is a parallel implementation of the well-known external memory algorithm,called Baeza-Yates-Gonnet-Sinder (BGS)algorithm.By theoretical analysis,we show that our algorithm runs more efficiently than Riberio-Kitajima-Ziviani (RKZ) algorithm,another parallel implementation of the BGS algorithm,in terms of parallel time and communication complexities.