c ○ 2001 Kluwer Academic Publishers. Manufactured in The Ne(17)

Abstract. A data cube is a popular organization for summary data. A cube is simply a multidimensional structure that contains in each cell an aggregate value, i.e., the result of applying an aggregate function to an underlying relation. In practical situat

LOGLINEAR-BASEDQUASICUBES27110%,itwouldbeenoughtoretainanextra29,119values(theaggregatedcellsthatexhibiterrorsbiggerthan10%inalltheothercuboids).Noticethatthis29,119areafraction(24.6%)ofthe117,973cellscontainedinallthecuboidsotherthanthecoreone.Infact,thecompressionratefortheoverallcubewouldbe18.3%,stillaverygoodratio.Bydoingthis,wecanguaranteea xedleveloferror(10%)forqueriesintheothercuboidsofthelattice.Queriesoverthecorecuboidwouldgetaguaranteederrorof40%,butactualerrorswouldlikelybemuchlessthanthatformostqueries.Ifonewouldinsistinmakingthe10%guaranteeacrossallcuboids,includingthecore,wewouldneedtostore20,035parameters,and64,348outliers(asshownin gure3),alongwiththe29,119cellsfortheothercuboids.Thiswouldbringtheoverallcompressionratioto40%.Bycontrast,usingthealgorithmdescribedinHarinarayanetal.(1996)todecidewhichcuboidswouldbethemostef cientchoicestomaterialize,assumingwewanttomaterializeupto3cuboids,onewouldneedtostore178,194cells(thoseofthecorecuboid,andthecuboidsYASandCAS),or62%ofthedatacube.Yet,doingthis,queriesoveranyothercuboidwouldrequiretheaggregationofcellsinoneoftheYACS(core),YASorCAScuboids(whichwouldinvolvealsoadditionalI/OandCPUtime).

Finally,weillustratehowthechunkmodelsareusefulinthemselves.Letusexaminethechunkwhichinvolves7countries(Pakistan,Russia,GreatBritain,Indonesia,U.S.,IndiaandChina),alltheyears,alltheagegroups,andbothsexes.Themodelwegetisthefollowing:

CYCAYAASlijkl=logy ijkl=γ+γiC+γjY+γkA+γlS+γij+γik+γjk+γkl(5)

Thismodelincludesalltheone-factoreffects(γiC,γjY,γkA,γlS),4two-factoreffectsCYCAASCSYA(γij,γik,γjk,γkl)andnohigher-factoreffects.Itmeansthetwo-factoreffects(γil,YSγjl)andhigher-factoreffectshavetrivialin uenceonthepopulation.Inotherwords,forthischunk,thevalueintheSex(S)atrributeisindependentwiththevalueintheCountry

(C)andYear(Y)attribute.Fromthestandardvariancesofthefactors,wediscoverthatthemostimportantattributeeffectisC(country),thesecondisA(agegroup).Foragivenattribute,forinstancecountry,weknowthatthebiggestparametervalue(γC)is1.384,correspondingtoChina.(Withoutlookingatthedata,weknowthatChinaisthecountrywithhighestpopulationinthischunk.)WecanalsodiscovertherankingofpopulationbylookingattherankingofparametersγC.Also,takinganeffectsuchasγCY,weknowthatforagivencountry,thesumoftheseeffectsisequaltozero(Eq.(3)).ThatimpliesthatwewillhaveabiggestpositiveandabiggestnegativeeffectγCYforeachcountry.Thesedefectstelluswhichyearshavethebiggestin uence(positiveornegative)inpopulationforthatcountry.Insum,thereisawealthofinformationcapturedbythechunkmodel.

3.2.Syntheticdataset

Weexperimentedwithasyntheticdataset,mostlytodeterminethescalabilityofourapproach.Inthisset,thecorecuboidis4-dimensional,withthefourdimensionsdenotedbythelettersA,B,CandD,withdomains80,40,20,10respectively.Wegeneratedthreedatasetsthatcontain50,200,and500thousandnon-emptycellsinthecorecuboid.The