Vi betraktar problemet med att lägga ut ett träd med fast förälder/barnstruktur i hierarkiskt minne. Målet är att minimera det förväntade antalet blocköverföringar som utförs under en sökning längs en root-to-leaf väg, med förbehåll för en given sannolikhetsfördelning på bladen. Detta problem övervägdes tidigare av Gil och Itai, som utvecklade optimala men långsamma algoritmer när block-överföring storlek B är känd. Vi presenterar snabbare men ungefärliga algoritmer för samma problem; den snabbaste sådan algoritm körs i linjär tid och producerar en lösning som är inom en additiv konstant av optimal. Dessutom visar vi hur man utökar någon i stort sett optimal algoritm till den cache-oblivious inställning där block-överföringsstorleken är okänd för algoritmen. Förfrågan prestanda cache-oblivious layout ligger inom en konstant faktor för frågeprestandan för den optimala kända block-storlek layout. Att beräkna cacheoblivious layout kräver bara logaritmiskt många anrop till layoutalgoritmen för känd blockstorlek; i synnerhet, cache-oblivious layout kan beräknas i O (N lg N ) tid, där N är antalet noder. Slutligen analyserar vi två giriga strategier, och visar att de har ett prestandaförhållande mellan eng B/lg lg B) och O(lg B) jämfört med den optimala layouten.
En annan metod för att packa träd i hierarkiskt minne med hjälp av ungefärliga algoritmer föreslås i REF.
Efficient Tree Layout in a Multilevel Memory Hierarchy
{'venue': 'ESA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}