Institute for Systems Research

Permanent URI for this communityhttp://hdl.handle.net/1903/4375

Browse

Author: search.filters.author.Faloutsos, ChristosSubject: search.filters.subject.computational geometry

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Estimating the Selectivity of Spatial Queries Using the orrelation' Fractal Dimension
    (1995) Belussi, Alberto; Faloutsos, Christos; ISR
    We 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.

    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).

    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).

  • Thumbnail Image
    Item
    Analysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectangles
    (1994) Faloutsos, Christos; Jagadish, H.V.; Manolopoulos, Yannis; ISR
    We give a closed-form expression for the average number of n- dimensional quadtree nodes (ieces' or locks') required by an n-dimensional hyper-rectangle aligned with the axes. Our formula includes as special cases the formulae of previous efforts for 2- dimensional spaces [8]. It also agrees with theoretical and empirical results that the number of blocks depends on the hyper- surface of the hyper-rectangle and not on its hyper-volume. The practical use of the derived formula is that it allows the estimation of the space requirements of the n-dimensional quadtree decomposition. Quadtrees are used extensively in 2- dimensional spaces (geographic information systems and spatial databases in general), as well in higher dimensionality spaces (as oct-trees for 3-dimensional spaces, e.g. in graphics, robotics and 3-dimensional medical images [2]). Our formula permits the estimation of the space requirements for data hyper- rectangles when stored in an index structure like a (n- dimensional) quadtree, as well as the estimation of the search time for query hyper-rectangles. A theoretical contribution of the paper is the observation that the number of blocks is a piece-wise linear function of the sides of the hyper-rectangle.