Algorithms for Data Migration with Cloning

Summary: Formalize the data-migration-with-cloning problem for reconfiguring multi-disk storage under dynamic demand; prove NP-hardness. Give polynomial-time approximation algorithms with a worst-case 9.5 factor and empirical comparisons to heuristics. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1275
Venue: PODS
Year: 2003
Pagerank: 5.3251649e-05
Overall Rank: 9,094 | 37.61%
DOI: 10.1145/773153.773156

Incoming Non-self Citations Over Time

Authors

1. Samir Khuller (University of Maryland)
2. Yoo-Ah Kim (University of Maryland)
3. Yung-Chun (Justin) Wan (University of Maryland)

BibTeX Citation

@inproceedings{khuller_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Algorithms for Data Migration with Cloning}},
        url = {https://dl.acm.org/doi/10.1145/773153.773156},
        doi = {10.1145/773153.773156},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Khuller, Samir and Kim, Yoo-Ah and Wan, Yung-Chun (Justin)},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,530	SQL-Exchange: Transforming SQL Queries Across Domains	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,428	Dynamic File Allocation in Disk Arrays	1991	SIGMOD
2	4,227	Distributed Algorithms For Dynamic Replication Of Data	1992	PODS
3	3,566	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD
4	11,641	Approximation Algorithms for Large Scale Data Analysis	2021	PODS
5	14,503	An Approximation Algorithm To The File Allocation Problem In Computer Networks	1983	PODS
6	5,888	Clustering Techniques for Minimizing External Path Length	1996	VLDB
7	7,688	Incremental File Reorganization Schemes	1985	VLDB
8	13,017	Optimal Response Time Retrieval of Replicated Data	1994	PODS
9	13,256	File Allocation in Distributed Databases with Interaction between Files	1983	VLDB
10	13,272	An Approximation Algorithm For A File-Allocation Problem In A Hierarchical Distributed System.	1980	SIGMOD