Algorithms for data migration with cloning

Samir Khuller*, Yoo Ah Kim, Yung Chun Wan

*Corresponding author for this work

Research output: Contribution to journalArticle

25 Scopus citations

Abstract

Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high-demand storage servers are used as Web servers or as multimedia servers for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. In this work we study the data migration problem, which arises when we need to quickly change one storage configuration into another. We show that this problem is NP-hard. In addition, we develop polynomial-time approximation algorithms for this problem and prove a worst-case bound of 9.5 on the approximation factor achieved by our algorithm.

Original languageEnglish (US)
Pages (from-to)448-461
Number of pages14
JournalSIAM Journal on Computing
Volume33
Issue number2
DOIs
StatePublished - Jan 1 2004

Keywords

  • Approximation algorithms
  • Broadcast
  • Gossip
  • Multicast

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this