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

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-BASEDQUASICUBES263parentchunkisdividedintochildchunks,weneedcopythetuplesintheparentchunktotheaccordingchildchunk.Afterthat,weonlykeepthetuplesinthosechildchunksandthespacefortheparentchunkcanbereleased.Duringthisstep,itneedsonereadandonewrite.InpracticetheI/Oactivitywillbemuchless,sincetherewillbechildchunksthat tinmemory.)Moreover,weneedtopointoutthatallthisI/Oactivitytakesplacebeforethequeryprocessingisundertaken.(Chunksandtheirmodelscanbestoredaspartofthecuboidandreusedforapproximatequeryprocessinganddatamining(BarbaraandWu,1999).)

Noticethatmanychoicesofmodelsarepossible(asurveyofmethodscanbefoundinBarbara´etal.(1997)),sincethegeneraltechniqueisquiteindependentofthemodelchosenforthechunks.Ofcourse,therewillbesomemodelsthatarebettersuitedforspeci cclassesofdataandthereforewillproducesmallerestimationerrors.(WehavestudiedsimplelinearregressionmodelsandtheireffectintheerrorsinBarbara´andSullivan(1997a).)Inthispaperwechoosetostudyloglinearmodels(Agresti,1996;Andersen,1997,1994);thewaytheirparametersarecomputedwillbeexplainedinthenextsubsection.

SpecialmentioningshouldbemadeofthetreatmentofholesforchunkswhosestateisSTAT-MODL.(HolesinchunkswhosestateisSTAT-SPARSEaretakencareofbyde nition:onlyalistofnon-zerocellsiskeptonthose.)SinceitisassumedthatthenumberofholesofaSTAT-MODLtypeofchunkissmall(sinceαmustbebig),wecansimplytreatthemasoutliersandkeepthemintheoutlierslist.Otherwise,weneedaseparateindextoindicatewhichcellsarenon-zero.Thishasrepercussionsinourmethod:thesmallerthechunkdescriptionsare,themoreofthemwewillbeabletokeepinmemory,therebyavoidingtheneedforfetchingthemfromthedisk.

2.2.Modelingthedatachunks

Wehavechosenloglinearmodels(Agresti,1996;Andersen,1997,1994)forthetaskofmodelingthechunksofdata.Loglinearmodelingisamethodologyforapproximatingdis-cretemultidimensionalprobabilitydistributions.Themulti-waytableofjointprobabilitiesisapproximatedbyaproductoflower-ordertables.Loglinearmodelsareknowntoprovideagood tformultinomialdistributions(Andersen,1997,1994).Hereweshouldnotelog-linearmodelsuseonlycategoricalattributesandcontinuousattributesmustbediscretized rst.

Foravalueyi1i2···ininacubeatpositioniroftherthdimensiondr(1≤r≤n),wede nethelogofanticipatedvaluey i1i2···inasalinearadditivefunctionofcontributionsfromvarioushigherlevelgroup-bysas:

l i1i2···in=logy i1i2···in=

G {d1,d2,...,dn}γ(Gir|dr∈G)(1)

Wewillrefertotheγtermsasthecoef cientsofthemodelequation.Forinstance,ina4-dimensionaltablewithdimensionA,B,C,D,weuse(i,j,k,l,yijkl)todenotethecellina4-Dcubespace,wherei=0,...,I 1,j=0,...,J 1,k=0,...,K 1,l=0,...,L 1,Eq.(2)givesthesaturatedloglinearmodelwhichmeansitcontainsallthepossiblek-factor