Measuring the difficulty of distance-based indexing

Abstract. Data structures for similarity search are commonly evalu-ated on data in vector spaces, but distance-based data structures are also applicable to non-vector spaces with no natural concept of dimen-sionality. The intrinsic dimensionality statistic of Chávez and Navarro provides a way to compare the performance of similarity indexing and search algorithms across different spaces, and predict the performance of index data structures on non-vector spaces by relating them to equiv-alent vector spaces. We characterise its asymptotic behaviour, and give experimental results to calibrate these comparisons.