ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

An Approximation Algorithm for a File-Allocation Problem in a Hierarchical Distributed System.

K. Lam, Clement T. Yu: An Approximation Algorithm for a File-Allocation Problem in a Hierarchical Distributed System. SIGMOD Conference 1980: 125-132
@inproceedings{DBLP:conf/sigmod/LamY80,
  author    = {K. Lam and
               Clement T. Yu},
  editor    = {Peter P. Chen and
               R. Clay Sprowls},
  title     = {An Approximation Algorithm for a File-Allocation Problem in a
               Hierarchical Distributed System},
  booktitle = {Proceedings of the 1980 ACM SIGMOD International Conference on
               Management of Data, Santa Monica, California, May 14-16, 1980},
  publisher = {ACM Press},
  year      = {1980},
  pages     = {125-132},
  ee        = {http://doi.acm.org/10.1145/582250.582270, db/conf/sigmod/LamY80.html},
  crossref  = {DBLP:conf/sigmod/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A file allocation problem in a hierarchical distributed computer network is examined. It is shown that the problem is NP-hard. An approximation algorithm is suggested. It is estimated that the approximation algorithm has a high chance of obtaining the optimal solution. Experimental results show that the difference between the optimal solution and the solution generated by the approximation algorithm is no more than 4% away from the optimal solution.

Copyright © 1980 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter P. Chen, R. Clay Sprowls (Eds.): Proceedings of the 1980 ACM SIGMOD International Conference on Management of Data, Santa Monica, California, May 14-16, 1980. ACM Press 1980 BibTeX
Contents

Online Edition: ACM Digital Library


References

[1]
...
[2]
Shi-Kuo Chang: Data Base Decomposition in a Hierarchical Computer System. SIGMOD Conference 1975: 48-53 BibTeX
[3]
...
[4]
Kapali P. Eswaran: Placement of Records in a File and File Allocation in a Computer. IFIP Congress 1974: 304-307 BibTeX
[5]
...
[6]
Sakti P. Ghosh: Distributing a Data Base with Logical Associations on a Computer Network for Parallel Searching. IEEE Trans. Software Eng. 2(2): 106-113(1976) BibTeX
[7]
...
[8]
...
[9]
...
[10]
Samy A. Mahmoud, J. Spruce Riordon: Optimal Allocation of Resources in Distributed Information Networks. ACM Trans. Database Syst. 1(1): 66-78(1976) BibTeX
[11]
Howard L. Morgan, K. Dan Levin: Optimal Program and Data Locations in Computer Networks. Commun. ACM 20(5): 315-322(1977) BibTeX
[12]
...
[13]
...

Referenced by

  1. Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:22 2009