Worst-case optimal tree layout in external memory

DOI10.1007/S00453-013-9856-2MaRDI QIDQ2354018zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, John Iacono, Stefan Langerman

Publication date 10 July 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0410048

zbMATH Keywords

treesdata structuresexternal-memory

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: Consider laying out a fixed-topology tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth D. We prove that the optimal number of memory transfers is ${\displaystyle }$ cases{ displaystyle Thetaleft( {D over lg (1{+}B)} ight) & when $D=O(lgN)$, cr displaystyle Thetaleft( {lg N over lg left(1{+}{B lg N over D} ight)} ight) & when $D=Omega(lgN)$ and $D=O(BlgN)$, cr displaystyle Thetaleft( {D over B} ight) & when $D=Omega(BlgN)$. } ${\displaystyle }$

Recommendations

• Optimal worst case trees
• scientific article; zbMATH DE number 1947390
• scientific article; zbMATH DE number 4062615
• scientific article; zbMATH DE number 1670677
• scientific article; zbMATH DE number 2163020
• Optimal worst-case operations for implicit cache-oblivious search trees.
• Dynamic and static algorithms for optimal placement of resources in a tree
• A data-parallel algorithm for minimum-width tree layout

Cites work

• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• Blocking for external graph searching
• How to Pack Trees
• The string B-tree

Cited in

(5)

• On the weak prefix-search problem
• Succinct and I/O efficient data structures for traversal in trees
• scientific article; zbMATH DE number 1947390 (Why is no real title available?)
• Belga B-trees
• I/O efficient dynamic data structures for longest prefix queries

This page was built for publication: Worst-case optimal tree layout in external memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354018)