Algorithms for Data Migration with Cloning

Samir Khuller*, Yoo Ah Kim, Yung Chun Wan

*Corresponding author for this work

Research output: Contribution to conferencePaper

37 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 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. We also compare the algorithm to several heuristics for this problem.

Original languageEnglish (US)
Pages27-36
Number of pages10
DOIs
StatePublished - Jan 1 2003
EventTwenty second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003 - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

Conference

ConferenceTwenty second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003
CountryUnited States
CitySan Diego, CA
Period6/9/036/11/03

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Algorithms for Data Migration with Cloning'. Together they form a unique fingerprint.

Cite this