| 講演名 | 2006-06-23 単純なRank/Select辞書 定兼 邦彦, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Rank/Select辞書とは,順序集合S⊂{0,1,…,m-1}においてrank(x,S)=|{y∈S|y≦x}|)とselect(i,S)(Sの中でi番目に小さい要素)を返すデータ構造である.これは文字列,木,グラフなどの圧縮データ構造の基本構成要素であり,多くのデータ構造が提案されている.しかしそれらは漸近的な性能のみを考えており,実データに対する性能は良くない.本研究では単純なRank/Select辞書を提案する.特徴としては,集合Sの要素数が小さい場合にデータ構造のサイズを縮小できることと,データ構造が単純であるために実装が容易で,実データに対する性能(データ構造のサイズと問い合わせ時間)が良い.実験により,既存の実装よりも速度,サイズともに優れていることを示す. |
| 抄録(英) | Rank/Select directories are data structures to compute, for an ordered set S ⊂{0, 1,...,m-1}, rank (x, S)=|{y∈S|y≦x}|) and select (i, S) (the i-th smallest element in S). These are basic components of succinct data structures to store strings, trees, graphs, etc., and many data structures for them have been proposed. However, in those data structures only asymptotic behavior is considered and their performance for real data is not satisfactory. In this paper, we propose simple Rank/Select directories. Advantages of them are: (1) the size of the data structure is small if the number of elements in S is small, (2) the data structure is simple, thus the performance for real data is superior in terms of size and query time. Experimental results show our data structure is superior to existing implementations in both size and query time. |
| キーワード(和) | 圧縮データ構造 / rank / select / 実装 |
| キーワード(英) | succinct data structures / rank / select / implementation |
| 資料番号 | COMP2006-23 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2006/6/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 単純なRank/Select辞書 |
| サブタイトル（和） | |
| タイトル（英） | Simple Rank/Select Directories |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 圧縮データ構造 / succinct data structures |
| キーワード(2)（和/英） | rank / rank |
| キーワード(3)（和/英） | select / select |
| キーワード(4)（和/英） | 実装 / implementation |
| 第 1 著者 氏名（和/英） | 定兼 邦彦 / Kunihiko SADAKANE |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Department of Computer Science and Communication Engineering, Kyushu University |
| 発表年月日 | 2006-06-23 |
| 資料番号 | COMP2006-23 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 128 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |