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.