Paper by Erik D. Demaine

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.

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.

This paper is also available as arXiv:cs.DS/0211010 of the Computing Research Repository (CoRR).

This paper replaces and rectifies the ESA version.

The paper is 14 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.