2004/10/19 by Erik D. Demaine, Demaine, Erik D., John Iacono +3
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #E.1 #F.2.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.cs/0410048
openalex publication_date 2004/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \cases Θ( D \over \lg (1+B) ) amp; when D = O(\lg N), \cr Θ( \lg N \over \lg (1+B \lg N \over D) ) amp; when D = Ω(\lg N) and D = O(B \lg N), \cr Θ( D \over B ) amp; when D = Ω(B \lg N).