Algorithms for data migration

E. Anderson, J. Hall, Jason D Hartline, M. Hobbes, A. Karlin, J. Saia*, R. Swaminathan, J. Wilkes

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

The data migration problem is the problem of computing a plan for moving data objects stored on devices in a network from one configuration to another. Load balancing or changing usage patterns might necessitate such a rearrangement of data. In this paper, we consider the case where the objects are fixed-size and the network is complete. Our results are both theoretical and empirical. Our main theoretical results are (1) a polynomial time algorithm 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 (2) a 3/2-approximation algorithm for the case where data must be migrated directly to its destination. We also run extensive experiments on several algorithms for various data migration problems and show that empirically, many algorithms perform better in practice than their theoretical bounds suggest. We conclude that many of the algorithms we present are both practical and effective for data migration.

Original languageEnglish (US)
Pages (from-to)349-380
Number of pages32
JournalAlgorithmica (New York)
Volume57
Issue number2
DOIs
StatePublished - Jun 1 2010

Keywords

  • Approximation algorithms
  • Data migration
  • Edge coloring
  • Load-balancing
  • Space constraints

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Algorithms for data migration'. Together they form a unique fingerprint.

Cite this