On the hierarchy of distribution-sensitive properties for data structures

Amr Elmasry; Arash Farzan; John Iacono

doi:10.1007/s00236-013-0180-8

On the hierarchy of distribution-sensitive properties for data structures

Amr Elmasry, Arash Farzan, John Iacono

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

Abstract

In this paper new dependencies are added to the hierarchy of the distribution-sensitive properties for data structures. Most remarkably, we prove that the working-set property is equivalent to the unified-bound property; a fact that had gone unnoticed since the introduction of such bounds in the Eighties by Sleator and Tarjan.

Original language	English (US)
Pages (from-to)	289-295
Number of pages	7
Journal	Acta Informatica
Volume	50
Issue number	4
DOIs	https://doi.org/10.1007/s00236-013-0180-8
State	Published - Jun 2013

ASJC Scopus subject areas

Software
Information Systems
Computer Networks and Communications

Access to Document

10.1007/s00236-013-0180-8

Cite this

@article{daf125ccadc84698879a2a479f2126c8,

title = "On the hierarchy of distribution-sensitive properties for data structures",

abstract = "In this paper new dependencies are added to the hierarchy of the distribution-sensitive properties for data structures. Most remarkably, we prove that the working-set property is equivalent to the unified-bound property; a fact that had gone unnoticed since the introduction of such bounds in the Eighties by Sleator and Tarjan.",

author = "Amr Elmasry and Arash Farzan and John Iacono",

note = "Funding Information: Amr Elmasry: Supported by fellowships from Alexander von Humboldt and VELUX foundations. Funding Information: John Iacono: Research partially supported by NSF grants CCF-0430849, CCF-1018370, and an Alfred P. Sloan fellowship, and by MADALGO—Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Aarhus University. ",

year = "2013",

month = jun,

doi = "10.1007/s00236-013-0180-8",

language = "English (US)",

volume = "50",

pages = "289--295",

journal = "Acta Informatica",

issn = "0001-5903",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - On the hierarchy of distribution-sensitive properties for data structures

AU - Elmasry, Amr

AU - Farzan, Arash

AU - Iacono, John

N1 - Funding Information: Amr Elmasry: Supported by fellowships from Alexander von Humboldt and VELUX foundations. Funding Information: John Iacono: Research partially supported by NSF grants CCF-0430849, CCF-1018370, and an Alfred P. Sloan fellowship, and by MADALGO—Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Aarhus University.

PY - 2013/6

Y1 - 2013/6

N2 - In this paper new dependencies are added to the hierarchy of the distribution-sensitive properties for data structures. Most remarkably, we prove that the working-set property is equivalent to the unified-bound property; a fact that had gone unnoticed since the introduction of such bounds in the Eighties by Sleator and Tarjan.

AB - In this paper new dependencies are added to the hierarchy of the distribution-sensitive properties for data structures. Most remarkably, we prove that the working-set property is equivalent to the unified-bound property; a fact that had gone unnoticed since the introduction of such bounds in the Eighties by Sleator and Tarjan.

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

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

U2 - 10.1007/s00236-013-0180-8

DO - 10.1007/s00236-013-0180-8

M3 - Article

AN - SCOPUS:84878799426

SN - 0001-5903

VL - 50

SP - 289

EP - 295

JO - Acta Informatica

JF - Acta Informatica

IS - 4

ER -

On the hierarchy of distribution-sensitive properties for data structures

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this