c ○ 2001 Kluwer Academic Publishers. Manufactured in The Ne

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

JournalofIntelligentInformationSystems,16,255–276,2001

c2001KluwerAcademicPublishers.ManufacturedinTheNetherlands.

Loglinear-BasedQuasiCubes

´DANIELBARBARA

XINTAOWU

ISEDepartment,GeorgeMasonUniversity,MSN4A4,Fairfax,VA22030,USA

ReceivedApril30,2000;AcceptedMay10,2001

Abstract.Adatacubeisapopularorganizationforsummarydata.Acubeissimplyamultidimensionalstructurethatcontainsineachcellanaggregatevalue,i.e.,theresultofapplyinganaggregatefunctiontoanunderlyingrelation.Inpracticalsituations,cubescanrequirealargeamountofstorage,so,compressingthemisofpracticalimportance.Inthispaper,weproposeanapproximationtechniquethatreducesthestoragecostofthecubeatthepriceofgettingapproximateanswersforthequeriesposedagainstthecube.Theideaistocharacterizeregionsofthecubebyusingstatisticalmodelswhosedescriptiontakelessspacethanthedataitself.Then,themodelparameterscanbeusedtoestimatethecubecellswithacertainlevelofaccuracy.Toincreasetheaccuracy,andtoguaranteetheleveloferrorinthequeryanswers,someofthe“outliers”(i.e.,cellsthatincurinthelargesterrorswhenestimated),areretained.Thestoragetakenbythemodelparametersandtheretainedcells,ofcourse,shouldtakeafractionofthespaceofthefullcubeandtheestimationprocedureshouldbefasterthancomputingthedatafromtheunderlyingrelations.Weuseloglinearmodelstomodelthecuberegions.Experimentsshowthattheerrorsintroducedintypicalqueriesaresmallevenwhenthedescriptionissubstantiallysmallerthanthefullcube.Sincecubesareusedtosupportdataanalysisandanalystsarerarelyinterestedintheprecisevaluesoftheaggregates(butratherintrends),providingapproximateanswersis,inmostcases,asatisfactorycompromise.Althoughothertechniqueshavebeenusedforthepurposeofcompressingdatacubes,ourshastheadvantageofusingparametric(loglinear)modelsandtheretainingofoutliers,whichenablesthesystemtogiveerrorguaranteesthataredataindependent,foreveryqueryposedonthedatacube.Themodelsalsoofferinformationabouttheunderlyingstructureofthedatamodeledbythem.Moreover,thesemodelsarerelativelyeasytoupdatedynamicallyasdataisaddedtothewarehouse.

Keywords:datacubes,compression,statisticalmodels,loglinear,queryapproximation

1.Introduction

Adatacubeisapopularorganizationforsummarydata(Grayetal.,1996).Acubeissimplyamultidimensionalstructurethatcontainsateachpointanaggregatevalue,i.e.,theresultofapplyinganaggregatefunctiontoanunderlyingrelation.Forinstance,acubecansummarizesalesdataforacorporation,withdimensions“timeofsale,”“locationofsale”and“producttype”.

Alotofworkonbuildingdatacubesef cientlyhasbeendoneintherecentpast(RossandSrivastava,1997;Agarwaletal.,1996;Zhaoetal.,1997).However,precomputationoftheentirecubecantakealotofspace.Considerforexamplearetailsalesdatasetwithdimensionsday,storeandproduct.Ifweassume1,000stores,10years(3,650days)and ThisworkhasbeensupportedbyNSFGrantIIS-9732113.