Searching in metric spaces：（度量空间中有哪些信誉好的足球投注网站）.pdfVIP

Searching in Metric Spaces ´ EDGAR CHAVEZ Escuela de Ciencias F´ısico-Matem´aticas, Universidad Michoacana GONZALO NAVARRO, RICARDO BAEZA-YATES Depto. de Ciencias de la Computaci´on, Universidad de Chile AND ´ ´ JOSE LUIS MARROQUIN Centro de Investigaci´on en Matem´aticas (CIMAT ) 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 a