RELAXING THE UNIFORMITY AND INDEPENDENCE ASSUMPTIONS USING THE CONCEPT OF FRACTAL DIMENSION

We propose the concept of fractal dimension of a set of points, in ord er to quantify the deviation from the uniformity distribution. Using m easurements on real data sets (road intersections of U.S. counties, po pulation versus area of different nations, etc.) we provide evidence t hat real data indeed are skewed, and, moreover, we show that for sever al scales of interest they behave as mathematical fractals with a meas urable noninteger fractal dimension. Armed with this tool, we then sho w its practical use in predicting the performance of spatial access me thods and, specifically, of R-trees. We provide the first analysis of R-trees for skewed distributions of points; we develop a formula that estimates the number of disk accesses for range queries, given only th e fractal dimension of the point set and its count. Experiments on rea l data sets show that the formula is very accurate; the relative error is usually below 5%, and it rarely exceeds 10%. We believe that the f ractal dimension will help replace the uniformity and independence ass umptions, allowing more accurate analysis for any spatial access metho d, as well as better estimates for query optimization on multi attribu te queries. (C) 1997 Academic Press.