在度量空间中索引和搜索的解释良好的算法

尤其是对于地理数据,请看 PostGIS 首先看看您是否需要实现任何东西。如果有,请从 Wikipedia entry on GiST .

看你的链接,你的度量空间似乎是一些编辑距离作为度量的字符串。一些解决方案的一个不错但老掉牙的概述如下: Navarro, Baeza-Yates, Sutinen, and Tarhio, IEEE Data Engineering Bulletin, 2001 有关Citeseer的相关论文也可能有用。 Locality Sensitive Hashing 是一种可能有用的新技术,但很多论文都是数学题。

BK-Trees 对于索引和搜索任何符合三角形不等式(包括度量空间)的内容都很有用。典型示例是在目标的给定编辑距离内搜索字符串。我写了一篇关于这个的文章 here .

不幸的是,Postgres没有内置的支持。你可以自己用 GIST 但很明显这将是一项很大的工作。如果不编写自己的索引,我想不出任何方法来实现它,除非将树存储在一个表中,显然这不会非常有效。

你可以试试 http://sisap.org 其中列出了许多现代度量指标,包括BK树。您可以在C中找到代码来尝试不同的替代方法。

一些涉及空间搜索的技术可能会帮助你爬山、神经网络训练、遗传算法和粒子群。

您还需要在度量空间上定义距离度量。你这样做了吗?(出于好奇,如果您这么做了,是什么原因)