Paper by Erik D. Demaine

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.

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.

This paper is also available from the electronic LNCS volume as

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.

The paper is \copyright Springer-Verlag.

The paper is 8 pages.

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)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 26, 2017 by Erik Demaine.