TY - GEN

T1 - Cost-oblivious storage reallocation

AU - Bender, Michael A.

AU - Farach-Colton, Martin

AU - Fekete, Sándor P.

AU - Fineman, Jeremy T.

AU - Gilbert, Seth

PY - 2014

Y1 - 2014

N2 - Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the mem-ory allocation problem. It is known to have a logarithmic overhead in the footprint size. This paper defines the storage reallocation problem, where previously allocated blocks can be moved, or real-located, but at some cost. This cost is determined by the allocation/reallocation cost function. The algorithms presented here are cost oblivious, in that they work for a broad and reasonable class of cost functions, even when they do not know what the cost function actually is. The objective is to minimize the storage footprint, that is, the largest memory address containing an allocated object, while simultaneously minimizing the reallocation costs. This paper gives asymptotically optimal algorithms for storage reallocation, in which the storage footprint is at most (1 + ε) times optimal, and the reallocation cost is at most O((1=ε) log(1=ε)) times the original allocation cost, which is asymptotically optimal for constant ε. The algorithms are cost oblivious, which means they achieve these bounds with no knowledge of the allocation/reallocation cost function, as long as the cost function is subadditive. Copyright is held by the owner/author(s).

AB - Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the mem-ory allocation problem. It is known to have a logarithmic overhead in the footprint size. This paper defines the storage reallocation problem, where previously allocated blocks can be moved, or real-located, but at some cost. This cost is determined by the allocation/reallocation cost function. The algorithms presented here are cost oblivious, in that they work for a broad and reasonable class of cost functions, even when they do not know what the cost function actually is. The objective is to minimize the storage footprint, that is, the largest memory address containing an allocated object, while simultaneously minimizing the reallocation costs. This paper gives asymptotically optimal algorithms for storage reallocation, in which the storage footprint is at most (1 + ε) times optimal, and the reallocation cost is at most O((1=ε) log(1=ε)) times the original allocation cost, which is asymptotically optimal for constant ε. The algorithms are cost oblivious, which means they achieve these bounds with no knowledge of the allocation/reallocation cost function, as long as the cost function is subadditive. Copyright is held by the owner/author(s).

KW - Cost oblivious

KW - Physical layout

KW - Reallocation

KW - Scheduling

KW - Storage allocation

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

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

U2 - 10.1145/2594538.2594548

DO - 10.1145/2594538.2594548

M3 - Conference contribution

AN - SCOPUS:84904330956

SN - 9781450323758

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 278

EP - 288

BT - PODS 2014 - Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems

PB - Association for Computing Machinery

T2 - 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014

Y2 - 22 June 2014 through 27 June 2014

ER -