Data migration on parallel disks: Algorithms and evaluation

Leana Golubchik*, Samir Khuller, Yoo Ah Kim, Svetlana Shargorodskaya, Yung Chun Wan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such storage servers are used as web servers or multimedia servers, for handling high demand for data. As the system is running, to exhibit good performance, it needs to respond dynamically to changes in demand for different data items. There are known algorithms for mapping demand to a layout. When the demand changes, a new layout can be computed. In this work we study the data migration problem, which arises when we need to change one layout to another quickly. This problem has been studied earlier where for each disk a new layout has been prescribed. However, to apply these algorithms effectively, we identify another problem that we refer to as the correspondence problem, whose solution has a significant impact on the overall solution for the data migration problem. We study algorithms for the data migration problem in more detail and identify variations of the basic algorithm that seem to improve performance in practice, even though some of the variations have poor worst-case behavior.

Original languageEnglish (US)
Pages (from-to)137-158
Number of pages22
JournalAlgorithmica (New York)
Issue number1
StatePublished - Jun 2006


  • Approximation algorithms
  • Data migration
  • Data movement
  • Data placement
  • Load balancing

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Data migration on parallel disks: Algorithms and evaluation'. Together they form a unique fingerprint.

Cite this