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@inproceedings{DBLP:conf/dolap/SunG98,
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, http://doi.acm.org/10.1145/294260.294275},
crossref = {DBLP:conf/dolap/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
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.
CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
DOLAP '98, ACM First International Workshop on Data Warehousing and OLAP, November 7, 1998, Bethesda, Maryland, USA, Proceedings.
ACM 1998
Contents 
Online Edition
Citation Page
References
- [1]
- Jon Louis Bentley:
Multidimensional Binary Search Trees Used for Associative Searching.
Commun. ACM 18(9): 509-517(1975)
- [2]
- Jon Louis Bentley:
Multidimensional Binary Search Trees in Database Applications.
IEEE Trans. Software Eng. 5(4): 333-340(1979)
- [3]
- Luc Bouganim, Daniela Florescu, Patrick Valduriez:
Dynamic Load Balancing in Hierarchical Parallel Database Systems.
VLDB 1996: 436-447
- [4]
- George Colliat:
OLAP, Relational, and Multidimensional Database Systems.
SIGMOD Record 25(3): 64-69(1996)
- [5]
- David J. DeWitt, Jim Gray:
Parallel Database Systems: The Future of High Performance Database Systems.
Commun. ACM 35(6): 85-98(1992)
- [6]
- Michael Freeston:
The BANG File: A New Kind of Grid File.
SIGMOD Conference 1987: 260-269
- [7]
- ...
- [8]
- 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)
- [9]
- William I. Grosky, Junping Sun, Farshad Fotouhi:
Dynamic Selectivity Estimation for Multidimensional Queries.
FODO 1993: 231-246
- [10]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
- [11]
- 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)
- [12]
- Brigitte Kröll, Peter Widmayer:
Distributing a Search Tree Among a Growing Number of Processors.
SIGMOD Conference 1994: 265-276
- [13]
- Jianzhong Li, Jaideep Srivastava, Doron Rotem:
CMD: A Multidimensional Declustering Method for Parallel Data Systems.
VLDB 1992: 3-14
- [14]
- Hongjun Lu, Kian-Lee Tan:
Dynamic and Load-balanced Task-Oriented Datbase Query Processing in Parallel Systems.
EDBT 1992: 357-372
- [15]
- ...
- [16]
- 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)
- [17]
- 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)
- [18]
- ...
- [19]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18
- [20]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518
- [21]
- ...
- [22]
- Patrick Valduriez:
Parallel Database Systems: Open Problems and New Issues.
Distributed and Parallel Databases 1(2): 137-165(1993)
- [23]
- 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
- [24]
- Kyu-Young Whang, Ravi Krishnamurthy:
The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure.
DASFAA 1991: 449-459
- [25]
- ...
- [26]
- Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton:
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates.
SIGMOD Conference 1997: 159-170
Last update Thu May 24 04:16:29 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
