• Articles • Previous Articles     Next Articles

Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time

Sheng-En Li1,2 and Shan Wang2   

  1. 1Department of Computer Science and Technology, Shandong Institute of Architecture and Engineering, Jinan 250014, P.R. China
    2School of Information, Renmin University, Beijing 100872, P.R. China
  • Received:2004-02-05 Revised:2004-08-15 Online:2005-05-10 Published:2005-05-10

The results of data cube will occupy huge amount ofdisk space when the base table is of a large number of attributes. Anew type of data cube, compact data cube like condensed cube andquotient cube, was proposed to solve the problem. It compresses data cubedramatically. However, its query cost is so high that it cannot be usedin most applications. This paper introduces the semi-closed cube to reducethe size of data cube and achieve almost the same queryresponse time as the data cube does. Semi-closed cube is a generalizationof condensed cube and quotient cube and is constructed from a quotientcube. When the query cost of quotient cube is higher than a giventhreshold, semi-closed cube selects some views and picks a fellow foreach of them. All the tuples of those views are materialized exceptthose closed by their fellows. To find a tuple of those views, users onlyneed to scan the view and its fellow. Thus, their query performance isimproved. Experiments were conducted using a real-world data set. Theresults show that semi-closed cube is an effective approach of datacube.

Key words: Hypercube; cube-connected cycles; linear complement permutation; routing algorithm; conflict; complexity;



[1] Gray J, Bosworth A, Layman A, Pirahesh H. Data cube: Arelational aggregation operator generalizing group-by, cross-tab, andsub-totals. In Proc. 12th Int. Conf. Data Engineering, NewOrleans, Louisiana, Feb. 26--Mar. 1, 1996, pp.152--159.

[2] Harinarayan V, Rajaraman A, Ullman J D. Implementing data cubesefficiently. In Proc. ACM SIGMOD Int. Conf. Management ofData, Montreal, Canada, June 4--6, 1996, pp.205--216.

[3] Shukla A, Deshpande P M, Naughton J F. Materialized viewselection for multidimensional datasets. In Proc. 24th Int. Conf.Very Large Data Base, New York City, NY, August 24--27, 1998,pp.488--499.

[4] Wei Wang, Hongjun Lu, Jianlin Feng, Jeffrey Xu Yu. Condensed cube:An effective approach to reducing data cube size. In Proc. 18th Int.Conf. Data Engineering, San Jose, CA, February 26--March 1,2002, pp.155--165.

[5] Lakshmanan L V S, Pei Jian, Han Jiawei. Quotient cube: How tosummarize the semantics of a data cube. In Proc. 23rd Int. Conf.Very Large Data Bases, Hong Kong, China, August 20--23, 2002,pp.778--789.

[6] Vitter J S, Wang M. Data cube approximation and histogram viawavelets. In Proc. 7th Int. Conf. Information andKnowledge Management, Bethesda, Maryland, November 3--7, 1998,pp.96--104.

[7]Kotidis Y, Roussopoulos N. An alternative storage organizationfor ROLAP aggregate views based on cubetrees. In Proc. ACM SIGMOD Int.Conf. Management of Data, Seattle, Washington, June 2--4, 1998,pp.249--258.

[8] Sismanis Y, Deligiannakis A, Roussopoulos N, Kotidis Y. Dwarf:Shrinking the PetaCube. In Proc. ACM SIGMOD Int. Conf.Management of Data, Madison, Wisconsin, June 3--6, 2002,pp.464--475.

[9] Lakshmanan L V S, Pei Jian, Zhao Yan. QC-Trees: An efficientsummary structure for semantic OLAP. In Proc. ACM SIGMOD Int.Conf. Management of Data, San Diego, California, June 9--12,2003, pp.64--75.

[10] Li Sheng-En, Wang Shan. Research on closed data cubetechnology. Journal of Software, 2004, 15(8): 1165--1171.

[11] Beyer K, Ramakrishnan R. Bottom-up computation of sparse andIceberg CUBEs. In Proc. ACM SIGMOD Int. Conf. Management ofData, Philadelphia, Pennsylvania, June 1--3, 1999, pp.359--370.

[12] Hahn C, Warren S, London J. Edited synoptic cloud reports fromships and land stations over the globe. Http://cdiac. Esd.ornl.gov/cdiac/ndps/ndp026b.html
[1] Jin-Qi Zhu, Li Lu, Chun-Mei Ma. From Interest to Location: Neighbor-Based Friend Recommendation in Social Media [J]. , 2015, 30(6): 1188-1200.
[2] Lei Zhao, Ji-Wen Yang. Resources Snapshot Model for Concurrent Transactions in Multi-Core Processors [J]. , 2013, 28(1): 106-118.
[3] David P. Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field [J]. , 2012, 27(4): 678-686.
[4] You-Ming Qiao (乔友明), Jayalal Sarma M.N., and Bang-Sheng Tang (唐邦晟). On Isomorphism Testing of Groups with Normal Hall Subgroups [J]. , 2012, 27(4): 687-701.
[5] Yi Wu (吴奕). Pricing Loss Leaders Can be Hard [J]. , 2012, 27(4): 718-726.
[6] Hossein Ajorloo and Abolfazl Lakdashti. HBIR: Hypercube-Based Image Retrieval [J]. , 2012, 27(1): 147-162.
[7] Yu-Ping Shen (沈榆平) and Xi-Shun Zhao (赵希顺). NP-Logic Systems and Model-Equivalence Reductions [J]. , 2010, 25(6): 1321-1326.
[8] Yu-Tao Ma (马于涛), Member, CCF, ACM, Ke-Qing He (何克清), Senior Member, CCF, IEEE, Bing Li (李兵), Senior Member, CCF, Jing Liu (刘婧) and Xiao-Yan Zhou (周晓燕). A Hybrid Set of Complexity Metrics for Large-Scale Object-Oriented Software Systems [J]. , 2010, 25(6): 1184-1201.
[9] Chong Long(龙 翀), Min-Lie Huang(黄民烈), Xiao-Yan Zhu(朱小燕), Member, CCF and Ming Li(李 明), Fellow, ACM, IEEE. A New Approach for Multi-Document Update Summarization [J]. , 2010, 25(4): 739-749.
[10] Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Thöle, and Henning Thomas. Approximation Algorithms for 3D Orthogonal Knapsack [J]. , 2008, 23(5 ): 749-762 .
[11] Jian-Xin Wang, Xiao-Shuang Xu, and Jian-Er Chen. Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs [J]. , 2008, 23(5 ): 763-768 .
[12] Ji-Gang Wu, Thambipillai Srikanthan, and Guang-Wei Zou. New Model and Algorithm for Hardware/Software Partitioning [J]. , 2008, 23(4 ): 644-651 .
[13] You-Jian Zhao, Zu-Hui Yue, and Jian-Ping Wu. Research on Next-Generation Scalable Routers Implemented with H-Torus Topology [J]. , 2008, 23(4 ): 684-.
[14] Jaime Lloret, Miguel Garcia, Jesus Tomás, and Fernando Boronat. GBP-WAHSN: A Group-Based Protocol for Large Wireless Ad Hoc and Sensor Networks [J]. , 2008, 23(3): 461-480 .
[15] Wen-Ling Wu, Wen-Tao Zhang, and Deng-Guo Feng. Impossible Differential Cryptanalysis of Reduced-Round ARIA and Camellia [J]. , 2007, 22(3): 449-456 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[7] Han Jianchao; Shi Zhongzhi;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[8] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[9] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[10] Shang Lujun; Xu Lihui;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

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