问题标签 [approximate-nn-searching]

FLANN（Fast Library for Approximate Nearest Neighbors）是一个用于在高维空间中执行快速近似最近邻搜索的库。它包含一组我们发现最适合最近邻搜索的算法，以及一个根据数据集自动选择最佳算法和最佳参数的系统。FLANN 是用 C++ 编写的，包含以下语言的绑定：C、MATLAB、Python 和 Ruby。https://github.com/mariusmuja/flann

FLANN 可用的算法有哪些？它如何选择要使用的算法和参数？

我问是因为，我注意到在使用 FLANN 之前使用体素过滤器会降低 x10 倍的速度，并希望弄清楚将其归因于什么。体素过滤器去除了数据中 70% 的点，但速度下降似乎要大得多。

我想使用 Python 中的文本数据集在 Levenshtein 距离上执行最近邻搜索。搜索可以是近似的，应该使用核心 Python 库来实现，并且查询应该是接近恒定时间的操作。下面，我列出了一些我考虑过的实现以及它们的缺陷。

天真的蛮力方法

一个天真的蛮力解决方案涉及计算查询和数据集中所有文本之间的成对 Levenshtein 距离：

然而，幼稚的方法相当缓慢。对于最大文本长度为 N 的 M 个文本，搜索查询的 K 个最近邻是 O(M * N^2) 操作。为 M 个文本中的每一个找到 K 个最近的邻居是一个 O(M^2 * N^2) 操作。

指标索引

我考虑的一种解决方案是指标索引。度量索引为度量空间中的 K-最近邻搜索提供了比初始速度更好的速度。被索引的单位不必是向量，只需配上距离函数，形成度量空间即可。配备 Levenshtein 距离的字符串形成一个度量空间。

度量学习的一个很好的特性是它在核心 Python 库中实现，例如在sklearn.neighbors.BallTree. 使用球树，搜索 a 的 K 个最近邻居变成了 O(log M * N^2) 操作。为 M 个文本中的每一个找到 K 个最近的邻居是一个 O(M log M * N^2) 操作。

sklearn 实现的一个缺点是它需要输入浮点向量。因此，似乎需要从字符串到浮点向量并返回的映射方案。该解决方案可以表示多达 2^53 个字符串的数据集，这似乎足够了：

但是，速度似乎仍然是一个主要缺点。我会很感激指向在接近 O(M * N^2) 时间的 Levenshtein 距离或度量空间上提供近似 K-最近邻搜索的库的指针。

球树算法有一种方法“查询”来查找最近的向量。

编码：

但是这里的输出是所需的向量数量，即o_i，我想获得查询图像所属的叶节点中存在的所有向量数量的输出，算法执行近似最近搜索。

这是一个理论问题。

假设我有一个大小(N, D)为数百万的数据集。如果我正确理解 k-means，它会将一个空间平均划分为 k 个子空间。如果是这种情况，我们是否可以简单地使用 k-means 中心（作为根节点）进行搜索，然后根据需要跳转到叶子中，从而消除在 ANN 搜索中“近似”的需要？

在上面的示例中，如果我们有 100 万个数据点并且 k 为 1000，我们将进行 2000 次比较（1000 个中心和 1000 个数据点）以获得最近的数据点。如果这仍然太多，我们可以进一步对中心进行聚类并进行 log N 比较。

我在我的研究项目中使用 Pynndescent 作为 python 中的近似最近邻 (ANN)。我遵循 (Pynndescent) 的作者提供的相同代码。不幸的是，pynnescent 库中没有用于拟合/变换的函数，因此我可以预测结果并提取其他评估，如精度、召回、f1 分数和混淆矩阵。你能帮忙吗？

谢谢

Lucene 最近基于这个原始分支为 Lucene 9.0.0 添加了 HNSW 近似最近邻搜索 (ANN)：https ://issues.apache.org/jira/browse/LUCENE-9004 。

Lucene 是否支持预过滤？例如，假设我们要对 2020 年之后创建的文档进行矢量搜索。是否可以在相同的矢量搜索请求中过滤这些文档？还是我们必须在取回 ANN 搜索结果后进行后过滤？

我注意到这里的方法下有一个成员 acceptOrds query：https ://javadoc.io/doc/org.apache.lucene/lucene-core/latest/org/apache/lucene/util/hnsw/HnswGraph.html 。可以用来过滤吗？