Abstract

The problem of searching the elements of a set that are close to a given query element under some similarity criterion has a vast number of applications in many branches of computer science, from pattern recognition to textual and multimedia information retrieval. We are interested in the rather general case where the similarity criterion defines a metric space, instead of the more restricted case of a vector space. Many solutions have been proposed in different areas, in many cases without cross-knowledge. Because of this, the same ideas have been reconceived several times, and very different presentations have been given for the same approaches. We present some basic results that explain the intrinsic difficulty of the search problem. This includes a quantitative definition of the elusive concept of "intrinsic dimensionality." We also present a unified Categories and Subject Descriptors: F.2.2 [Analysis of algorithms and problem complexity]: Nonnumerical algorithms and problems-computations on discrete structures, geometrical problems and computations, sorting and searching; H.2.1 [Database management]: Physical design-access methods; H.3.1 [Information storage and retrieval]: Content analysis and indexing-indexing methods; H.3.2 [Information storage and retrieval]: Information storage-file organization; H.3.3 [Information storage and retrieval]: Information search and retrieval-clustering, search process; 1.5.1 [Pattern recognition]: Models-geometric; 1.5.3 [Pattern recognition]: Clustering General Terms: Algorithms. ©2001 ACM.