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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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)
[2]: ...
[3]: Mee Yee Chan: A Note on Redundant Disk Modulo Allocation. Inf. Process. Lett. 20(3): 121-123(1985)
[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
[6]: ...
[7]: C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
[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)
[9]: George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108
[10]: Michelle Y. Kim: Synchronized Disk Interleaving. IEEE Trans. Computers 35(11): 978-988(1986)
[11]: Miron Livny, Setrag Khoshafian, Haran Boral: Multi-Disk Management Algorithms. SIGMETRICS 1987: 69-77
[12]: Kenneth Salem, Hector Garcia-Molina: Disk Striping. ICDE 1986: 336-342
[13]: David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116
[14]: Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258
[15]: Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182
[16]: Sakti Pramanik, Myoung-Ho Kim: Parallel Processing of Large Node B-Trees. IEEE Trans. Computers 39(9): 1208-1212(1990)
[17]: Bernhard Seeger, Per-Åke Larson: Multi-Disk B-trees. SIGMOD Conference 1991: 436-445
[18]: Kien A. Hua, Chiang Lee: An Adaptive Data Placement Scheme for Parallel Database Computer Systems. VLDB 1990: 493-506
[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
[23]: ...