講演抄録/キーワード |
講演名 |
2009-04-17 14:40
動的簡潔順序木 ○定兼邦彦(九大) COMP2009-6 |
抄録 |
(和) |
動的な順序木に対する簡潔データ構造を提案する.
簡潔データ構造とは,サイズが表現するデータの情報理論的下限に漸近的に
一致するデータ構造であり,$n$ 節点の順序木に対する下限は $2n-\Theta(\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-\Theta(\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 $\Order(\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 / / / / |
文献情報 |
信学技報, vol. 109, no. 9, COMP2009-6, pp. 37-41, 2009年4月. |
資料番号 |
COMP2009-6 |
発行日 |
2009-04-10 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-6 |