database - 如何在大数据中进行模糊搜索

Question

我是那个领域的新手，我主要想知道最先进的技术是什么以及我可以在哪里阅读它。

假设我只有一个键/值存储，并且以某种方式定义了一些距离(key1，key2)(不确定它是否必须是一个度量，即三角不等式是否必须始终成立)。

我主要想要的是一个 search(key) 函数，该函数返回所有具有与搜索键相距一定距离的键的项目。也许距离限制是可配置的。也许这也只是一个惰性迭代器。也许也可以有一个计数限制，并且一个项目 (key,value) 在返回的集合中有一定的概率 P，其中 P = 1/distance(key,search-key) 左右(即完美匹配肯定是至少很有可能在盘中和势均力敌的比赛中)。

---

一个示例应用程序是 MusicBrainz 中的指纹匹配.他们使用 AcoustId指纹并定义了this compare function .他们使用 PostgreSQL GIN 索引，我猜(虽然我还没有完全理解/阅读 acoustid-server 代码)GIN Partial Match Algorithm但我还没有完全理解这是否是我要求的以及它是如何工作的。

---

对于文本，到目前为止我发现的是使用一些 phonetic algorithm根据发音简化单词。一个例子是 here .这主要是为了将搜索空间分解为更小的空间。但是，这有几个限制，例如它必须在较小的空间中仍然是完美的匹配。

但无论如何，我也在寻找更通用的解决方案(如果存在的话)。

Answer 1

没有(快速)通用的解决方案，每个应用程序都需要不同的方法。

这两个示例实际上都没有进行传统的最近邻搜索。 AcoustID(我是作者)只是在寻找完全匹配，但它会搜索大量的哈希值，希望其中一些能够匹配。语音搜索示例使用变音位将单词转换为其语音表示形式，并且也仅查找完全匹配项。

您会发现，如果您有大量数据，那么使用巨大的哈希表进行精确搜索是您唯一实际可以做的事情。那么问题就变成了如何将模糊匹配转换为精确搜索。

一种常见的方法是使用 locality-sensitive hashing (LSH) 使用智能哈希方法，但正如您在两个示例中所见，有时您可以使用更简单的方法。

顺便说一句，您正在寻找专门用于文本搜索的最简单方法，将输入拆分为 N-grams并索引那些。根据您的距离函数的定义方式，这可能会为您提供正确的候选匹配项，而无需太多工作。