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

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

260´ANDWUBARBARA

thecorecuboid.Thenon-emptycellsinthecuboidareasetofmultidimensionalpoints,V={v 1,v 2,...,v m}.whereeachv i={vi1,vi2,...,vid,mi},withvijthei-thdimensionvalueandmithevalueofthecell.

AswepointedoutinSection2,weneedto nd“chunks”ofthecorecuboidthataredenseenoughtobemodeledproperly:Ifaregionistoosparse,themodelswillnot twell.Moreover,ifwetrytomodelachunkthatistoosparse,the“holes”inthechunk,i.e.,thecellsthatdonothaveanyvalues,willbetoomany.Sinceweneedtolisttheseholes,itisverylikelythatthecompressiongainsachievedbythemodelwouldbeoffsetbythesizeoftheholelist.So,ourprocedureistohierarchicallyexplorelevelsofchunks(partitioningchunksintosub-chunks,andsoon),untilwe ndregionsthataredenseenoughformodeling.Noticethatdoingthisalsomakesourtechniquescalewellwithlargedatacubes:Regardlessofthesizeofthecorecuboid,weaimtoachievesmalldescriptionsofitsdenseregions,therebycompressingthedatainthoseregionsbydescribingitviaafewmodelparametersandalistofoutliersandholes.Forbigcuboids,wewillhavemoredenseregions,butsinceeachoneofthemwillbecompressed,theoverallcompressionratewillbegood.Moreover,weneverhavetodealwithhavingto tamodelfortoolargearegion(whichwouldincreasethecomputationtimeforthe ttingprocess),sincethechunksaresmallerthantheentirecuboid.

Therearemanywaystopartitionthecorecuboid.Wetakeasimpleapproachdescribedinwhatfollows.Initially,wepartitionthespaceofthecuboidintonon-overlappingrectangular

111st-levelchunkswhichhavethesamechunksize,i.e.,µ11×···×µd,whereµiisthesize

ofthechunkindimensioni.Hence,thenumberofchunksin1stlevelis

Di

1Cno=.iWeuseci1todenotethechunkinthe rstlevel.Thesizeofanyofthe1stlevel i-th

1chunksisgivenbydi=µi.Clearly,werequirethatµi1≤ Di foralli;moreover,wechoosenottodividethosedimensionswithsmalldomains(forthemwemakeµi1= Di ).Atanypointduringtheprocessofpartitioningwemaydecidetofurtherdividea1st-level

chunkintoseveral2ndlevelchunks,andsuccessivelyanj-thlevelchunkintoj+1-thjjlevelchunks.Thesizeofanj-thlevelchunkispredeterminedtobe{µ1,...,µd},forj=1,...,MAXLEVEL,whereMAXLEVEListhemaximumlevelofanychunk.

Beforeweformallypresentthealgorithmforcuboidpartitioning,letusdescribethedatastructuresthatareneededtomakeitwork.Achunkisdescribedasastructurewhichcontainsthefollowing elds(eachwiththeobviousmeaning):Chunk-number,Number-cells,Number-outliers,Level,State,Pointer-to-parent,Parameter-list,Cell-list,Outlier-list,Sum-Value,Max-Value.

Inparticular,Statede nesthestateofthechunk,whichchangesdynamicallyasthepartitioningprocessruns.Thepossiblestateswhereachunkcanbefoundareasfollowing: STAT-NULL:nocellsarelocatedinthischunk.Thisistheinitialstateofeverychunkandthe nalstateforemptychunks.

STAT-SPARSE:achunkwithveryfewcellsinit.(Wejustretainallcellsinthischunk.) STAT-DENSE:achunkwithenoughcellswhichcanbemodeled.