On algorithms for efficient data migration

Joseph Hall*, Jason Hartline, Anna R. Karlin, Jared Saia, John Wilkes

*Corresponding author for this work

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

71 Scopus citations

Abstract

The data migration problem is the problem of computing an efficient plan for moving data stored on devices in a network from one configuration to another. Load balancing or changing usage patterns could necessitate such a rearrangement of data. In this paper, we consider the case where the objects are fixed-size and the network is complete. The direct migration problem is closely related to edge-coloring. However, because there are space constraints on the devices, the problem is more complex. Our main results are polynomial time algorithms for finding a near-optimal migration plan in the presence of space constraints when a certain number of additional nodes is available as temporary storage, and a 3/2-approximation for the case where data must be migrated directly to its destination.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages620-629
Number of pages10
StatePublished - Dec 1 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
Country/TerritoryUnited States
CityDallas, TX
Period4/30/015/1/01

Keywords

  • Algorithms
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On algorithms for efficient data migration'. Together they form a unique fingerprint.

Cite this