如果我放宽一些限制，我能得到一个算法的近邻的捷径吗？

Question

对于类似于最近邻搜索的问题，我正在寻找一种每次查询时间最快的算法，但有两个不同之处：

• 我只需要大致确认(容忍I型和II型错误)邻居在一定距离内的存在，或返回近邻的近似距离。
• 我可以一次查询很多

我想要比近似最近的邻居库(https://github.com/erikbern/ann-benchmarks)更好的吞吐量，它看起来更适合单个查询。特别是，第一准则的算法松弛似乎应该为算法捷径留出空间，但我在文献中找不到任何解决方案，也无法找到如何设计一个解决方案。

下面是我目前最好的解决方案，它在每个CPU上以大约10k /秒的速度运行。如果可能的话，我正在寻找接近数量级加速的东西。

sample_vectors = np.random.randint(low=0, high=2, size=(10000, vector_size))
new_vectors = np.random.randint(low=0, high=2, size=(100000, vector_size))

import annoy
ann = annoy.AnnoyIndex(vector_size, metric='hamming')
for i, v in enumerate(sample_vectors):
    ann.add_item(i, v)
ann.build(20)

for v in new_vectors:
    print(ann.get_nns_by_vector(v, n=1, include_distances=True))

Answer 1

我很感激这些解决方案，他们给了我一些想法，但我会回答我自己的问题，因为我找到了一个解决了我的问题的解决方案，也许它将在未来帮助其他人。

我使用了基准测试中链接的库之一恩斯瓦利布，因为它不仅比not稍微提高了性能，而且还具有批量查询选项。Hnswlib的算法还允许在性能上进行高度灵活的性能/精度权衡，这非常适合于我想做的高度容错的近似检查。此外，即使并行化的改进远远不是线性的每核，它仍然是一些东西。在我的特殊情况下，上述因素加在一起可以加速5倍。

正如狗狗说的，你的里程可能会因你的问题陈述而有所不同。

Answer 2

我有点怀疑基准，如你所链接的基准，因为在我的经验中，我发现手头问题的定义在重要性上远远超过任何一种算法在另一组(可能类似的)问题上的优点。

简单地说，在给定的基准测试中，一个高性能的算法并不意味着(而不是)会在您所关心的问题上具有更高的性能。即使是对问题的表述进行微小的或看似微不足道的更改，也会显著改变任何固定算法集的性能。

尽管如此，考虑到您所关心的问题的具体情况，我建议如下：

• 使用本文[1]中描述的级联方法
• 使用SIMD操作(无论是英特尔芯片上的SSE还是GPU)来加速，最近的邻居问题是一个更接近金属的操作和并行性可以真正发光的问题。
• 优化算法的参数以最大化您的目标；特别是[1]的算法有几个容易调优的参数，这些参数将极大地牺牲性能以获得准确性，请确保对这些参数执行网格搜索，以将它们设置为解决问题的最佳位置。

注意:我推荐了这篇论文[1]，因为我尝试了基准测试中列出的许多算法，您链接了这些算法，发现它们都不如[1]中列出的方法(用于图像重建的任务)，同时比[1]复杂得多，这都是不可取的特性。YMMV取决于问题的定义。