ACM SIGMOD Anthology VLDB dblp.uni-trier.de

CMD: A Multidimensional Declustering Method for Parallel Data Systems.

Jianzhong Li, Jaideep Srivastava, Doron Rotem: CMD: A Multidimensional Declustering Method for Parallel Data Systems. VLDB 1992: 3-14
@inproceedings{DBLP:conf/vldb/LiSR92,
  author    = {Jianzhong Li and
               Jaideep Srivastava and
               Doron Rotem},
  editor    = {Li-Yan Yuan},
  title     = {CMD: A Multidimensional Declustering Method for Parallel Data
               Systems},
  booktitle = {18th International Conference on Very Large Data Bases, August
               23-27, 1992, Vancouver, Canada, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1992},
  isbn      = {1-55860-151-1},
  pages     = {3-14},
  ee        = {db/conf/vldb/LiSR92.html},
  crossref  = {DBLP:conf/vldb/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

I/O parallelism appears to be a promising approach to achieving high performance in parallel database systems. In such systems, it is essential to decluster database files into fragments andspread them across multiple disks so that the DBMS software can exploit the I/Obandwidth reading and writing the disks in parallel. In this paper, we consider the problem of declustering multidimensional data ona parallel disk system. Since the multidimensional range query is the main work-horse for applications accessing such data, our aim is to provide efficient support for it. A new declustering method for parallel disk systems, called coordinate modulo distribution (CMD), is proposed. Our analysis shows that the method achieves optimum parallelism for a very highpercentage of range queries on multidimensional data, if the distribution of data on each dimension is stationary. We have derived the exact conditions under which optimality is achieved. Also provided are the worst and average case bounds on multidimensional range query performance. Experimental results show that the method achieves near optimum performance in almost all cases even when the stationarity assumption does not hold. Details of the parallel algorithms for range query processing and data maintenance are also provided.

Copyright © 1992 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Li-Yan Yuan (Ed.): 18th International Conference on Very Large Data Bases, August 23-27, 1992, Vancouver, Canada, Proceedings. Morgan Kaufmann 1992, ISBN 1-55860-151-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
...
[3]
Mee Yee Chan: A Note on Redundant Disk Modulo Allocation. Inf. Process. Lett. 20(3): 121-123(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
Chin-Chen Chang, L. S. Lian: On Strict Optimality Property of Allocating Binary Cartesian Product Files on Multiple Disk Systems. FODO 1985: 159-175 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Michelle Y. Kim: Synchronized Disk Interleaving. IEEE Trans. Computers 35(11): 978-988(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Miron Livny, Setrag Khoshafian, Haran Boral: Multi-Disk Management Algorithms. SIGMETRICS 1987: 69-77 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Kenneth Salem, Hector Garcia-Molina: Disk Striping. ICDE 1986: 336-342 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Sakti Pramanik, Myoung-Ho Kim: Parallel Processing of Large Node B-Trees. IEEE Trans. Computers 39(9): 1208-1212(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Bernhard Seeger, Per-Åke Larson: Multi-Disk B-trees. SIGMOD Conference 1991: 436-445 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Kien A. Hua, Chiang Lee: An Adaptive Data Placement Scheme for Parallel Database Computer Systems. VLDB 1990: 493-506 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
...
[21]
...
[22]
David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
...

Copyright © Tue Mar 16 02:22:02 2010 by Michael Ley (ley@uni-trier.de)