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
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
|
leaf-root.pdf | 2022-08-26 | Public | Download |