###
Towards Measuring the Searching Complexity of Metric Spaces

####
Edgar Chávez and Gonzalo Navarro

In recent times searching in metric spaces for proximity queries has deserved
attention in the algorithmic community due to applications linked to Web
searching, data mining and multimedia retrieval. In vector spaces, the *curse
of dimensionality* describes the phenomenon whereby the performance of all
the existing algorithms grows exponentially with the dimension. Recent worst
case lower bounds have been established for this case. In general metric spaces
the complexity is measured as the number of distance computations, but the
absence of coordinates prevents complexity analyses in terms of the dimension.
Nevertheless, for proximity queries in metric spaces a behavior closely
resembling the curse of dimensionality is observed: there are (hard) metric
spaces where all the algorithms, even those competitive in other (easy) metric
spaces, perform poorly.
In this paper we introduce a new measure of the intrinsic searching complexity
of a general metric space. This measure reflects the expected behavior of the
search algorithms on the metric space, yet it is easy to estimate and
independent of the search algorithm. We prove average case lower bounds, in
terms of this complexity measure, for a large class of proximity search
algorithms. This gives some new insight on the intrinsic difficulty of the
search problem in metric spaces.