**Reference**:- Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, and Mikkel Thorup, “Efficient Tree Layout in a Multilevel Memory Hierarchy”, Manuscript, December 2003.
**Abstract**:-
We consider the problem of laying out a tree with fixed parent/child
structure in hierarchical memory. The goal is to minimize the
expected number of block transfers performed during a search along a
root-to-leaf path, subject to a given probability distribution on
the leaves. This problem was previously considered by Gil and Itai,
who developed optimal but slow algorithms when the
block-transfer size
*B*is known. We present faster but approximate algorithms for the same problem; the fastest such algorithm runs in linear time and produces a solution that is within an additive constant of optimal.In addition, we show how to extend any approximately optimal algorithm to the

*cache-oblivious*setting in which the block-transfer size is unknown to the algorithm. The query performance of the cache-oblivious layout is within a constant factor of the query performance of the optimal known-block-size layout. Computing the cache-oblivious layout requires only logarithmically many calls to the layout algorithm for known block size; in particular, the cache-oblivious layout can be computed in*O*(*N*lg*N*) time, where*N*is the number of nodes.Finally, we analyze two greedy strategies, and show that they have a performance ratio between Ω(lg

*B*/ lg lg*B*) and*O*(lg*B*) when compared to the optimal layout. **Comments**:- This paper is also available as arXiv:cs.DS/0211010 of the Computing Research Repository (CoRR).
This paper replaces and rectifies the ESA version.

**Length**:- The paper is 14 pages.
**Availability**:- The paper is available in PostScript (367k), gzipped PostScript (165k), and PDF (201k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- TreeLayout_ESA2002 (Efficient Tree Layout in a Multilevel Memory Hierarchy)

See also other papers by Erik Demaine.

Last updated July 21, 2021 by Erik Demaine.