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
  author    = {Jianzhong Li and
               Jaideep Srivastava and
               Doron Rotem},
  editor    = {Li-Yan Yuan},
  title     = {CMD: A Multidimensional Declustering Method for Parallel Data
  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,}


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 ... BibTeX

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 BibTeX


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

Referenced by

  1. Mikhail J. Atallah, Sunil Prabhakar: (Almost) Optimal Parallel Block Access for Range Queries. PODS 2000: 205-215
  2. Bongki Moon, Joel H. Saltz: Scalability Analysis of Declustering Methods for Multidimensional Range Queries. IEEE Trans. Knowl. Data Eng. 10(2): 310-327(1998)
  3. Sunil Prabhakar, Khaled A. S. Abdel-Ghaffar, Divyakant Agrawal, Amr El Abbadi: Cyclic Allocation of Two-Dimensional Data. ICDE 1998: 94-101
  4. Junping Sun, William I. Grosky: Dynamic Maintenance of Multidimensional Range Data Partitioning for Parallel Data Processing. DOLAP 1998: 72-79
  5. Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Allocation of Two-Dimensional Data. ICDT 1997: 409-418
  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. Duen-Ren Liu, Shashi Shekhar: A Similarity Graph-Based Approach to Declustering Problems and Its Application towards Paralleling Grid Files. ICDE 1995: 373-381
  9. Jeong-Ki Kim, Jae-Woo Chang: A New Parallel Signature File Method for Efficient Information Retrieval. CIKM 1995: 66-73
  10. Won S. Lee, Phillip C.-Y. Sheu: An Object-Oriented Query Evaluation Scheme for Logical Databases in Massively Parallel Environment. IEEE Trans. Knowl. Data Eng. 6(1): 181-187(1994)
  11. Jaideep Srivastava, Thomas M. Niccum, Bhaskar Himatsingka: Data Declustering in PADMA: A PArallel Database MAnager. IEEE Data Eng. Bull. 17(3): 3-13(1994)
  12. Kent E. Seamons, Marianne Winslett: Physical Schemas for Large Multidimensional Arrays in Scientific Computing Applications. SSDBM 1994: 218-227
  13. Vram Kouramajian, Ramez Elmasri, Anurag Chaudhry: Declustering Techniques for Parallelizing Temporal Access Structures. ICDE 1994: 232-242
  14. Bhaskar Himatsingka, Jaideep Srivastava: Performance Evaluation of Grid Based Multi-Attibute Record Declustering Methods. ICDE 1994: 356-365
  15. Pavel Zezula, Paolo Ciaccia, Paolo Tiberio: Hamming Filters: A Dynamic Signature File Organization for Parallel Stores. VLDB 1993: 314-327
  16. Jianzhong Li, Doron Rotem, Jaideep Srivastava: Algorithms for Loading Parallel Grid Files. SIGMOD Conference 1993: 347-356
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:50 2009