An Empirical Evaluation of Intrinsic Dimensionality Estimators
Cristian Bustos, Gonzalo Navarro, Nora Reyes, and Rodrigo Paredes
We study the behavior of different algorithms that attempt to
estimate the
intrinsic dimension (ID) in metric spaces. Some of these algorithms were
developed
specifically for evaluating the complexity of the search on metric spaces,
based on different theories related to the distribution of distances between
objects
on such spaces. Others were designed originally only for vector spaces and
they have been adapted so that they can be applied to metric spaces.
To determine the goodness of the ID estimation obtained
with each algorithm ---or at least determine which one fits the best to the
actual difficulty
of the search process on the tested metric spaces--- we make comparisons
using two indices, one based on pivots and the other on compact partitions.
This allows us to verify if the considered ID estimators reflect the actual
hardness of
searching over the considered spaces.