Efficient Tree Layout in a Multilevel Memory Hierarchy
| dc.creator | Alstrup, Stephen | |
| dc.creator | Bender, Michael A. | |
| dc.creator | Demaine, Erik D. | |
| dc.creator | Farach-Colton, Martin | |
| dc.creator | Rauhe, Theis | |
| dc.creator | Thorup, Mikkel | |
| dc.date | 2002-11-12 | |
| dc.date | 2004-07-28 | |
| dc.date.accessioned | 2026-07-07T03:18:59Z | |
| dc.date.available | 2026-07-07T03:18:59Z | |
| dc.description | 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 Omega(lg B / lg lg B) and O(lg B) when compared to the optimal layout. | |
| dc.description | 18 pages. Version 2 adds faster dynamic programs. Preliminary version appeared in European Symposium on Algorithms, 2002 | |
| dc.identifier | https://arxiv.org/abs/cs/0211010 | |
| dc.identifier | http://arxiv.org/abs/cs/0211010 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31338 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | E.1; F.2.2 | |
| dc.title | Efficient Tree Layout in a Multilevel Memory Hierarchy | |
| dc.type | text |