WEKO3
アイテム
大規模データ処理のための簡潔データ構造
https://ipsj.ixsq.nii.ac.jp/records/65880
https://ipsj.ixsq.nii.ac.jp/records/65880167f957b-48a0-4b17-b002-346ad37019d2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MGN480815.pdf (494.0 kB)
|
Copyright (c) 2007 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Magazine(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2007-08-15 | |||||||
| タイトル | ||||||||
| タイトル | 大規模データ処理のための簡潔データ構造 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Succinct Data Structures for Large-Scale Data Processing | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 解説 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | article | |||||||
| 著者所属 | ||||||||
| 九州大学大学院システム情報科学研究院 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu Univ. | ||||||||
| 著者名 |
定兼, 邦彦
× 定兼, 邦彦
|
|||||||
| 著者名(英) |
Kunihiko, SADAKANE
× Kunihiko, SADAKANE
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | データ列に対して検索効率などを効率化するため，索引を付加することがある．演算を効率化するために，データに対して特定の情報を付加したものを，ここではデータ構造と呼ぶこととする．本稿ではこのようなデータ構造のうち，もとのデータの長さnに対してo(n)程度の付加情報のみを与える，簡潔データ構造と呼ばれる分野について解説する．特に，最も基本的かつ応用範囲の広いビットベクトルに関する簡潔データ構造に焦点を当てる．ビットベクトルBに対して，先頭からi番目までのビット中の1の数を与えるrank1(B i)と，i番目の1の位置を与える select1(B i)という演算は，基本的かつ重要な演算である．これらの演算が定数時間で可能な簡潔データ構造について，具体的なデータ構造とアルゴリズムを紹介し，次に付加するデータサイズの下界についての結果を示し，最後に今後の展望について述べる． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116625 | |||||||
| 書誌情報 |
情報処理 巻 48, 号 8, p. 899-902, 発行日 2007-08-15 |
|||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
