research-article

Approximation algorithms for data placement on parallel disks

Authors:

Leana Golubchik,

Sanjeev Khanna,

Ramakrishna Thurimella,

An ZhuAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 5, Issue 4

Article No.: 34, Pages 1 - 26

https://doi.org/10.1145/1597036.1597037

Published: 06 November 2009 Publication History

Abstract

We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data objects) that need to be assigned to a storage system consisting of N disks d₁,d₂…,d_N. We are also given sets U₁,U₂,…,U_M such that U_i is the set of clients seeking the ith data object. Each disk d_j is characterized by two parameters, namely, its storage capacity C_j which indicates the maximum number of data objects that may be assigned to it, and a load capacity L_j which indicates the maximum number of clients that it can serve. The goal is to find a placement of data objects to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system.

We study this data placement problem for two natural classes of storage systems, namely, homogeneous and uniform ratio. We show that an algorithm developed by Shachnai and Tamir [2000a] for data placement achieves the best possible absolute bound regarding the number of clients that can always be satisfied. We also show how to implement the algorithm so that it has a running time of O((N + M) log(N + M)). In addition, we design a polynomial-time approximation scheme, solving an open problem posed in the same paper.

References

[1]

Berson, S., Ghandeharizadeh, S., Muntz, R. R., and Ju, X. 1994. Staggered striping in multimedia information systems. In Proceedings of the ACM SIGMOD Conference, 79--90.

Digital Library

[2]

Chekuri, C., and Khanna, S. 1999. On multidimensional packing problems. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms. 185--194.

Digital Library

[3]

Chervenak, A. L. 1994. Tertiary storage: An evaluation of new applications. Ph.D. thesis, University of California Berkeley.

Digital Library

[4]

Chou, C.-F., Golubchik, L., Lui, J., and Chung, I.-H. 2002. Design of scalable continuous media servers. J. Multimedia Tools Appl. (Special issue on QoS) 17, 2-3, 181--212.

Digital Library

[5]

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company.

Digital Library

[6]

Frieze, A. M., and Clarke, M. R. B. 1984. Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-Case and probabilistic analyses. Eur. J. Oper. Res. 100--109.

[7]

Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.

Digital Library

[8]

Kashyap, S., and Khuller, S. 2003. Algorithms for non-uniform size data placement on parallel disks. In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). 265--276.

[9]

Knuth, D. E. 1973. The Art of Computer Programming, vol. 3. Addison-Wesley.

[10]

Pugh, W. 1990. Skip lists: A probabilistic alternative to balanced trees. Comm. ACM 33, 6, 668--676.

Digital Library

[11]

Raghavan, P. 1988. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Syst. Sci. 130--143.

Digital Library

[12]

Shachnai, H., and Tamir, T. 2000a. On two class-constrained versions of the multiple knapsack problem. Algorithmica 29, 3, 442--467.

Digital Library

[13]

Shachnai, H., and Tamir, T. 2000b. Polynomial time approximation schemes for class-constrained packing problems. In Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249.

Digital Library

[14]

Shachnai, H., and Tamir, T. 2003. Approximation schemes for generalized 2-dimensional vector packing with application to data placement. In Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249.

[15]

Stonebraker, M. 1986. A case for shared nothing. Datab. Engin. 9, 1, 4--9.

[16]

Wolf, J., Yu, P., and Shachnai, H. 1995. DASD dancing: A disk load balancing optimization scheme for video-on-demand computer systems. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. 157--166.

Digital Library

Cited By

Zhang ZFeng QHuang JWang J(2022)Improved approximation algorithms for solving the squared metric k-facility location problemTheoretical Computer Science10.1016/j.tcs.2022.11.027Online publication date: Nov-2022
https://doi.org/10.1016/j.tcs.2022.11.027
Zhang ZFeng Q(2021)An Improved Approximation Algorithm for Squared Metric k-Facility LocationCombinatorial Optimization and Applications10.1007/978-3-030-92681-6_42(538-552)Online publication date: 11-Dec-2021
https://doi.org/10.1007/978-3-030-92681-6_42
Borges YMiyazawa FSchouery RXavier E(2020)Exact algorithms for class-constrained packing problemsComputers & Industrial Engineering10.1016/j.cie.2020.106455144(106455)Online publication date: Jun-2020
https://doi.org/10.1016/j.cie.2020.106455
Show More Cited By

Index Terms

Approximation algorithms for data placement on parallel disks
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Approximation Algorithms for Data Placement Problems

We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimize the average data-access cost. We ...
A priority-based data placement method for databases using solid-state drives
RACS '18: Proceedings of the 2018 Conference on Research in Adaptive and Convergent Systems

When applications require high I/O performance, solid-state drives (SSDs) are often preferable because they perform better than traditional hard-disk drives (HDDs). Therefore, database system response time can be improved by moving frequently used data ...
Algorithms for non-uniform size data placement on parallel disks

We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data items) that need to be assigned to a storage system consisting of N disks d₁, d₂,...,d_N...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 5, Issue 4

October 2009

281 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1597036

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2009

Accepted: 01 July 2008

Revised: 01 June 2007

Received: 01 December 2006

Published in TALG Volume 5, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
452
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang ZFeng QHuang JWang J(2022)Improved approximation algorithms for solving the squared metric k-facility location problemTheoretical Computer Science10.1016/j.tcs.2022.11.027Online publication date: Nov-2022
https://doi.org/10.1016/j.tcs.2022.11.027
Zhang ZFeng Q(2021)An Improved Approximation Algorithm for Squared Metric k-Facility LocationCombinatorial Optimization and Applications10.1007/978-3-030-92681-6_42(538-552)Online publication date: 11-Dec-2021
https://doi.org/10.1007/978-3-030-92681-6_42
Borges YMiyazawa FSchouery RXavier E(2020)Exact algorithms for class-constrained packing problemsComputers & Industrial Engineering10.1016/j.cie.2020.106455144(106455)Online publication date: Jun-2020
https://doi.org/10.1016/j.cie.2020.106455
Li XZhang LWu YLiu XZhu EYi HWang FZhang CYang Y(2019)A Novel Workflow-Level Data Placement Strategy for Data-Sharing Scientific Cloud WorkflowsIEEE Transactions on Services Computing10.1109/TSC.2016.262524712:3(370-383)Online publication date: 1-May-2019
https://doi.org/10.1109/TSC.2016.2625247
Shao YLi CTang H(2019)A data replica placement strategy for IoT workflows in collaborative edge and cloud environmentsComputer Networks10.1016/j.comnet.2018.10.017148(46-59)Online publication date: Jan-2019
https://doi.org/10.1016/j.comnet.2018.10.017
Khuller SSaha BSarpatwar K(2016)New Approximation Results for Resource Replication ProblemsAlgorithmica10.1007/s00453-015-9978-974:3(969-991)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s00453-015-9978-9
Lin THsu CHsu L(2013)Optimization by Ant Colony Hybrid Local Search for Online Class Constrained Bin Packing ProblemApplied Mechanics and Materials10.4028/www.scientific.net/AMM.311.123311(123-128)Online publication date: Feb-2013
https://doi.org/10.4028/www.scientific.net/AMM.311.123
Shachnai HTamir T(2012)Approximation schemes for generalized two-dimensional vector packing with application to data placementJournal of Discrete Algorithms10.1016/j.jda.2011.07.00110(35-48)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1016/j.jda.2011.07.001
Khuller SSaha BSarpatwar K(2012)New Approximation Results for Resource Replication ProblemsApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-32512-0_19(218-230)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32512-0_19
Petrov DTatarinov Y(2009)Data migration in the scalable storage cloud2009 International Conference on Ultra Modern Telecommunications & Workshops10.1109/ICUMT.2009.5345514(1-4)Online publication date: Oct-2009
https://doi.org/10.1109/ICUMT.2009.5345514

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents