Paper by Erik D. Demaine

Reference:

Erik D. Demaine, John Iacono, and Stefan Langerman, “Worst-Case Optimal Tree Layout in External Memory”, Algorithmica, volume 72, number 2, 2015, pages 369–378.

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

Θ	({	D / lg (1+B)		when D = O(lg N)	)	.
		lg N / lg (1 + (B lg N) / D)		when D = Ω(lg N) and D = O(B lg N)
		D / B		when D = Ω(B lg N)

Comments:

This paper is also available as arXiv:cs.DS/0410048 of the Computing Research Repository (CoRR).

This paper is also available from SpringerLink.

Length:

The paper is 10 pages.

Availability:

The paper is available in PostScript (440k), gzipped PostScript (223k), and PDF (229k).

See information on file formats.

[Google Scholar search]