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

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-BASEDQUASICUBES265runningtimemakesitabetterchoiceforcompressingdatachunks.Forourcase,weappliedamodi edversionoftheirUpDownmethod,involvingthefollowingsteps:

Up-phase:Inthisphase,allthelparametersshownbeforearecomputed.Fromforeachgroup-byinEq.(4),computethecorrespondinglvaluefromtheparametersinthepreviousgroup-by-s.Forexample,inordertocomputelij..,wecouldusethevaluesoflijk.,aggregatingforallk.(Ingeneral,thereismorethanonewayofcomputingtheparameters,sincethereisalatticeofgroup-byaggregations;Abene tanalysisapproachliketheoneinHarinarayanetal.(1996)canbeusedtoselectthebestchoice.)Weneedtostartfromthemostdetailedgroup-by:ingeneralthisistheonede nedbytherawdata(basecuboid).Inourcase,westartfromMAXLVLfactors.Forinstance,ifMAXLVLis2,westartfromthelij..(γAB).

Down-phase:foreachgroup-by(upperlimitbeingMAXLVL)startingfromtheleastdetailed(forinstance,l....inEq.(4)),computethecorrespondingeffect(i.e.,γ)atGbysubtractingfromthecorrespondinglvaluetheparametersfromallthegroup-by-sHwhereH G.(Forinstance,tocomputeγijAB,weneedtosubtractfromlij..thevaluesofγiA,γjBandγ.)

AspointedbySarawagietal.(1998),tocomputean-attributegroup-byparameterintheDown-phaseinvolves2n 1parameters.Sarawagietal.(1998)userewritingoftheformulastogetacomputationspeedup.Intherewritingform,computingan-attributegroup-byparameterinvolvesonlynsubtractions.However,rewritingassumesthatthereisnomissingdata,otherwisetheresultsarenotaccurate.Inourtechnique,sincewecanlimittheamountofcomputationbyusingtheparameterMAXLVL,andsinceweareperformingthecomputationforachunkinsteadofforthewholecube,weassumetheexpenseofsubtracting2n 1parametersistolerable(i.e.,wedonotuserewriting).Itisobviousthatalargenumberofmodelscanbeusedto tagivensetofdatapoints.nForann-dimensionalloglinearmodel,therearetotally22possiblemodels(determinedbywhichparametersofthesaturatedmodelaresettozero).Fingleton(1984)presentssomepossiblestrategiesofmodelselection.Asuitablecriterionforchoosingamodelistominimizethechi-squaredX2ortheassociatedlikelihood-ratiostatisticY2values.However,justminimizingthesestatisticscanleadustochoosethesaturatedmodelinviewofitsperfect t.Fordatareduction,wearemoreinterestedinconcisemodels:inotherwords,inchoosingthesimplestmodelthatisnotinconsistentwiththedataset.Suchamodeliseasiertointerpret,identi estheessentialrelationsamongvariablesandmoretoourpoint,ingbrute-forcetocompareamongmodelscaneasilygetoutofhand;therefore,wemustresorttoagoodstrategythatgetsanacceptablemodelusingasfewaspossiblemodelcomparisons.Inselectingagoodmodel,wehavetwogoals: rst,achieveagoodlevelofdatareduction(thistranslatestousingasfewparametershavingasfewsomeoutliersaspossibletoapproximatethecube)andtohaveameaningfulmodelfromwhichknowledgeaboutthisportionofthedatacubecanbeextracted(thisimpliesagood t,butalsoamodelsimpleenoughtounderstand;itisforinstance,hardtointerpretcombinationeffectsofmorethanthreeattributes).