Fractal Dimension and Similarity Search in High-Dimensional Spatial Databases

In this paper, the relationship between the dimension of the address space and the intrinsic ("fractal") dimension of the data set is investigated. An estimate of a lower bound for the number of features needed in a similarity search is given and it is shown that this bound is a function of the intrinsic dimension of the data set. Our result indicates the "deflation" of the dimensionality curse in fractal data sets by showing the explicit relationship between the intrinsic dimension of the data set and the embedding dimension of the address space. More precisely, we show that the relationship between the intrinsic dimension and the embedded dimension is linear