An experimental study of data migration algorithms

Eric Anderson*, Joe Hall, Jason Hartline, Michael Hobbs, Anna R. Karlin, Jared Saia, Ram Swaminathan, John Wilkes

*Corresponding author for this work

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

37 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. We introduce two new data migration algorithms, one of which has provably good bounds. We empirically compare the performance of these new algorithms against similar algorithms from Hall et al. [7] which have better theoretical guarantees and find that in almost all cases, the new algorithms perform better. We also find that both the new algorithms and the ones from Hall et al. perform much better in practice than the theoretical bounds suggest.

Original languageEnglish (US)
Title of host publicationAlgorithm Engineering - 5th International Workshop, WAE 2001, Proceedings
Pages145-158
Number of pages14
DOIs
StatePublished - 2001
Event5th International Workshop on Algorithm Engineering, WAE 2001 - Arhus, Denmark
Duration: Aug 28 2010Aug 31 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2141 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Workshop on Algorithm Engineering, WAE 2001
CountryDenmark
CityArhus
Period8/28/108/31/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An experimental study of data migration algorithms'. Together they form a unique fingerprint.

Cite this