Inlämning av Examensarbete / Submission of Thesis

Venkata Sudheer Kumar Reddy Yasam MCS-2009-23, pp. 45. COM/School of Computing, 2009.

The work

Författare / Author: Venkata Sudheer Kumar Reddy Yasam
sudheergid@gmail.com
Titel / Title: An Optimized Representation for Dynamic k-ary Cardinal Trees
Abstrakt Abstract:

Trees are one of the most fundamental structures in computer science. Standard pointer-based representations consume a significant amount of space while only supporting a small set of navigational operations. Succinct data structures have been developed to overcome these difficulties. A succinct data structure for an object from a given class of objects occupies space close to the information-theoretic lower-bound for representing an object from the class, while supporting the required operations on the object efficiently. In this thesis we consider representing trees succinctly. Various succinct representations have been designed for representing different classes of trees, namely, ordinal trees, cardinal trees and labelled trees. Barring a few, most of these representations are static in that they do not support inserting and deleting nodes. We consider succinct representations for cardinal trees that also support updates (insertions and deletions), i.e., dynamic cardinal trees.
A cardinal tree of degree k, also referred to as a k-ary cardinal tree or simply a k-ary tree is a tree where each node has place for up to k children with labels from 1 to k. The information-theoretic lower bound for representing a k-ary cardinal tree on n nodes is roughly (2n+n log k) bits. Representations that take (2n+n log k+ o(n log k ) ) bits have been designed that support basic navigations operations like finding the parent, i-th child, child-labeled j, size of a subtree etc. in constant time. But these could not support updates efficiently. The only known succinct dynamic representation was given by Diego, who gave a structure that still uses (2n+n log k+o(n log k ) ) bits and supports basic navigational operations in O((log k+log log n) ) time, and updates in O((log k + log log n)(1+log k /log (log k + log log n))) amortized time. We improve the times for the operations without increasing the space complexity, for the case when k is reasonably small compared to n. In particular, when k=(O(√(log n ))) our representation supports all the navigational operations in constant time while supporting updates in O(√(log log n )) amortized time.

Ämnesord / Subject: Datavetenskap - Computer Science\Computersystems

Nyckelord / Keywords: Succinct data structures, binary trees, ordinal trees, cardinal trees, rank, select, static and dynamic.

Publication info

Dokument id / Document id:
Program:/ Programme Magisterprogram i Datavetenskap/MSC in Computer science
Registreringsdatum / Date of registration: 06/16/2009
Uppsatstyp / Type of thesis: Masterarbete/Master's Thesis (120 credits)

Context

Handledare / Supervisor: Stefan J. Johansson
stefan.johansson@bth.se
Examinator / Examiner: Guohua Bai
Organisation / Organisation: Blekinge Institute of Technology
Institution / School: COM/School of Computing

+46 455 38 50 00