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 http://link.springer.de/link/service/series/0558/papers/2461/24610165.pdf.
- 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
Last updated September 13, 2019 by