如果我放松一些约束，我可以获得近似最近邻的算法捷径吗？

Question

我正在寻找一种每次查询时间最快的算法，用于解决类似于最近邻搜索的问题，但有两个区别：

我只需要大致确认（容忍I类和II类错误）某距离内是否存在邻居k或return的大致距离最近的邻居。
我可以一次查询很多

我想要比那里的近似最近邻库 (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

我有点怀疑基准测试，例如您链接的基准测试，因为根据我的经验，我发现手头问题的定义在重要性上远远超过任何一种算法在一组其他（可能看起来相似）问题。

更简单地说，在给定基准测试中表现出色的算法并不意味着它在您关心的问题上表现更好。即使对问题的公式进行微小或明显微不足道的更改也会显着改变任何固定算法集的性能。

也就是说，鉴于您关心的问题的具体情况，我会推荐以下内容：

使用论文 [1]
使用 SIMD 操作（英特尔芯片或 GPU 上的 SSE）来加速，最近邻问题是一个更接近金属和并行性的操作可以真正发挥作用的问题
调整算法的参数以最大化您的objective；特别是，[1] 的算法有一些易于调整的参数，这些参数将显着牺牲性能以换取准确性，请确保对这些参数执行网格搜索以进行设置他们到 最佳位置 来解决你的问题

注意：我推荐了论文 [1]，因为我已经尝试了您链接的基准中列出的许多算法，发现它们（对于图像重建任务）都不如所列方法在 [1] 中，同时比 [1] 复杂得多，这两种特性都不受欢迎。 YMMV 取决于您的问题定义。

Answer 2

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

我使用了基准测试中链接的库之一，hnswlib 因为它不仅比 annoy 的性能略有提高，而且还有一个 bulk-query 选项。 Hnswlib 的算法还允许高度灵活的 performance/accuracy 权衡以支持性能，这是 well-suited 我想做的 highly-error 容忍近似检查。此外，即使并行化改进远非线性 per-core，它仍然是一些东西。在我的特定情况下，上述因素结合起来实现了约 5 倍的加速。

正如 ldog 所说，您的里程数可能会因您的问题陈述而异。

如果我放松一些约束，我可以获得近似最近邻的算法捷径吗？

If I relax some constraints, can I get an algorithmic shortcut on Approximate Nearest Neighbors?

python

algorithm

nearest-neighbor