Succinct and I/O efficient data structures for traversal in trees

Public Deposited
Resource Type
Creator
Abstract
  • We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in the tree T and traverses a path to the root. For blocks of size B, a tree on N nodes, and for a path of length K, we design data structures that permit traversal of the bottom-up path in O(K/B) I/Os using only bits, for an arbitrarily selected constant, ε, where 0∈<∈ε<∈1. Our second result is for top-down traversal in binary trees. We store T using (3∈+∈q)N∈+∈o(N) bits, where q is the number of bits required to store a key, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.

Language
Publisher
Identifier
Citation
  • Dillabaugh, C. (Craig), He, M. (Meng), & Maheshwari, A. (2008). Succinct and I/O efficient data structures for traversal in trees. doi:10.1007/978-3-540-92182-0_13
Date Created
  • 2008-12-01

Relations

In Collection:

Items