| 講演名 | 2000/7/19 DE2000-28 インクリメンタルな更新を伴う全文検索インデックスの分散並列処理方式 吉原 潤, 加藤 和彦, 奈良崎 清彦, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 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. Furthermore we propose the spliting scheme of suffix arrays to balance the retrieval prosessing load |
| キーワード(和) | suffix array / 分散並列処理 / 全文検索 |
| キーワード(英) | suffix array / distributed parallel processing / full-text search |
| 資料番号 | DE2000-28 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2000/7/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | DE2000-28 インクリメンタルな更新を伴う全文検索インデックスの分散並列処理方式 |
| サブタイトル（和） | |
| タイトル（英） | Distributed Parallel Processing Scheme of a Full-Text Index Structure with Incremental Updating |
| サブタイトル（和） | |
| キーワード(1)（和/英） | suffix array / suffix array |
| キーワード(2)（和/英） | 分散並列処理 / distributed parallel processing |
| キーワード(3)（和/英） | 全文検索 / full-text search |
| 第 1 著者 氏名（和/英） | 吉原 潤 / Jun Yoshiwara |
| 第 1 著者 所属（和/英） | 筑波大学大学院修士課程理工学研究科 Master's Program in Science and Engineering University of Tsukuba |
| 第 2 著者 氏名（和/英） | 加藤 和彦 / Kazuhiko Kato |
| 第 2 著者 所属（和/英） | 筑波大学電子・情報工学系:科学技術振興事業団 Institute of Information Science and Electronics University of Tsukuba:Japan Science and Technology Corporation |
| 第 3 著者 氏名（和/英） | 奈良崎 清彦 / Kiyohiko Narazaki |
| 第 3 著者 所属（和/英） | 筑波大学第三学群情報学類:(現)日立製作所 College of Information Sciences Third Cluster of Colleges University of Tsukuba |
| 発表年月日 | 2000/7/19 |
| 資料番号 | DE2000-28 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 226 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |