Cost-oblivious storage reallocation

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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).

    Original languageEnglish (US)
    Title of host publicationPODS 2014 - Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
    PublisherAssociation for Computing Machinery
    Number of pages11
    ISBN (Print)9781450323758
    StatePublished - 2014
    Event33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014 - Snowbird, UT, United States
    Duration: Jun 22 2014Jun 27 2014

    Publication series

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


    Conference33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014
    Country/TerritoryUnited States
    CitySnowbird, UT


    • Cost oblivious
    • Physical layout
    • Reallocation
    • Scheduling
    • Storage allocation

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Hardware and Architecture


    Dive into the research topics of 'Cost-oblivious storage reallocation'. Together they form a unique fingerprint.

    Cite this