ACM SIGMOD Anthology TODS dblp.uni-trier.de

Optimal Disk Allocation for Partial Match Queries.

Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Disk Allocation for Partial Match Queries. ACM Trans. Database Syst. 18(1): 132-156(1993)
@article{DBLP:journals/tods/Abdel-GhaffarA93,
  author    = {Khaled A. S. Abdel-Ghaffar and
               Amr El Abbadi},
  title     = {Optimal Disk Allocation for Partial Match Queries},
  journal   = {ACM Trans. Database Syst.},
  volume    = {18},
  number    = {1},
  year      = {1993},
  pages     = {132-156},
  ee        = {http://doi.acm.org/10.1145/151284.151288, db/journals/tods/Abdel-GhaffarA93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The problem of disk allocation addresses the issue of how to distribute a file on several disks in order to maximize concurrent disk accesses in response to a partial match query. In this paper a coding-theoretic analysis of this problem is presented, and both necessary and sufficient conditions for the existence of strictly optimal allocation methods are provided. Based on a class of optimal codes, known as maximum distance separable codes, strictly optimal allocation methods are constructed. Using the necessary conditions proved, we argue that the standard definition of strict optimality is too strong and cannot be attained, in general. Hence, we reconsider the definition of optimality. Instead of basing it on an abstract definition that may not be attainable, we propose a new definition based on the best possible allocation method. Using coding theory, allocation methods that are optimal according to our proposed criterion are developed.

Copyright © 1993 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 1713 KB]

References

[1]
Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: On the Optimality of Disk Allocation for Cartesian Product Files. PODS 1990: 258-264 BibTeX
[2]
Alfred V. Aho, Jeffrey D. Ullman: Optimal Partial-Match Retrieval When Fields Are Independently Specified. ACM Trans. Database Syst. 4(2): 168-179(1979) BibTeX
[3]
...
[4]
...
[5]
David Hung-Chang Du, J. S. Sobolewski: Disk Allocation for Cartesian Product Files on Multiple-Disk Systems. ACM Trans. Database Syst. 7(1): 82-101(1982) BibTeX
[6]
Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258 BibTeX
[7]
...
[8]
Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182 BibTeX
[9]
...
[10]
...
[11]
...
[12]
Alan W. Nordstrom, John P. Robinson: An Optimum Nonlinear Code. Information and Control 11(5/6): 613-616(1967) BibTeX
[13]
David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 BibTeX
[14]
Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX
[15]
James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) BibTeX
[16]
...
[17]
...
[18]
Sam Yuan Sung: Performance Analysis of Disk Modulo Allocation Method for Cartesian Product Files. IEEE Trans. Software Eng. 13(9): 1018-1026(1987) BibTeX
[19]
...

Referenced by

  1. Bongki Moon, Joel H. Saltz: Scalability Analysis of Declustering Methods for Multidimensional Range Queries. IEEE Trans. Knowl. Data Eng. 10(2): 310-327(1998)
  2. C. Y. Chen, H. F. Lin, Chin-Chen Chang, Richard C. T. Lee: Optimal Bucket Allocation Design of k-ary MKH Files for Partial Match Retrieval. IEEE Trans. Knowl. Data Eng. 9(1): 148-160(1997)
  3. Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Allocation of Two-Dimensional Data. ICDT 1997: 409-418
  4. Byoung Mo Im, Myoung-Ho Kim, Jae Soo Yoo: MIN-Entropy: A New Signature File Declustering Algorithm for Intra-Query Parallelism. DASFAA 1997: 235-242
  5. Paolo Ciaccia, Paolo Tiberio, Pavel Zezula: Declustering of Key-Based Partitioned Signature Files. ACM Trans. Database Syst. 21(3): 295-338(1996)
  6. Peter Muth, Achim Kraiss, Gerhard Weikum: LoT: Dynamic Declustering of TSB-Tree Nodes for Parallel Access to Temporal Data. EDBT 1996: 553-572
  7. Gerhard Weikum: Tutorial on Parallel Database Systems. ICDT 1995: 33-37
  8. Jaideep Srivastava, Thomas M. Niccum, Bhaskar Himatsingka: Data Declustering in PADMA: A PArallel Database MAnager. IEEE Data Eng. Bull. 17(3): 3-13(1994)
  9. Vram Kouramajian, Ramez Elmasri, Anurag Chaudhry: Declustering Techniques for Parallelizing Temporal Access Structures. ICDE 1994: 232-242
  10. Bhaskar Himatsingka, Jaideep Srivastava: Performance Evaluation of Grid Based Multi-Attibute Record Declustering Methods. ICDE 1994: 356-365
  11. Pavel Zezula, Paolo Ciaccia, Paolo Tiberio: Hamming Filters: A Dynamic Signature File Organization for Parallel Stores. VLDB 1993: 314-327
  12. Shaibal Roy: Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning. PODS 1991: 259-267
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:14 2008