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

Question

我需要在Postgres（*）（PL或PL / Python）中实现某种度量空间搜索。所以，我正在寻找好的资料（或论文），对这些思想背后的机制有一个非常明确和清晰的解释，以便我自己实现它。

我希望明确效率。

（*）更好地描述了对此的需求此处。

Answer 1

特别是对于地理数据，请先查看 PostGIS ，看看是否需要实施任何内容。如果您这样做，请从 GiST上的Wikipedia条目中列出的论文开始。

查看您的链接，您的指标空间似乎是具有某种编辑距离的字符串作为指标。 Navarro，Baeza给出了一些不错但旧的概述。 -Yates，Sutinen和Tarhio，IEEE Data Engineering Bulletin，2001 ;关于Citeseer的相关文章也可能有用。 Locality Sensitive Hashing 是一种可能有用的新技术，但很多论文对数学很重视。

Answer 2

BK-Trees 可用于索引和搜索服从三角形不等式的任何内容，包括公制空间。规范示例是在目标的给定编辑距离内搜索字符串。我写了一篇关于这里的文章。

不幸的是，在Postgres中没有内置的支持。你可以使用 GIST 自己实现它，但显然是'我会做很多工作。在没有编写自己的索引而不将树存储在表中的情况下，我想不出任何方法来实现它，这显然不会非常有效。

Answer 3

您可以尝试 http://sisap.org ，其中列出了许多现代指标索引，包括BK树。您可以在C中找到代码以尝试不同的替代方案。

Answer 4

一些涉及空间搜索的技术可能对您有所帮助，包括爬坡，神经网络训练，遗传算法和粒子群。

您还需要在指标空间中定义距离指标。你有没有这样做过？（出于好奇，有什么，如果你这样做的话）