快速計(jì)算濃縮立方體的方法

涂建新，游進(jìn)國(guó)

(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南昆明 650500)

快速計(jì)算濃縮立方體的方法

涂建新，游進(jìn)國(guó)

(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南昆明 650500)

為了能夠更快地生成濃縮立方體，提出了一種新的通過各個(gè)值的頻率對(duì)格子的空間進(jìn)行分解的MM－Cubing算法:用一種計(jì)數(shù)、排序算法和相關(guān)的數(shù)據(jù)結(jié)構(gòu)來計(jì)算每一個(gè)值出現(xiàn)的頻率，同時(shí)提供一種數(shù)據(jù)結(jié)構(gòu)來方便主要值的選取和計(jì)算其子空間;選取主要值，聚會(huì)稠密的子空間，遞歸調(diào)用稀疏子空間.實(shí)驗(yàn)結(jié)果表明:MM－Cubing算法優(yōu)于MinCube算法和SQCube算法.

濃縮立方體;格子;空間;算法

0 引言

自從數(shù)據(jù)倉(cāng)庫(kù)中聯(lián)機(jī)分析處理(On－Line Analysis Processing，以下簡(jiǎn)稱:OLAP)和數(shù)據(jù)立方體的提出，有效計(jì)算數(shù)據(jù)立方體成為一個(gè)熱門話題，數(shù)據(jù)立方體的計(jì)算方法有:用簡(jiǎn)單或者復(fù)雜的值計(jì)算完全和冰上立方體［1－2］;對(duì)壓縮的數(shù)據(jù)立方體進(jìn)行近似計(jì)算，如準(zhǔn)立方體［3］;用索引進(jìn)行封閉立方體計(jì)算，如濃縮立方體、侏儒立方體和商立方體［4－5］;選擇物化視圖［6］.

語義OLAP的思想被許多學(xué)者提出，即對(duì)整個(gè)數(shù)據(jù)立方體的數(shù)據(jù)用一種特殊的壓縮存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，這種結(jié)構(gòu)不但能對(duì)所有立方體的元組進(jìn)行表示和生成，而且對(duì)整個(gè)數(shù)據(jù)立方的操作性能(如查詢、維護(hù)等方面)有極大的改善，比如濃縮立方體、商立方體樹等.濃縮數(shù)據(jù)立方體產(chǎn)生的單一元組分區(qū)通過使用聚合計(jì)算，該元組將該分區(qū)對(duì)應(yīng)的屬性及其超集對(duì)應(yīng)的元組都包含在其中，從而降低數(shù)據(jù)立方體的大小.商立方體樹［7］使用的是等價(jià)類，它把具有相同聚合值的元組放在一起，同時(shí)將每一個(gè)等價(jià)類的在語義上對(duì)應(yīng)的上界計(jì)算出來，進(jìn)而降低了數(shù)據(jù)立方體對(duì)存儲(chǔ)空間的需求.

Wang Wei等人［8］于2002年基于基本單一元組，介紹了濃縮數(shù)據(jù)立方體應(yīng)該滿足的性質(zhì)，并展示了一種生成最小濃縮數(shù)據(jù)立方的MinCube算法.因?yàn)镸inCube算法生成最小濃縮數(shù)據(jù)立方體有一定困難，所以作者決定用壓縮率的降低來換取體積的減少，提出了并不保證生成最小濃縮立方體的啟發(fā)式算法 ButtomUpBST以及其優(yōu)化算法ReorderButtomUpBST，這兩個(gè)算法雖然速度很快，但壓縮率明顯低于最小濃縮數(shù)據(jù)立方體的壓縮率.

王琢等人于2005年在ButtomUpBST算法的基礎(chǔ)上，提出一個(gè)可以比較快速生成最小濃縮數(shù)據(jù)立方的SQCube算法［9］，但是該算法需要進(jìn)一步的優(yōu)化.

本文根據(jù)在一個(gè)維度中每一個(gè)值出現(xiàn)的頻率不同，從而對(duì)格子空間進(jìn)行分解，提出一種用MM－Cubing計(jì)算濃縮立方體的方法，實(shí)驗(yàn)結(jié)果表明該方法比Mincube、ButtomUpBST和SQCube算法能更好生成濃縮立方體.

1 分解格子空間

在數(shù)學(xué)上，每一個(gè)單元可以用(a，b，c，d，…)來表示:a、b、c和d是一個(gè)與其維度相對(duì)應(yīng)的值，或者用*來表示所有值.這些單元形成格子空間，每一個(gè)格子空間的基數(shù)等于1加上輸入元組相對(duì)應(yīng)的每一個(gè)維度上的基數(shù).

MinCube、ButtomUpBST和SQCube算法是自上而下、自底向上或者同時(shí)使用，而忽略了數(shù)據(jù)的值密度.在一個(gè)維度中，對(duì)于所有的非*值，有些值出現(xiàn)的頻率比較高，而有些值出現(xiàn)的頻率很低，為了使執(zhí)行效率更高和有很好的可擴(kuò)展性，計(jì)算濃縮立方體，有必要對(duì)于不同頻率的值進(jìn)行不同的處理.頻率值的大小反映了單元的頻率，將頻率高的值作為主要值(major value)，頻率低的值作為次要值(minor value).用D表示輸入元組的維度數(shù)量，在主要值與次要值之間對(duì)格子空間進(jìn)行分解，它們的值用分開點(diǎn)來表示，新的網(wǎng)格結(jié)構(gòu)有3D個(gè)節(jié)點(diǎn).用M表示主要值，I表示次要值，*表示所有值.一個(gè)3-D格子可以表示為({M，I，*}，{M，I，*}，{M，I，*})，一個(gè)次要值也應(yīng)該至少出現(xiàn)1次，一個(gè)小于1的值不會(huì)出現(xiàn)在濃縮立方體中.

由于一個(gè)主要值出現(xiàn)的頻率很高，所以與*共享計(jì)算是比較好的;而對(duì)于一個(gè)次要值，需要進(jìn)一步的計(jì)算.因此，將格子空間分為以下4個(gè)子空間:({M，*}，{M，*}，{M，*})，(I，{M，I，*}，{M，I，*})，({M，*}，I，{M，I，*})，({M，*}，{M，*}，I).這些子空間沒有交集，所有的子空間之和剛好是原始格子空間，如圖1所示.

圖1 (1)傳統(tǒng)格子空間(2)傳統(tǒng)格子樹(3)分解新的格子空間Fig.1 (1)Traditional lattice space(2)Traditional lattice tree(3)Factorization of the new lattice space

在第一個(gè)子空間({M，*}，{M，*}，{M，*})中，每一個(gè)維度的值是一個(gè)主要值或者是*，在這個(gè)子空間中的數(shù)據(jù)出現(xiàn)的頻率可能會(huì)很高，子空間相對(duì)密集，為密集子空間.

在第二個(gè)子空間(I，{M，I，*}，{M，I，*})中，所有的值在第一個(gè)維中是次要值，數(shù)據(jù)出現(xiàn)的頻率不會(huì)很高，由于次要值的值不是很大.

第三個(gè)子空間({M，*}，I，{M，I，*})類似于第二個(gè)子空間，數(shù)據(jù)出現(xiàn)的頻率不會(huì)很大，但是有一點(diǎn)不同，在第一個(gè)維度中其值只能是主要值和*.

第四個(gè)子空間({M，*}，{M，*}，I)除了有兩個(gè)維度的值必須是主要值和*外，類似于第三個(gè)子空間.

第一個(gè)子空間為密集子空間，其余三個(gè)子空間為稀疏子空間，在稀疏子空間中可以通過遞歸調(diào)用探測(cè)其他的密集子空間.

格子空間的分解方法并不是唯一的，也可以將格子空間分解為以下5個(gè)子空間:

2 MM-Cubing算法

MM－Cubing算法:首先按照?qǐng)D1中(3)的方法分解格子空間，然后計(jì)算聚合密集子空間和遞歸調(diào)用稀疏子空間.

在分解格子空間之前，首先應(yīng)該計(jì)算在每一個(gè)維度中值出現(xiàn)的頻率，然后按照從大到小進(jìn)行排序，最后確定哪個(gè)值是主要值或次要值.

MM－Cubing計(jì)算濃縮立方體算法輸入的是一個(gè)關(guān)系表R，輸出的是濃縮立方體.

2.1 計(jì)數(shù)和排序

選擇一種數(shù)據(jù)結(jié)構(gòu)來計(jì)算每一個(gè)值的頻率，從而選擇主要值并計(jì)算子空間.

假設(shè)有表1所示的輸入數(shù)據(jù)，則輸出結(jié)果如表2所示.

表1 輸入數(shù)據(jù)Table 1 Data of input

表2 輸出結(jié)果Table 2 Result of output

數(shù)據(jù)結(jié)構(gòu)的選擇對(duì)于性能提升有很大的影響，因此使用桶排序算法同時(shí)使用兩個(gè)數(shù)組(一個(gè)大小為一個(gè)維度基準(zhǔn)的大小和另一個(gè)的大小為輸入元組鏈表的大小)進(jìn)行計(jì)算，輸出的數(shù)據(jù)結(jié)構(gòu)是數(shù)組的結(jié)構(gòu)和元組ID的數(shù)組，稱之為共享數(shù)組，如圖2所示.

圖2 共享數(shù)組結(jié)構(gòu)Fig.2 Shared array structure

2.2 選擇主要值

主要值賦值應(yīng)該保證運(yùn)行時(shí)間最小.然而這個(gè)算法是遞歸的，很難估計(jì)遞歸調(diào)用的時(shí)間，由于這依賴于在子空間中主要值的賦值，因此給出一個(gè)主要值選擇的規(guī)則——在一個(gè)維度中的所有主要值應(yīng)該大于在相同維度中的次要值，這就是通過頻率來對(duì)值進(jìn)行排序的原因.

運(yùn)用一個(gè)啟發(fā)式的方法來選擇主要值:定義一個(gè)量度，work_done完成工作作為總量，完成工作通過聚合

式(1)中:T為元組的數(shù)量，sum［i］為在維度i中主要值的元組個(gè)數(shù)，D為維度的數(shù)量.

聚合表的大小可以計(jì)算為∏i(1+MC［i］)，其中MC［i］為在第i個(gè)維度中主要值的數(shù)量.

希望主要值是最大值而聚合表的大小不會(huì)超過一個(gè)常量的大小，定義的完成工作來自于這樣一個(gè)算法:用一個(gè)哈希表來存儲(chǔ)所有的聚合單元，這個(gè)哈希表的鍵值是聚合單元自己，值是這個(gè)單元的出現(xiàn)頻率.這個(gè)方法需要T×2D個(gè)步驟完成.盡量將work_done放在密集的子空間中，由于使用的是同時(shí)聚合，因而當(dāng)數(shù)據(jù)密集的時(shí)候效果很好.

使用一個(gè)貪心方法來對(duì)主要值進(jìn)行選擇.首先，所有的非*值是次要值，反復(fù)從每一個(gè)維度中頻率較大的值中選擇來作為最有可能的次要值，讓其作為一個(gè)主要值直到到達(dá)剛開始時(shí)定義表的大小.

在每一個(gè)維度中出現(xiàn)頻率最高的值，定義一個(gè)權(quán)值，用工作增長(zhǎng)的比例除以空間增長(zhǎng)比例進(jìn)行計(jì)算求得.這個(gè)權(quán)值最高的值很有可能作為一個(gè)主要值.由于使用的是一個(gè)共享數(shù)組結(jié)構(gòu)，很容易找到每一個(gè)維度的最高頻率值，如果有多個(gè)的，選擇最先出現(xiàn)的那個(gè)作為主要值.

2.3 對(duì)密集空間進(jìn)行同時(shí)聚合

所有的聚合值放在一個(gè)大小為維度D的數(shù)組A［b1］［b2］…［bi］(i=1，2，3，…，D)中，bi的范圍從0到MC［i］之間，子空間0對(duì)應(yīng)一個(gè)*值.同時(shí)聚合分為兩個(gè)步驟:尋找每一個(gè)元組的基本單元，進(jìn)行聚合操作.每一個(gè)元組有一個(gè)相對(duì)應(yīng)的基本單元，很難知道哪個(gè)基本單元與一個(gè)元組相對(duì)應(yīng)，雖然在主要值－編號(hào)表中沒有值，但是我們可以計(jì)算所有元組的基本單元，在共享數(shù)組的幫助下更加有效，我們用一個(gè)數(shù)組B［元組］［維度］來存儲(chǔ)相對(duì)應(yīng)的子空間.僅僅需要遍歷一次共享數(shù)組就可得到子空間數(shù)組，進(jìn)而知道每一個(gè)元組相對(duì)應(yīng)的基本單元.

這個(gè)問題的關(guān)鍵是如何處理不是主要值的值，如果對(duì)一個(gè)不是主要值的值賦給它一個(gè)新的主要值編號(hào)，這個(gè)聚合表的大小將會(huì)是2D，即使沒有主要值，這使得當(dāng)維度大于30的時(shí)候，使用MM－Cubing是不可能的，然而，如果讓非主要值與*共享空間，主存空間將會(huì)大大節(jié)省，這個(gè)方法需要一個(gè)與A大小相同的輔助數(shù)組C，在數(shù)組C中，所有的元組都有相對(duì)應(yīng)的基本單元，在數(shù)組C中子空間0表示所有的非主要值，而在A中表示為*值，所以有

為了節(jié)省內(nèi)存，最好使用一個(gè)數(shù)組為A和C，通過合理安排聚合的順序，為了效率，最好將A轉(zhuǎn)換為一個(gè)D維數(shù)組來實(shí)現(xiàn)，因?yàn)槊恳粋€(gè)元組將會(huì)只用到一個(gè)子空間，數(shù)組B也是一個(gè)D維的，反過來也節(jié)省了許多的內(nèi)存.

2.4 對(duì)稀疏子空間進(jìn)行遞歸調(diào)用

對(duì)稀疏子空間(I，{M，I，*}，{M，I，*})通過遞歸調(diào)用進(jìn)行計(jì)算，可以得到:

為了使每一個(gè)子空間的右邊相等，在第一個(gè)維度中是一個(gè)值，可以通過第一個(gè)維度的值分割所有的元組，對(duì)于第一個(gè)維度中的最小值運(yùn)用遞歸調(diào)用MM－Cubing算法.

在計(jì)數(shù)和排序步驟，已經(jīng)得到在一個(gè)指定維中所有元組的相同值.僅僅需要傳遞一個(gè)元組的編號(hào)，而不是元組本身，對(duì)于遞歸調(diào)用，在這種方式下，可以節(jié)省內(nèi)存和提升程序執(zhí)行速度.所有子空間的計(jì)算與第一個(gè)基本相同，但是有一點(diǎn)不同，例如，對(duì)于子空間({M，*}，I，{M，I，*})，在第一個(gè)維度中的主要值是主要值或者是*，由于(I，I，{M，I，*})在第一個(gè)子空間已經(jīng)計(jì)算了，解決這個(gè)問題的方法是將第一個(gè)維度中的次要值設(shè)置成一個(gè)特殊的非聚合值，然后計(jì)算這個(gè)子空間，這個(gè)次要值重新存儲(chǔ)，通過共享數(shù)組結(jié)構(gòu)可以很方便的進(jìn)行設(shè)置和恢復(fù)操作從非聚合值中.

3 試驗(yàn)結(jié)果及分析

測(cè)試環(huán)境:CPU為Intel Core 2.27GHz，512MB內(nèi)存;使用的是C++語言;基本關(guān)系和所有輸出的濃縮數(shù)據(jù)立方存儲(chǔ)在 SQL Server2008數(shù)據(jù)庫(kù)中.當(dāng)維度和每一個(gè)維度的基數(shù)一定的時(shí)候，分別用MinCube、ButtomUpBST、SQCube和MM-Cubing算法對(duì)天氣數(shù)據(jù)集進(jìn)行計(jì)算.各種算法生成濃縮立方體速度如圖3所示，D(dimension)表示維數(shù)，C(cordandial)表示基數(shù).

從圖3可以看出MM－Cubing算法生成濃縮數(shù)據(jù)立方體的速度是最快的.因?yàn)镸M－Cubing將格子空間分解為一個(gè)密集的子空間，沒有進(jìn)行遞歸調(diào)用，所以 MM－Cubing算法能夠達(dá)到很高的速度.

圖3 維數(shù)為8，基數(shù)為100時(shí)，各種算法生成濃縮立方體速度的比較Fig.3 D=8 C=100 all kind of algorithms generate condensed cubes speed

4 結(jié)語

與傳統(tǒng)基于格子的算法不一樣，MM－Cubing算法通過分解格子空間，維度的重新排序會(huì)加快計(jì)算，通過生成子空間用很小的維度，不同的主要值選擇會(huì)影響效率，貪心策略執(zhí)行得很好，但是可以通過另外的主要值選擇策略來提升性能.雖然MM－Cubing在數(shù)據(jù)集中執(zhí)行的很好，但內(nèi)存的消耗是基本表的好幾倍.因此，如何提升算法的性能、減少內(nèi)存的消耗以及如何更好優(yōu)化生成數(shù)據(jù)立方的存儲(chǔ)組織方式等問題是未來研究的主要方向.

［1］Beyer K，Ramakrishnan R.Bottom－up computation of sparse and iceberg cubes［C］//Delis A，F(xiàn)aloutsos C，Ghandeharizadeh S.SIGMOD’99.Procceedings of the 1999 ACM SIGMOD international conference on management of data，June 1－3，1999，Philadelphia，Pennsylvania.New York:ACM Press，1999，28(2): 359－370.

［2］Han J，Pei J，Dong G，et al.Efficient computation of iceberg cubes with complex measures［C］//Sellis T，Mehrotra S.SIGMOD’01.Procceedings of the 2001 ACM SIGMOD international conference on management of data，May 21－24，2001，Santa Barbara，California.New York:Association for Computing Machinery，2001，30(2):1－12.

［3］Barbara D，Sullivan M.Quasi－cubes:Exploiting approximation in multidimensional database［C］//Peckman J M.SIGMOD’97.Proceedings of 1997 ACM SIGMOD international conference on management of data，May 13－15，1997，Tucson，Arizona，USA.New York:Association for Computing Machinery，1997，26 (2):12－17.

［4］Sismanis Y，Deligiannakis A，Roussopoulos N，et al.Dwarf:Shrinking the PetaCube［C］//Franklin M，Moon B，Ailamaki A.SIGMOD’02.Proceedings of the ACM SIGMOD international conference on management of data，June 3－6，2002.New York:Association forComputing Machinery，2002，31(2): 464－475.

［5］Lakeshmanan L V S，Pei J，Han J.Quotient Cubes: How to Summarize the Semantics of a Data Cube［C］// Bressan S，Chaudhri A，Lee M L，et al.VLDB’02.Proceedings of the 28th international conference on Very Large Databases，August 20－23，2002，Hong Kong.San Fransisco:Morgan Kaufmann Publishers，2002:476－487.

［6］Shukla A，Deshpande P M，Naughton J F.Materialized view selection for multidimensional datasets［C］// VLDB’98.Proceedings of the 24th international conference on Very Large Databases，August 24－27，1998， New York.San Fransisco:Morgan Kaufmann Publishers，1998:488－499.

［7］Lakshmanan L V S，Pei J，zhao Y.QcTrees:An efficient summary structure for semantic 0LAP［C］//Halevy A Y，Ives Z G，Doan A H.SIGMOD’03.Proceedings of the ACM SIGMOD international conference on management of data，June 9－12，2003，San Diego，California.New York:Association for Computing Machinery，2003:64－75.

［8］Wang W，F(xiàn)eng J L，Lu H J，et al.Condensed cube:an effective approach to reducing data cube size［C］// Agrawal R，Dittrich K，Ngu A H H.ICDE’02.18th international conference on data engineering，F(xiàn)ebruary 26－March 1，2002，San Jose，California.Los Alamitos，California:IEEE Computer Society Press，2002: 155－165.

［9］王琢，鮑玉斌.一種快速生成最小濃縮數(shù)據(jù)立方的算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2005，26(12): 2212－2215.

Fast algorithm for computing condensed cube

TU Jian-xin，YOU Jin-guo
(School of Information Engineering and Automation，Kunming University of Science and Technology，Kunming 650500，China)

To generate condensed cube faster，a new approach named MM-Cubing was proposed that computes condensed cubes by factorizing the lattice space according to the frequency of values:The count and sort algorithms and related data structures were used to compute the frequency of the values，and a data structure was provided to facilitate the major value selection and compute its subspaces;the major values were selected; aggregation was operated in dense subspace and the sparse subspace was called recursivly.The result shows that MM-Cubing algorithm is significantly outperform the MinCube algorithm and SQCube algorithm.

condensed cube;lattice;space;algorithm

TP311.13

A

10.3969/j.issn.1674-2869.2012.03.011

1674-2869(2012)03-0051-05

2011-12-27

涂建新(1987－)，男，湖北黃岡人，碩士研究生.研究方向:數(shù)據(jù)倉(cāng)庫(kù)與并行計(jì)算.

指導(dǎo)老師:游進(jìn)國(guó)(1977－)，男，湖南長(zhǎng)沙人，博士，碩士生導(dǎo)師.研究方向:數(shù)據(jù)倉(cāng)庫(kù)與并行計(jì)算.

本文編輯:苗 變