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

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

274´ANDWUBARBARA

(raw)forthesyntheticdatasetof200,000cells.ThegraphshowsthequerytimeinsecondsintheYaxisversustheselectivityofthequery,asapercentageofthecells,intheXaxis.(Eachpointistheresultofaveraging100rangequeriesofthesameselectivity.)Thegraphshowsthatqueriesoverthecompressedcubeoutperformthoseoverthestandardcubeforalltherangeofselectivities.Itisimportanttonoticethatthetimesreportedinthegraphmaybeimprovedbytheuseofindexes(e.g.,commercialproductsmayhaveabetterresponsetimethantheonesreportedinthegraphforretrievingrawdata),however,indexeswouldhelpboth,theapproximatequeryansweringandtherawdataqueryansweringinthesameproportion,sotheperformancegainsoftheapproximateansweringtechniquewouldhold.Figure8showstheaverageerrorintheanswersobtainedbyrangequeriesasafunctionoftheselectivityofthequery(shownasafractionofthenumberofcellsinthecorecuboid).Therangequerieswererunovertheapproximatecorecuboid,compressedwithaβ=0.2.Asitcanbeseenfromtheresults,noneoftheanswersexhibitsanerrorthatgoesbeyond1%,inspiteofthe20%errorthattheindividualcellsinthecuboidmayreach.

4.Conclusions

Inthispaper,wehavepresentedaneffectivetechniquetocompressdatacubes,tradingspaceforaccuracyofthequeryanswers.Wehaveshownthatinrealdatasetswecanachieveagoodcompressionratiowhilestillobtainingsmallerrorsinthequeryanswers.Itisimportanttoremarkthattheerrorintherangequeryanswerisusuallymuchsmallerthantheerrorlevelthresholdwhenwesetforeachcellinthemodelingphase.

Usingsomeextraspace,onecanretaintheaggregatevaluesforcellsinthelessdetailedcuboidsonthelattice(coarseraggregations),guaranteeingmaximumlevelsoferrorforqueriesonthesecuboids(thisarehardguarantees,e.g.,theerrorinthequerywillbelessthanorequalthan10%).(Thiswasshown,asanexample,intheresultspresentedin gure5.)Doingthis,onecaneffectivelycompetewithtechniquesthatchoosewhichcuboidsinthelatticearethemosteffectivetomaterialize,basedonspacerestrictions(suchastheonesdescribedinHarinarayanetal.(1996)).ThosetechniqueswouldstillhavetoincurinCPUandI/Otimeintryingtoanswerqueriesfromothercuboidsthatarenotmaterialized,whileourtechniquewouldprovidemuchfasterresponsetimeattheexpenseofsomeerrorsintheanswers(whoselevelsareguaranteed).

Therearesomeaspectsofthisworkthatmeritfurtherresearch.Amongthem,wearetryingtoevaluateotherheuristicsformodelselection,andotherwaysofpre-clusteringthecellsinthecorecuboidbeforeweproceedtodivideitintochunks.Wearecurrentlyexperi-mentingwithheuristicstoreshu ethe“rows”ofeachdimensionsinordertoobtaindenserregionswhosemodelsprovidebetter tting(therebydecreasingthenumberofoutlierstoberetained).Theseheuristics,whicharebasedonsampling,bringtheaddedbene tofnothavingtopre-computethecorecuboidbeforewechunkit.Inotherwords,thecomputationofthechunkscellsandthechunkmodelingcanbedoneinthesamestep.Itisworthtopointoutthatsincetheheuristicsdependonsampling,thereshu ingprocessislinearonthenumberofdatacubedimensions(d),andthusverypractical.

Anotherideathatweareexperimentingwithistokeeptwosetsofmodelsinthechunksdescriptions:themultiplicativeloglinearmodelwedescribedinthispaperandanadditive