Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/29103
Title: Dynamizing succinct tree representations
Authors: Joannou, Stelios
Raman, Rajeev
First Published: 9-Jun-2012
Presented at: Proceedings of the 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012.
Start Date: 7-Jun-2012
End Date: 9-Jun-2012
Publisher: Springer Berlin Heidelberg
Citation: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7276, pp. 224-235
Abstract: We consider succinct, or space-efficient, representations of ordinal trees. Representations exist that take 2n + o(n) bits to represent a static n-node ordinal tree - close to the information-theoretic minimum - and support navigational operations in O(1) time on a RAM model; and some implementations have good practical performance. The situation is different for dynamic ordinal trees. Although there is theoretical work on succinct dynamic ordinal trees, there is little work on the practical performance of these data structures. Motivated by applications to representing XML documents, in this paper, we report on a preliminary study on dynamic succinct data structures. Our implementation is based on representing the tree structure as a sequence of balanced parentheses, with navigation done using the min-max tree of Sadakane and Navarro (SODA '10). Our implementation shows promising performance for update and navigation, and our findings highlight two issues that we believe will be important to future implementations: the difference between the finger model of (say) Farzan and Munro (ICALP '09) and the parenthesis model of Sadakane and Navarro, and the choice of the balanced tree used to represent the min-max tree.
DOI Link: 10.1007/978-3-642-30850-5_20
ISSN: 0302-9743
eISSN: 1611-3349
Links: http://link.springer.com/chapter/10.1007%2F978-3-642-30850-5_20
http://hdl.handle.net/2381/29103
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2012, Springer-Verlag Berlin Heidelberg. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
dynamictrees.pdfPost-review (final submitted)267.7 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.