Algorithms for Data Migration with Cloning

Samir Khuller; Yoo Ah Kim; Yung Chun Wan

doi:10.1145/773153.773156

Algorithms for Data Migration with Cloning

Samir Khuller^*, Yoo Ah Kim, Yung Chun Wan

^*Corresponding author for this work

Computer Science

Research output: Contribution to conference › Paper › peer-review

43 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 language	English (US)
Pages	27-36
Number of pages	10
DOIs	https://doi.org/10.1145/773153.773156
State	Published - 2003
Event	Twenty second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003 - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003

Conference

Conference	Twenty second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003
Country/Territory	United States
City	San Diego, CA
Period	6/9/03 → 6/11/03

ASJC Scopus subject areas

Software
Information Systems
Hardware and Architecture

Access to Document

10.1145/773153.773156

Cite this

@conference{268f53af395c4a8e9200d957b459d4f4,

title = "Algorithms for Data Migration with Cloning",

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.",

author = "Samir Khuller and Kim, {Yoo Ah} and Wan, {Yung Chun}",

year = "2003",

doi = "10.1145/773153.773156",

language = "English (US)",

pages = "27--36",

note = "Twenty second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003 ; Conference date: 09-06-2003 Through 11-06-2003",

}

TY - CONF

T1 - Algorithms for Data Migration with Cloning

AU - Khuller, Samir

AU - Kim, Yoo Ah

AU - Wan, Yung Chun

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1142299772&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1142299772&partnerID=8YFLogxK

U2 - 10.1145/773153.773156

DO - 10.1145/773153.773156

M3 - Paper

AN - SCOPUS:1142299772

SP - 27

EP - 36

T2 - Twenty second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003

Y2 - 9 June 2003 through 11 June 2003

ER -

Algorithms for Data Migration with Cloning

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this