database - 用于在度量空间中进行索引和搜索的很好解释的算法

Question

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

我更喜欢清晰而不是效率。

(*)此处更好地描述了对此的需求。

score 2 · Accepted Answer

尤其是地理数据，先看看PostGIS，看看是否需要实现什么。如果您这样做，请从GiST 上的 Wikipedia 条目中列出的论文开始。

查看您的链接，您的度量空间似乎是具有某种编辑距离作为度量的字符串。Navarro、Baeza-Yates、Sutinen 和 Tarhio，IEEE Data Engineering Bulletin，2001给出了一些解决方案的不错但过时的概述；Citeseer 上的相关论文也可能有用。Locality Sensitive Hashing是一种可能有用的新技术，但很多论文都侧重于数学。

score 1 · Accepted Answer

BK-Trees可用于索引和搜索任何遵守三角不等式的事物，包括度量空间。典型示例是在目标的给定编辑距离内搜索字符串。我在这里写了一篇关于这个的文章。

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

score 1 · Accepted Answer

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

score -1 · Accepted Answer

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

您还需要在度量空间上定义距离度量。你这样做了吗？（出于好奇，如果你这样做了，那是什么）

4 回答 4