Paper by Erik D. Demaine

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.

BibTeX

@Misc{TreeLayout_Manuscript2003,
  AUTHOR        = {Stephen Alstrup and Michael A. Bender and Erik D. Demaine
                   and Martin Farach-Colton and J. Ian Munro and Theis Rauhe
                   and Mikkel Thorup},
  TITLE         = {Efficient Tree Layout in a Multilevel Memory Hierarchy},
  HOWPUBLISHED  = {Manuscript},
  MONTH         = {December},
  YEAR          = 2003,

  LENGTH        = {14 pages},
  PAPERS        = {TreeLayout_ESA2002},
  COMMENTS      = {This paper is also available as
                   <A HREF="http://arXiv.org/abs/cs.DS/0211010">
                   arXiv:cs.DS/0211010</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.
                   <P>
                   This paper replaces and rectifies the
                   <A HREF="../TreeLayout_ESA2002">ESA
                   version</A>.}
}

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)