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

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

268´ANDWUBARBARA

STAT-MODL:determinewhetherthenewvalueiswithintheerrorlevelwhencom-pared(asbefore)withthevaluegeneratedbythemodel.(Asbefore,computethenewvaluebyretrievingtheoldvaluefromtertiarystorage.)Ifso,justdiscardthisvalue,otherwise,keepthisvalueintheoutlierset.

3.Thenewcellwhichisbeyondthescopeoftheoriginaldataspaceofthecube(e.g.,astimegoesbynewtransactionsareaddedtothewarehouse).Inthiscase,weshouldkeepthesenewcellsinNEW-CELLset,theNEW-CELLsetformsanewdataspacewhichisneighborhoodwiththeolddataspace.AftertheNEW-CELLsetisbiggerthansomethreshold,wecandividetheNEW-CELLspaceintochunksandmodelthem.(Storethenewvalueontertiarystorage.)

Incase1andcase2,asmorenewdataarrivestothewarehouse,thenumberofoutliersmayexceedthethreshold .Inthiscase,weshouldre-modelthechunks.

3.Experimentalresults

Inthissectionweshowtheresultsofexperimentingwithtwodatasets.TheexperimentswereconductedinaSUNUltra2,withtwoprocessors,and500MbytesofRAM.

3.1.Censusdataset

The rstdatasetusedistakenfromtheU.SCensusBureaudata(http://www.census.gov/main/www/access.html).Thedatasetcontainspopulationbrokenbycountry,year,agegroupandsex.WeuseC,Y,AandSrespectively,todenotethesedimensions.Thesedimensionshavedomainsofsize227,23,17,and2respectively.Thereisatotalof169,694cellsand7,820missingcellsinthespaceofthecorecuboid.

Figure3showsthedatacompressionachievedunderdifferenterrorlevels(β).Thetableshowsthenumberofcellsinthecorecuboid,cellsthatareretainedasbelongingtosparsechunks(SingleCells),numberofparametersusedbythemodels(Parameters),andnumberofoutliers(Outliers).Thecompressionratioindicatestheratiobetweenthespaceneededtostoretheparameters,singlecells,outliersanddatastructuresusedtodescribethechunks,andthespaceneededtostorethecellsintheoriginalcube.Noticethatwestartachievinghighcompressionrates(33%andunder)onlywhentheindividualcellserrorrateislefttobehigherthan15%.Foranindividualcellerrorof40%weachieveavalueof14%compressionrate.Although,at rstglancethismaynotseemveryimpressive,onehastorememberthatveryrarelyinOLAPtheanalystscareaboutsinglecellvalues.Rather,whatisusuallyneededishigherlevelaggregations,suchasrangequeriesorothercuboidsinthelattice.Toshowourperformanceinthoseaggregations, gure4showstheaverageerrorintheanswersobtainedbyrangequeriesasafunctionoftheselectivityofthequery(shownasafractionofthenumberofcellsinthecorecuboid).Therangequerieswererunovertheapproximatecorecuboid,compressedwithaβ=0.4.Theserangequeriescomputetheaggregationofallthecellsintheirranges.Asitcanbeseenfromtheresults,noneof