Paper by Erik D. Demaine

Reference:

Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton, “Efficient Tree Layout in a Multilevel Memory Hierarchy”, in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 165–173.

BibTeX

@InProceedings{TreeLayout_ESA2002,
  AUTHOR        = {Michael A. Bender and Erik D. Demaine and Martin
                   Farach-Colton},
  TITLE         = {Efficient Tree Layout in a Multilevel Memory Hierarchy},
  BOOKTITLE     = {Proceedings of the 10th Annual European Symposium on
                   Algorithms (ESA 2002)},
  bookurl       = {http://www.dis.uniroma1.it/~algo02/esa02/},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 2461,
  ADDRESS       = {Rome, Italy},
  MONTH         = {September 17--21},
  YEAR          = 2002,
  PAGES         = {165--173},

  COPYRIGHT     = {The paper is \copyright Springer-Verlag.},
  LENGTH        = {8 pages},
  PAPERS        = {TreeLayout_Manuscript2003},
  UPDATES       = {We have discovered some of the claims in this paper to be
                   incorrect.  Please refer to the
                   <A HREF="../TreeLayout_Manuscript2002">revision</A>
                   where these mistakes are described and corrected.},
  doi           = {https://dx.doi.org/10.1007/3-540-45749-6_18},
  dblp          = {https://dblp.org/rec/conf/esa/BenderDF02},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/cs/0211010">arXiv:cs/0211010</A>.},
}

Abstract:

We consider the problem of laying out a tree or trie in a hierarchical memory, where the tree/trie has a fixed parent/child structure. The goal is to minimize the expected number of block transfers performed during a search operation, subject to a given probability distribution on the leaves. This problem was previously considered by Gil and Itai, who show optimal but high-complexity algorithms when the block-transfer size is known. We propose a simple greedy algorithm that is within an additive constant strictly less than 1 of optimal. We also present a relaxed greedy algorithm that permits more flexibility in the layout while decreasing performance (increasing the expected number of block transfers) by only a constant factor. Finally, we extend this latter algorithm to the cache-oblivious setting in which the block-transfer size is unknown to the algorithm; in particular this extension solves the problem for a multilevel memory hierarchy. The query performance of the cache-oblivious layout is within a constant factor of the query performance of the optimal layout with known block size.

Comments:

This paper is also available as arXiv:cs/0211010.

Updates:

We have discovered some of the claims in this paper to be incorrect. Please refer to the revision where these mistakes are described and corrected.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 8 pages.

Availability:

The paper is available in PostScript (133k), gzipped PostScript (54k), and PDF (117k).

See information on file formats.

[Google Scholar search]

Related papers:

TreeLayout_Manuscript2003 (Efficient Tree Layout in a Multilevel Memory Hierarchy)