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
intrinsic dimension (ID) in metric spaces. Some of these algorithms were
specifically for evaluating the complexity of the search on metric spaces,
based on different theories related to the distribution of distances between
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
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
searching over the considered spaces.