Cost-oblivious storage reallocation

DOI10.1145/3070693MaRDI QIDQ4962674zbMATH OpenOpenAlexFDO

Authors Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Michael A. Bender, Seth Gilbert

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.2019

zbMATH Keywords

cost-obliviousphysical layoutreallocationschedulingstorage allocation

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Database theory (68P15)

Abstract: Databases need to 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. If previously allocated blocks cannot be moved, the problem is called the memory allocation problem, which is known to have a logarithmic overhead in the footprint. This paper defines the storage reallocation problem, where previously allocated blocks can be moved, or reallocated, but at some cost. 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 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+epsilon) times optimal, and the reallocation cost is at most (1/epsilon) times the original allocation cost, which is also optimal. The algorithms are cost oblivious as long as the allocation/reallocation cost function is subadditive.

Recommendations

• Insertion and Compaction Algorithms in Sequentially Allocated Storage
• scientific article; zbMATH DE number 1003306
• Tight Bounds for Dynamic Storage Allocation
• A provably efficient algorithm for dynamic storage allocation
• Cache replacement with memory allocation

Cited in

(5)

• Optimal allocation of storage space
• A theory and algorithms for combinatorial reoptimization
• Maintaining Arrays of Contiguous Objects
• Minimal cost reconfiguration of data placement in a storage area network
• A generalized matching reconfiguration problem

This page was built for publication: Cost-oblivious storage reallocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962674)