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.

BibTeX

@Article{TreeLayoutWorstCase_Algorithmica,
  AUTHOR        = {Erik D. Demaine and John Iacono and Stefan Langerman},
  TITLE         = {Worst-Case Optimal Tree Layout in External Memory},
  JOURNAL       = {Algorithmica},
  journalurl    = {https://www.springer.com/journal/453},
  VOLUME        = 72,
  NUMBER        = 2,
  PAGES         = {369--378},
  YEAR          = 2015,

  length        = {10 pages},
  doi           = {https://dx.doi.org/10.1007/s00453-013-9856-2},
  dblp          = {https://dblp.org/rec/journals/algorithmica/DemaineIL15},
  comments      = {This paper is also available as
                   <A HREF="http://arXiv.org/abs/cs.DS/0410048">
                   arXiv:cs.DS/0410048</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>. <P>
                   This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00453-013-9856-2">SpringerLink</A>.},
}

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]