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

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

256´AND

tticeforthedatacubewithdimensionsday,store,product.

20,000products,materializingjustthecorecuboidrequiresstoragefor73billionaggregatevalues.(Thecorecuboidisthe nestlevelofaggregationinthedatacube,withcellsde nedforeachcombinationofallthedimensionsinthedata:inourexample,eachday,storeandproduct.)Whileinpractice,onlyafractionofthecellswillbepopulated,thecorecuboidcanstillbelarge(e.g.,even2%of73billionamountsto1.46billioncells).Moreover,adatacubeisde nedasalatticeofaggregationlevels(seeGrayetal.(1996)andHarinarayanetal.(1996)),withanexponentialnumber(inthenumberofdimensions)ofcuboids.Forinstance,inourexample,acuboidcanbeformedwithaggregationsofthedimensionsdaysandstores,whereeverycellcontainssalesperdayandperstore,foralltheproducts;noticethatthiscuboidcanbecomputedfromthecorecuboid.Figure1showsthelatticeforthedatacubeofourexample.InRelationalOn-LineAnalyticalProcessing(ROLAP),thecomputationofthecubecellsisdeferreduntilusersexaminethem.(Inrealproductssomeofthecuboidsarepre-computedandstoredinrelationaltables.)Whentheentriesareneeded,thesystemqueriestheunderlyingdatabasetocomputethem.Sometimes,ahybridstrategyisusedinwhichpartofthecubeismaterialized(e.g.,thebasedata)andtherestiscomputedondemand.Thesetechniqueshowever,canimposelongdelaysinansweringqueries.

Theselimitationshavepromptedresearcherstolookfortechniquestocompressthedatacubeinsuchawaythatonlyafractionofthespaceisneeded(Barbara´andSullivan,1997a,1997b;Poosalaetal.,1996;Shanmugasundarametal.,1999;VitterandWang,1999).Sincethecompressiontechniquesarelossy,onecanonlyprovideapproximateanswerstothequeriesposedtothedatacube.Ontheotherhand,thequeriescanbeansweredwithoutincurringintomuchdiskI/O,sotheresponsetimeisconsiderablysmallerthantheoneexperiencedinuncompresseddatacubes.

Inthispaperwepresentatechniquetocompressdatacubesbasedonloglinearmodels(Agresti,1996).Loglinearmodelsareaformofstatisticalparametricmodels,i.e.,modelsthatattempttoestimatethedatapointsusingafunctioncomposedbyaseriesofparameters.(WehavepreliminaryexploredasimplerparametrictechniquebasedonlinearregressioninBarbara´andSullivan(1997a,1997b).)Thetechniqueusesloglinearmodelstocharacterize