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

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

264´ANDWUBARBARA

effects,allthepossiblek 1-factoreffects,andsoonuptothe1-factoreffectsandthe

ABmean(γ.Forexample,γiAisone-factoreffect,γijistwo-factoreffectwhichshowstheABCdependencywithinthedistributionsoftheassociatedattributesA,B,γijkisthree-factor

effectwhichshowsthedependencywithinthedistributionsoftheassociatedattributes

ABCA,B,C.Notethesizeofpossiblehigh-factoreffectscanbeverylarge(forγijk,thesize

isI×J×K).

ABACADBClogy ijkl=γ+γiA+γjB+γkC+γlD+γij+γik+γil+γjk

BDCDABCABDACDBCDABCD+γjl+γkl+γijk+γijl+γikl+γjkl+γijkl(2)

Therearealsosomelinearconstraintstoovercometheoverparameterization,asshowninEq.(3).

γ.A=γ.B=γ.C=γ.D=0

ABACACCDγiAB=0.=γ.j=γi.=γ.k=···=γ.l

...

ABCDABCDγijk=γij=γiABCD=γ.ABCD=0.kljkl..l(3)whereadot“.”meansthattheparameterhasbeensummedovertheindex(Forexample, 1ABABγi.=J

j=0γij).Inshort,theconstraintsspecifythattheloglinearparameterssumto0overallindices.

Therearetwoapproachestoestimatethemodelcoef cients.Oneistheiterativepropor-tional ttingmethod,basedonsolvingthecorrespondinglikelihoodequations.Thismethodcanalwaysgettheprecisesolutions,butitneedsmanyiterativestepsoverthedata.

Theothermethodistocomputethecoef cientsfromthevaluesdirectly.Thecoef cientscorrespondingtoanygroup-byGareobtainedbysubtractingfromaveragelvalueatgroup-byGallthecoef cientsfromhigherlevelgroup-by-s.Forinstance,Eq.(4)showstheparametersina4-dimensionaltable.

γ=l....

γiA=li... γ.

...

ABγij=lij.. γiA γjB γ.

ABCABACBCγijk=lijk. γij γik γjk γiA γjB γkC γ.

...(4)

wherel....isthegrandmeanoraverage(Notethata“·”denotesanaggregationalongthatdimension.)andli...isthemeanoverallvaluesalongithmemberofdimensionA.Froml....andli...,γiAdenoteshowmuchtheaverageofthevaluesalongithmemberofdimensionAdiffersfromtheoverallaverage.

Sarawagietal.(1998)presentfastcomputationtechniquesthatmakethisapproachfeasibleforlargesets,andalthoughthismethoddoesnotgiveprecisesolutions,itsfaster