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-BASEDQUASICUBES

273Figure8.Errorofrangequeriesoverthesyntheticdataset,computedfromtheapproximatebasecuboidcom-pressedwithβ=0.2.(Theerrorsreportedaretheaverageoverrangequeriesofthesameselectivity.Totalnumberofcellsis200,000.)

backward-forwardheuristicdescribedinSection2.2.

DCDyijkl=20×EffiA×EffjB×EffCk×Effl×Effkl

CDlijkl=logy ijkl=γ+γiA+γjB+γkC+γlD+γkl(6)(7)

Figure6showstheresultsonthesyntheticdataset.Thecorecuboidwasdividedwithparametersα=0.15(minimumdensityofthechunks),β=0.2(maximumerrortoler-ated)and =0.4(maximumpercentageofoutliersinthechunk).Thetableshowsthenumberofcellsinthecorecuboid,cellsthatareretainedasbelongingtosparsechunks(SingleCells),numberofparametersusedbythemodels(Parameters),numberofoutliers(Outliers),andthecompressionratio.Theresultsshowthatforthelargestset,thecompres-sionrateapproaches90%(only10%oftheoriginalspaceisneededtostoreparameters,outliersandsinglecells).Thebuildingtimegrowslinearlywiththesizeofthedataset(from11.73secondsforthesmallestdatasetto140.91secondsforthelargest;agrowthof12timesfora10foldincreaseofsizeinthedataset).Figure7showstheresultsofrunningrangequeriesagainsttheapproximaterepresentationofthecorecuboid,andthestandardcuboid