Succinct and I/O efficient data structures for traversal in trees
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 a tree on N nodes and traverses a path to the root. We show how a tree T on N nodes with q-bit keys, where q = O(lgN), can be blocked in a succinct fashion such that a bottom-up traversal requires O(K/B + 1) I/Os using only (2 + q)N + q . [2τN(q+2 lgB) w + o(N)] + 8tN lgB w bits to store T for any constant 0 < τ <1, where K is the path length and w is the word size. This data structure is succinct because the above space cost is at most (2+q)N +q . (?N +o(N)) bits for any arbitrarily selected constant, ?, such that 0<?<1. When storing keys with tree nodes is not required, we can represent T in 2N + εN lgB w + o(N) bits, where ε is an arbitrarily selected constant such that 0 < ε <1, while providing the same support for queries. Our second result is for top-down traversal in binary trees. We store the tree in (3 + q)N + o(N) bits, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.
|Keywords||Data structures, I/O efficient data structures, Path traversal, Succinct data structures, Trees|
Dillabaugh, C. (Craig), He, M. (Meng), & Maheshwari, A. (2012). Succinct and I/O efficient data structures for traversal in trees. Algorithmica, 63(1-2), 201–223. doi:10.1007/s00453-011-9528-z