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

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

LOGLINEAR-BASEDQUASICUBES261 STAT-REDV:achunkwithintermediatedensity(enoughcellsnottobesparse,butnotenoughtobemodeledyet),orachunkwhereamodel tisnotsatisfactory.Thisarechunkssubjectedtofurtherpartitioningtothenextlevel.

STAT-MODL:thischunkhasbeenmodeled. STAT-DVOK:thischunkhasbeenfurthersubdivided.

Afterthepartitioningprocedure,everychunkshouldbeinSTAT-NULL,STAT-SPARSEorSTAT-MODL.Therestareintermediatestates.

AteverystepofthepartitioningprocesswemaintainaCHUNK-DESClistinmemorywhichcontainsinformationabouteverychunk’slevel,state,andcountofcells.Moreover,therearethreeparametersusedtodrivethepartitioningprocess:

α:thismarkstheminimumacceptabledensityforchunksmeasuredbythenumberofcellsinthechunkdividedbythechunk’ssize.

β:thisisthemaximumerrorleveltoleratedintheestimationprocess.Thatisifyisthevalueofacellandy thevalueoftheestimationbythemodeldescribingthechunk,therelativeerrorgivenby|y y |/ymustbelessthanorequaltoβ.Anycellwhoseestimationerrorsurpassesβisdeclaredanoutlier.

:thisisthemaximumpercentageofoutliercellsallowedinthechunk,whichismeasuredasthenumberofoutliersdividedbythenumberofcellsinthechunk.Ifthepercentageofoutliercellsisbiggerthan ,wedeclarethechunk’sstateasSTAT-REDVandproceedtopartitionitfurther.

Theusercansettheparametersα,β, basedonbothhisorherpre-knowledgeandrequirementbeforethesystempartitionsthecube.Forexample,thevalueβdependsontheuser’sexpectationofqueryaccuracyandthevaluee dependsontherequirementofcompressionratioandsystemstorage.Forα,givenaspeci cdataset,theusercancomputetheaveragedensityτofthewholecubebydividingthetotalnumberofnon-zerocellsbythesizeofthecubespace.Sotheαcanbesetasα=cτwherecisachosenconstant.Anotherautomaticapproachtosetαneedsapreprocessofthedataset.Aswe talkedjbefore,atachosenj-thlevel,wherej∈{1,...,MAXLEVEL},thereareCno= i µi jthlevelchunksandtheaccordingsizeofeachjthlevelchunkispredeterminedtobejj{µ1,...,µd}.Afteronescanscanofthedataset,wecancomputethedensityτiforeachjchunk,wherei=1,...,Cno.Thenwecandosomestatisticaltesttodecidethevalueα.Forexample,ifthechunkdensityτisatis estheunifromdistribution,wecansetα=cτ¯;σifnormaldistribution,α=τ¯ zα,wherezαisthelevelαofthevalueofthestandardCnonormaldistribution.

Aftertheαisset,duringthepartitionprocess,thechunkwillbeclasi edas:STAT-NULLifthereisnotupleinthischunk;STAT-SPARSEifthenumberoftuplesinthischunkislessthanMINITUPLE;STAT-DENSEifthedensityofthischunkisbiggerthanα;STAT-REDVifthedensityofthischunkislessthanαbutthenumberoftuplesinthischunkisbiggerthanMINITUPLE.

Figure2presentsthepseudo-codeforthepartitioningalgorithm.Ascanbenoticed,thealgorithmproceedstodividetheinitialcuboidin1stlevelchunks,assigningcellstoeach