Worst-Case Optimal Tree Layout in External Memory

Erik D. Demaine; John Iacono; Stefan Langerman

doi:10.1007/s00453-013-9856-2

Worst-Case Optimal Tree Layout in External Memory

Erik D. Demaine, John Iacono, Stefan Langerman

Research output: Contribution to journal › Article › peer-review

Abstract

Consider laying out a fixed-topology binary 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 (Formula Presented.)

Original language	English (US)
Pages (from-to)	369-378
Number of pages	10
Journal	Algorithmica
Volume	72
Issue number	2
DOIs	https://doi.org/10.1007/s00453-013-9856-2
State	Published - Jun 1 2015

Keywords

Data structures
External-memory
Trees

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-013-9856-2

Cite this

@article{776757d1a2da498f9bead0e2475932ce,

title = "Worst-Case Optimal Tree Layout in External Memory",

abstract = "Consider laying out a fixed-topology binary 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 (Formula Presented.)",

keywords = "Data structures, External-memory, Trees",

author = "Demaine, {Erik D.} and John Iacono and Stefan Langerman",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2015",

month = jun,

day = "1",

doi = "10.1007/s00453-013-9856-2",

language = "English (US)",

volume = "72",

pages = "369--378",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Worst-Case Optimal Tree Layout in External Memory

AU - Demaine, Erik D.

AU - Iacono, John

AU - Langerman, Stefan

PY - 2015/6/1

Y1 - 2015/6/1

N2 - Consider laying out a fixed-topology binary 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 (Formula Presented.)

AB - Consider laying out a fixed-topology binary 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 (Formula Presented.)

KW - Data structures

KW - External-memory

KW - Trees

UR - http://www.scopus.com/inward/record.url?scp=84929061198&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84929061198&partnerID=8YFLogxK

U2 - 10.1007/s00453-013-9856-2

DO - 10.1007/s00453-013-9856-2

M3 - Article

AN - SCOPUS:84929061198

SN - 0178-4617

VL - 72

SP - 369

EP - 378

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -

Worst-Case Optimal Tree Layout in External Memory

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this