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

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-BASEDQUASICUBES257densechunksofthecorecuboidinthedatacube.Thesemodels,canbeusedtoestimatecells,withacertaindegreeofaccuracy.Wekeeptheerrorscausedbytheestimationprocessundercontrolbystoring,alongwiththemodelparameters,thosecellswhoseestimatedvaluesdifferfromtherealvaluesbymorethanapre-establishedthreshold.Thisideamaintainsa xedboundforqueriesoverthecorecuboid,providingguaranteesfortheapproximatedanswers.Moreover,theideacanbeeasilyextendedtoanyothercuboid(withouthavingtorecomputemodelsforanyofthesecuboids):bymaintainingasmallnumberofcellsineachlevelofaggregation,orcuboid,wecanhaveguaranteedboundsforapproximateanswersovertheentiredatacube.This,isanalternativetotechniquesthatdecidewhichpartsofthecubeshouldbematerializedtoobtainagoodtradeoffbetweenspaceandqueryperformance,suchastheheuristicspresentedinHarinarayanetal.(1996).Inourcase,withaverysmallinvestment(afewofthecuboids’cells)wecanprovideapproximateanswersforqueriesposedoverallthedatacube.Moreover,withcoarseraggregations(cuboidswithlessdimensions,suchasday,productinthelatticeof gure1),wecanguaranteetighterboundsfortheanswers,simplybecausetheerrorscommittedbytheestimationofindividualcellstendtocanceleachother.

WecallthestructurethatresultsfromstoringthemodelsandtheretainedcellsaQuasi-Cube.Itisimportanttoemphasizethat,inaQuasi-Cube,theerrorboundcanbekeptatadesiredlevel,independentlyofthedistributionofthedata.Whenansweringqueries,thesystemcanusethemodelsandtheretainedcellstogiveananswerwithaguaranteedmaximumerrorlevelattachedtoit.

Parametricmethodstocompressdatacubeshaveanadvantageoverothertechniques(suchastheonesdescribedinPoosalaetal.(1996)andVitterandWang(1999)):theparameterscomputeddescribethedataaccuratelyandcanserveasagoodbasistomineimportantconclusionsabouttheunderlyingdistributionofdata.Thestructureofthemodeldescribesthepatternsofinteraction(Agresti,1996).Moreover,onecanimmediatelyknowwhichdimension(orcombinationsofdimensions)exertthebiggestin uenceinthedatabylookingattherelativesizeofthemodelparameters(Agresti,1996).Bycomparison,itisdif culttodrawinformationfromahistogram(asusedinPoosalaetal.(1996))orawaveletdecomposition(asusedinVitterandWang(1999)).AlthoughtheapproachusedinShanmugasundarametal.(1999)offerssimilaradvantagestoourtechniquebyobtainingakernelthatexplainsthedistributionofthedata,itiswell-knownthatkernelestimationsareveryinef cientasthenumberofdimensionsgrow(Silverman,1994).Thisistruebecausetruncatingthetailsofthedistributionscanhaveanenormouseffectontheerrorsobtained.(Inotherwords,inmoderate-tohigh-dimensionalcases,regionsofrelativelowdensitycanstillbeveryimportantpartsofthedistribution.)Incontrast,itisknownthatanydistributioncanbeapproximatedarbitrarilyclosebyaparametricmodelbyusingenoughparameters(CherkasskyandMulier,1998).Infact,themodelwithwithtoomanyparametersisnotveryinformativetoend-users.Howtochoosetheconciseyetprecisemodelisonemotivationofourwork.Moreover,inShanmugasundarametal.(1999),theauthorsdecidetoretainonlythe“outliers”that tinamemorybuffer,makingtheaccuracyofthemethoddependonthedata,ratherthanonthemethoditself.

Itisalsoimportanttostressthattheprovidingcompressionofthewholedatacube,whileguaranteeingerrorboundsforeveryquery,regardlessoftheaggregationisnotaneasytask