| 講演名 | 2009-04-17 動的簡潔順序木 定兼 邦彦, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 動的な順序木に対する簡潔データ構造を提案する.簡潔データ構造とは,サイズが表現するデータの情報理論的下限に漸近的に一致するデータ構造であり,n節点の順序木に対する下限は2n-Θ(log n)ビットである.本論文のデータ構造は順序木に対する様々な問合せと,木構造の変更(節点の追加・削除)を効率よく実現する.2つのデータ構造があり,1つはサイズが2n+O(n/log n)ビットで全ての演算をO(log n)時間で行える.もう1つはサイズが2n+O(n log log n/log n)ビットで多くの演算をO(log n/log log n)時間,木構造の変更をO(log n)均し時間で実現する. |
| 抄録(英) | This paper proposes succinct data structures for dynamic ordinal trees. Succinct data structures are the ones whose size are asymptotically the same as the information-theoretic lower bounds of data, and the lower bound for n-node trees is 2n-Θ(log n) bits. Data structures of this paper efficiently support various queries and update operations (insertion/deletion of nodes) to ordinal trees. There are two types of data structures; the one is of size 2n+O(n/log n) bits and supports all operations in O(log n) time, and the other is of size 2n+O(n log log n/log n) bits and supports most of the queries in O(log n/log log n) time, and update operations in amortized O(log n) time. |
| キーワード(和) | 簡潔データ構造 / 順序木 / 括弧列 / 動的データ構造 |
| キーワード(英) | succinct data structures / ordinal trees / balanced parentheses sequences / dynamic data structures |
| 資料番号 | COMP2009-6 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2009/4/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 動的簡潔順序木 |
| サブタイトル（和） | |
| タイトル（英） | Dynamic Succinct Ordinal Trees |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 簡潔データ構造 / succinct data structures |
| キーワード(2)（和/英） | 順序木 / ordinal trees |
| キーワード(3)（和/英） | 括弧列 / balanced parentheses sequences |
| キーワード(4)（和/英） | 動的データ構造 / dynamic data structures |
| 第 1 著者 氏名（和/英） | 定兼 邦彦 / Kunihiko SADAKANE |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Department of Computer Science and Communication Engineering, Kyushu University |
| 発表年月日 | 2009-04-17 |
| 資料番号 | COMP2009-6 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 9 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |