Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension
| dc.contributor.author | Belussi, Alberto | en_US |
| dc.contributor.author | Faloutsos, Christos | en_US |
| dc.date.accessioned | 2004-05-31T21:03:04Z | |
| dc.date.available | 2004-05-31T21:03:04Z | |
| dc.date.created | 1995-02 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | We examine the estimation of selectivities for range and spatial join queries in real spatial databases. As we have shown earlier, real point sets: (a) violate consistently the "uniformity" and "independence" assumptions, (b) can often be described as "fractals", with non-integer (fractal) dimension. In this paper we show that, among the infinite family of fractal dimensions, the so called "Correlation Dimension" D2 is the one that we need to predict the selectivity of spatial join. 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 "biased" range queries (i.e., queries whose centers prefer areas of high point density). We present the formulas to estimate the selectivity for the biased queries, including an integration constant (Kshape) for each query shape. Finally, we show results on real and synthetic point sets, where our formulas achieve very low relative errors (typically about 10%, versus 40%-100% of the uniform assumption). | en_US |
| dc.format.extent | 1340025 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/425 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | Computer Science Department Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3423 | en_US |
| dc.title | Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension | en_US |
| dc.type | Technical Report | en_US |