Searching in metric spaces
Searching in metric spaces
复制标题
DOI：
10.1145/502807.502808
复制
发表时间：
2001-09-01
影响因子：
16.6
通讯作者：
Marroquín, JL
中科院分区：
文献类型：
--
作者：
Chávez, E;Navarro, G;Marroquín, JL
在某种相似性准则下搜索集合中与给定查询元素接近的元素的问题在计算机科学的许多分支中有着大量的应用，从模式识别到文本和多媒体信息检索。我们感兴趣的是相当一般的情况下，相似性标准定义了一个度量空间，而不是一个向量空间的更严格的情况。在不同的领域提出了许多解决方案，在许多情况下没有交叉知识。正因为如此，同样的想法已经被重新考虑了好几次，而且对同样的方法给出了非常不同的介绍。我们提出了一些基本的结果，解释搜索问题的内在困难。这包括对难以捉摸的“内在维度”概念的定量定义。“我们还提出了一个统一的观点，所有已知的建议，以组织度量空间，以便能够理解他们在一个共同的框架。大多数方法都是一些不同概念的变体。我们将这些作品组织在一个分类法中，使我们能够从以前没有注意到的概念组合中设计新的算法，因为不同社区之间缺乏沟通。我们目前的实验验证我们的结果，并比较现有的方法。最后，我们对从业人员提出了建议，并就未来的发展提出了开放性问题。
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 view of all the known proposals to organize metric spaces, so as to be able to understand them under a common framework. Most approaches turn out to be variations on a few different concepts. We organize those works in a taxonomy that allows us to devise new algorithms from combinations of concepts not noticed before because of the lack of communication between different communities. We present experiments validating our results and comparing the existing approaches. We finish with recommendations for practitioners and open questions fur future development.