• Articles • Previous Articles     Next Articles

Parallel Data Cube Storage Structure for Range Sum Queries and Dynamic Updates

Hong Gao and Jian-Zhong Li   

  1. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, P.R. China
  • Received:2004-12-02 Online:2005-05-10 Published:2005-05-10

I/O parallelism is considered to be a promising approach to achievinghigh performance in parallel data warehousing systems where hugeamounts of data and complex analytical queries have to be processed.This paper proposes a parallel secondary data cube storage structure(PHC for short) to efficiently support the processing of range sumqueries and dynamic updates on data cube using parallel computingsystems. Based on PHC, two parallel algorithms for processing range sumqueries and updates are proposed also. Both the algorithms have the same time complexity, O(logdn/P). The analytical and experimentalresults show that PHC and the parallel algorithms have high performanceand achieve optimum speedup.

Key words: Proof by consistency; inductive soundness; strong inductive model; congruence relation; equation;

[1] Codd E F. Providing OLAP (on-line analytical processing) touser-analysts: An IT mandate. Technical Report, E.F. Codd andAssociates, 1993.

[2] Gray J et al. Data cube: A relational aggregation operatorgeneralizing group-by, cross-tab and sub-totals. Data Mining andKnowledge Discovery, 1997, 1(1): 29--54.

[3] Ho C T, Agrawal R, Megiddo R, Srikant R. Range queriesin OLAP data cubes. In Proc. The Int. ACM SIGMODConference, Tucson, Arizona, May 1997, pp.73--88.

[4] Geffner S, Agrawal D, Abbadi A, Smith T. Relativeprefix sums: An efficient approach for querying dynamic OLAP datacubes. In Proc. The 15th Int. Conference on DataEngineering, Sydney, Australia, March 1999, pp.328--335.

[5] Chan C Y, Ioannidis Y E. Hierarchical cubes for range-sumqueries. In Proc. The 25th VLDB Conference, Edinburgh, Scotland,UK, September 1999, pp.675--686,

[6] Chun S J, Chung C W, Lee J H, Lee S L. Dynamic updatecube for range-sum queries. In Proc. 27th VLDB Conf., Rome,Italy, Sept. 2001, pp.521--530.

[7] Liang W, Wang H, Orlowska M E. Range queries in dynamicOLAP data cubes. Data and Knowledge Engineering, 2000, 34: 21--38.

[8] Li J Z, Gao H. Hierarchical data cube for range queries anddynamic updates. In Proc. The East-European Conference on Advances inDatabases and Information Systems (ADBIS), Dresden, Germany,2003, 9: 61--75.

[9] Jens Albrecht, Wolfgang Sporer. Aggregate-based queryprocessing in a parallel data warehouse server. In the10th International Workshop on Database and Expert SystemsApplications, Florence, Italy, September, 1999, pp.40--44.

[10] Hector G M, Wilburt J L, Janet L W et al. Distributedand parallel computing issues in data warehousing.http://www-db.stanford.edu/warehousing/warehouse.html.

[11] Sun J, Grosky W I. Dynamic Maintenance of MultidimensionalRange Data Partitioning for Parallel Data Processing. In Proc.DOLAP98, Washington DC, USA, Nov.1998, pp.72--79.

[12] Muto S, Kitsuregawa M. A dynamic load balancing strategy forparallel datacube computation. In Proc. DOLAP99, Kansas,Missouri, USA, Nov. 1999, pp.67--72.

[13] Rohm U, Bohm K et al. OLAP query routing and physicaldesign in a DB cluster. EDBT, 2000, pp.254--268.

[14] Dehne F, Eavis T, Rau-Chaplin A. A cluster architecture forparallel data warehousing. In Proc. International Conference on ClusterComputing and the Grid (CCGrid 2001), Brisbane, Australia, May 2001,p.161.

[15] Goil S, Choudhary A. An infrastructure for scalableparallel multidimensional analysis. In Proc. 11th InternationalConference on Scientific and Statistical Database Management, Cleveland, Ohio, USA, July, 1999, pp.102--111.

[16] Gao H, Li J Z. Hierarchical data cube for range sumqueries. Journal of Software, 2003, 7: 1258--1268.
[1] Hong-Xing Qin, Jin-Long He, Meng-Hui Wang, Yu Dai, Zhi-Yong Ran. A Gradient-Domain Based Geometry Processing Framework for Point Clouds [J]. , 2018, 33(4): 863-872.
[2] Jie Liang and Hong Qian. Computational Cellular Dynamics Based on the Chemical Master Equation: A Challenge for Understanding Complexity [J]. , 2010, 25(1): 154-168.
[3] Chandrajit L. Bajaj, Guo-Liang Xu, and Qin Zhang. Higher-Order Level-Set Method and Its Application in Biomolecular Surfaces Construction [J]. , 2008, 23(6 ): 1026-1036 .
[4] Wen-Tsun Wu and Xiao-Shan Gao. Automated Reasoning and Equation Solving with the Characteristic Set Method [J]. , 2006, 21(5): 756-764 .
[5] Zhong-Xuan Liu, Shi-Guo Lian, and Zhen Ren. Quaternion Diffusion for Color Image Filtering [J]. , 2006, 21(1): 126-136 .
[6] Jian-Jun Zhang and Li-Hua You. PDE Surface Generation with Combined Closed and Non-Closed Form Solutions [J]. , 2004, 19(5): 0-0.
[7] LI Guodong (李国东) and ZHANG Defu (张德富). Distributing and Scheduling Divisible Task on Parallel Communicating Processors [J]. , 2002, 17(6): 0-0.
[8] ZHANG Guoqiang(张国强)and CHEN Yixiang(陈仪香). Domains via Graphs [J]. , 2001, 16(6): 0-0.
[9] SUN Yongqiang(孙永强),LIN Kai(林凯)and LU Chaojun(陆朝俊). Partial Completion of Equational Theories [J]. , 2000, 15(6): 0-0.
[10] SUN Yongqiang; LIN Kai; LU Chaojun;. Partial Completion of Equational Theories [J]. , 2000, 15(6): 552-559.
[11] TING Jing'an;. A Neural Paradigm for Time-Varying Motion Segmentation [J]. , 1999, 14(6): 539-550.
[12] He Ziqiang;. Anothr Definition of Order-Sorted Algebra [J]. , 1998, 13(6): 547-551.
[13] Xu Yingqing; Hans Dehlinger; Qi Dongxu; Liu Shenquan;. Line-Art and its Mathematical Models [J]. , 1998, 13(1): 73-78.
[14] Xu Yingqing; Su Cheng; Qi Dongxu; Li Hua; Liu Shenquan;. Simulation of Waters [J]. , 1997, 12(5): 408-413.
[15] Cai Wenli; Shi Jiaoying;. Composed Scattering Model for Direct Volume Rendering [J]. , 1996, 11(5): 433-442.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved