Estimating the Selectivity of Spatial Queries Using the orrelation' Fractal Dimension

dc.contributor.authorBelussi, Albertoen_US
dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:58:53Z
dc.date.available2007-05-23T09:58:53Z
dc.date.issued1995en_US
dc.description.abstractWe examine the estimation of selectivities for range and spatial join queries in real spatial databases. As we have shown earlier [FK94a], real point sets: (a) violate consistently the ﲵniformity' and ndependence' assumptions, (b) can often be described as ﲦractals , with non-integer (fractal) dimension. In this paper we show that, among the infinite family of fractal dimensions, the so called ﲃorrelation Dimensions D2 is the one that we need to predict the selectivity of spatial join.<P>The main contribution is that, for all the real and synthetic point- sets we tried, the average number of neighbors for a given point of the point-set follows a power law, with D2 as the exponent. This immediately solves the selectivity estimation for spatial joins, as well as for ﲢiased range queries (i.e., queries whose centers prefer areas of high point density).<P>We present the formulas to estimate the selectivity for the biased queries, including an integration constant (K hape' ) for each query shape. Finally, we show results on real and synthetic points sets, where our formulas achieve very low relative errors (typically about 10%, versus 40% - 100% of the uniform assumption).en_US
dc.format.extent1181815 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/5625
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1995-37en_US
dc.subjectdistributed information processingen_US
dc.subjectalgorithmsen_US
dc.subjectcomputational geometryen_US
dc.subjecttelemedicineen_US
dc.subjectdatabase - spatial databaseen_US
dc.subjectquery optimizationen_US
dc.subjectfractalsen_US
dc.subjectSystems Integration Methodologyen_US
dc.titleEstimating the Selectivity of Spatial Queries Using the orrelation' Fractal Dimensionen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR_95-37.pdf
Size:
1.13 MB
Format:
Adobe Portable Document Format