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.

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 from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2461/24610165.pdf.

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)