快速計算濃縮立方體的方法

涂建新，游進國

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

快速計算濃縮立方體的方法

涂建新，游進國

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

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

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

0 引言

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

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

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

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

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

1 分解格子空間

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

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

由于一個主要值出現(xiàn)的頻率很高，所以與*共享計算是比較好的;而對于一個次要值，需要進一步的計算.因此，將格子空間分為以下4個子空間:({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

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

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

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

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

第一個子空間為密集子空間，其余三個子空間為稀疏子空間，在稀疏子空間中可以通過遞歸調用探測其他的密集子空間.

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

2 MM-Cubing算法

MM－Cubing算法:首先按照圖1中(3)的方法分解格子空間，然后計算聚合密集子空間和遞歸調用稀疏子空間.

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

MM－Cubing計算濃縮立方體算法輸入的是一個關系表R，輸出的是濃縮立方體.

2.1 計數(shù)和排序

選擇一種數(shù)據結構來計算每一個值的頻率，從而選擇主要值并計算子空間.

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

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

表2 輸出結果Table 2 Result of output

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

圖2 共享數(shù)組結構Fig.2 Shared array structure

2.2 選擇主要值

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

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

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

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

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

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

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

2.3 對密集空間進行同時聚合

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

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

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

2.4 對稀疏子空間進行遞歸調用

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

為了使每一個子空間的右邊相等，在第一個維度中是一個值，可以通過第一個維度的值分割所有的元組，對于第一個維度中的最小值運用遞歸調用MM－Cubing算法.

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

3 試驗結果及分析

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

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

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

4 結語

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

［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］.小型微型計算機系統(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ù)據倉庫與并行計算.

指導老師:游進國(1977－)，男，湖南長沙人，博士，碩士生導師.研究方向:數(shù)據倉庫與并行計算.

本文編輯:苗 變