Presentation	2009-04-17 Dynamic Succinct Ordinal Trees Kunihiko SADAKANE,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	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.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	succinct data structures / ordinal trees / balanced parentheses sequences / dynamic data structures
Paper #	COMP2009-6
Date of Issue

Conference Information
Committee	COMP
Conference Date	2009/4/10(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Dynamic Succinct Ordinal Trees
Sub Title (in English)
Keyword(1)	succinct data structures
Keyword(2)	ordinal trees
Keyword(3)	balanced parentheses sequences
Keyword(4)	dynamic data structures
1st Author's Name	Kunihiko SADAKANE
1st Author's Affiliation	Department of Computer Science and Communication Engineering, Kyushu University()
Date	2009-04-17
Paper #	COMP2009-6
Volume (vol)	vol.109
Number (no)	9
Page	pp.pp.-
#Pages	5
Date of Issue