Fractal dimension and similarity search in high-dimensional spatial databases

MALCOK M., ASLANDOGAN Y. A., Yesildirek A.

IEEE International Conference on Information Reuse and Intergration (IRI 2006), Hawaii, United States Of America, 16 - 18 September 2006, pp.380-381 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/iri.2006.252444
  • City: Hawaii
  • Country: United States Of America
  • Page Numbers: pp.380-381
  • Yıldız Technical University Affiliated: No

Abstract

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