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

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

258´ANDWUBARBARA

forthecompressionschemesproposedinVitterandWang(1999),Poosalaetal.(1996)andShanmugasundarametal.(1999),sincetheyaimtocompressapartofthedatacube,i.e.,thecorecuboid.1Theiranswerswill,indeedhavetighterboundsastheaggregationsgrowcoarser,buttheirmethodscanonlytellusthattheerrorsarelessthantheonescommittedinthequeriesoverthecorecuboid,withoutbeingabletoestablishanytighterbound.Thisisduetothefactthatnoneoftheothertechniquestakestheapproachofretainingoutlierstocontroltheerrorbounds.

Thereareotherdisadvantagestopublishedmethods.InthewaveletdecompositionmethodadvocatedbyVitterandWang(1999)itisnotclearhowresilientthemethodistomissingcells,acommonoccurrenceindatacubes.Inthehistogram-basedmethodofAcharyaetal.(1999)andPoosalaetal.(1996),asetofpre-computedsamplesofasmallsetofdistinguishedjoins,orjoinsynopses,isusedtoestimatetheanswerstothequeries.Acriticismtothistechniqueisthatthesesamplesmustbefrequentlyrecomputedtoavoidthebiasintroducedbyansweringallqueriesusingthesamesetofrestricteddata.Again,inthewaythatbothmethods,wavelet-decompositionandjoinsynopses,areimple-mented,theaccuracyofthemethoddependsonthedatadistributionbutnotonthemethoditself.

Anotherimportantmatteristhatofmaintainingthecompressedversionofthecubeasnewdataarrivestothewarehouse.AsweexplaininSection2.4,itisveryeasytoaccomplishthisinourtechnique.Ontheotherhand,usingwaveletsasinVitterandWang(1999),bringsaboutanenormouscomplexityindynamicallykeepingthecoef cientsup-to-date(theauthorsdonotdiscussthisissueinthepaper,leavingitforfuturework).Thesameistruewhenusingkernels(Shanmugasundarametal.,1999).Onedrawbackofkernelmethodisitcanonlyanswerrangequery.Itcannotgivetheanswerforpointquery(withonesinglecell)forwecannotintegratethekernelestimatefunctiontoonepoint.Asnewtuplearrives,thekernelfunctioncannotdecidewhetherthisnewcelliswellornot.

Finally,datacubecompressioncanserveanotherusefulpurpose:on-lineaggregation(Hellersteinetal.,1997).Thisistheprocessbywhichonecanstreamlinethecomputationofmorere nedanswerstothequeriesastheuserislookingatthecurrentestimate.Withourmethod,thereisarelativelyeasywaytoimplementthis:usingdifferenterrorthresholds,classifythedataintoerrorbins,eachbincorrespondingtoanerrorlevel.Toproducethe rstestimate,onlythedatainthehighest-errorbinneedstobebroughtfromdisk;tore netheanswer,successivebinsarebroughttomemory.Itisnotclearhowtodothiswiththejoinsypnosesorthedensityestimationmethods.And,althoughwaveletdecompositionlendsitselftomultiresolutionandthusestimatere ning,therearetwomajorroadblocks.First,itisnoteasytodecidewhichcoef cientstoputineacherrorbin:ifoneusesthedecompositionlevelsofthewavelet,thepartitionistoouneven,sinceeachlevelhastwicethenumberofcoef cientsofthepreviousone.Secondly,thetotalnumberofcoef cientsisusuallylargerthanthenon-zerodatacellsofthecube(simplybecauseithastobeapowerof2).(Althoughwedonotdescribeon-lineaggregationsupportinthispaper,wearecurrentlybuildingatestbedtoexperimentonit.)

Thispaperisorganizedasfollows.InSection2,wepresentourtechniqueindetail,includingalgorithmstodividethecubeinregions(chunks)andtomodelthedatainthem.Section3presentstheexperimentalresultsovertwodatasets:arealdatasetandasynthetic