Dynamic Maintenance of Multidimensional Range Data Partitioning for Parallel Data Processing.

Junping Sun, William I. Grosky: Dynamic Maintenance of Multidimensional Range Data Partitioning for Parallel Data Processing. DOLAP 1998: 72-79
  author    = {Junping Sun and
               William I. Grosky},
  title     = {Dynamic Maintenance of Multidimensional Range Data Partitioning
               for Parallel Data Processing},
  booktitle = {DOLAP '98, ACM First International Workshop on Data Warehousing
               and OLAP, November 7, 1998, Bethesda, Maryland, USA, Proceedings},
  publisher = {ACM},
  year      = {1998},
  pages     = {72-79},
  ee        = {db/conf/dolap/SunG98.html,},
  crossref  = {DBLP:conf/dolap/98},
  bibsource = {DBLP,}


Star schema has been a typical model for both online transaction processing in traditional databases and online analytical processing in large data warehouses. In the star schema, the dominant volumes of data are stored in the relationship table in terms of databases or the fact table in terms of data warehouses. Sometimes this relationship or fact table is called multidimensional table, cube, or data set. In this paper, we present a parallel method to partition the fact table in terms of multidimensional space for parallel star query processing. Also a dynamic approach to maintain load balance among all the processors is given in terms of a set of heuristics for the cases when the fact table undergoes frequent updates such as insertions/deletions. The multidimensionally partitioned data sets in the fact table are stored as leaf nodes in a multidimensional range tree, and each data set stored in the leaf node is mapped into each processor for parallel data partitioning and star query processing. As far as load balance is concerned in each of processors, we try to maintain the distribution of data volumes as uniform as possible by the set of heuristics for the star query processing in OLAP.

Copyright © 1998 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

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

DOLAP '98, ACM First International Workshop on Data Warehousing and OLAP, November 7, 1998, Bethesda, Maryland, USA, Proceedings. ACM 1998
Contents BibTeX

Online Edition

Citation Page BibTeX


Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX
Luc Bouganim, Daniela Florescu, Patrick Valduriez: Dynamic Load Balancing in Hierarchical Parallel Database Systems. VLDB 1996: 436-447 BibTeX
George Colliat: OLAP, Relational, and Multidimensional Database Systems. SIGMOD Record 25(3): 64-69(1996) BibTeX
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) BibTeX
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, Hamid Pirahesh: Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals. Data Min. Knowl. Discov. 1(1): 29-53(1997) BibTeX
William I. Grosky, Junping Sun, Farshad Fotouhi: Dynamic Selectivity Estimation for Multidimensional Queries. FODO 1993: 231-246 BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Kien A. Hua, Chiang Lee, Chau M. Hua: Dynamic Load Balancing in Multicomputer Database Systems Using Partition Tuning. IEEE Trans. Knowl. Data Eng. 7(6): 968-983(1995) BibTeX
Brigitte Kröll, Peter Widmayer: Distributing a Search Tree Among a Growing Number of Processors. SIGMOD Conference 1994: 265-276 BibTeX
Jianzhong Li, Jaideep Srivastava, Doron Rotem: CMD: A Multidimensional Declustering Method for Parallel Data Systems. VLDB 1992: 3-14 BibTeX
Hongjun Lu, Kian-Lee Tan: Dynamic and Load-balanced Task-Oriented Datbase Query Processing in Parallel Systems. EDBT 1992: 357-372 BibTeX
Yasuaki Nakamura, Shigeru Abe, Yutaka Ohsawa, Masao Sakauchi: A Balanced Hierarchical Data Structure for Multidimensional Data with Highly Efficient Dynamic Characteristics. IEEE Trans. Knowl. Data Eng. 5(4): 682-694(1993) 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
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993) BibTeX
Christopher B. Walton, Alfred G. Dale, Roy M. Jenevein: A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins. VLDB 1991: 537-548 BibTeX
Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459 BibTeX
Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton: An Array-Based Algorithm for Simultaneous Multidimensional Aggregates. SIGMOD Conference 1997: 159-170 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
DOLAP 1998 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:07:20 2009