查找所有 k 最近邻

Find all k-nearest neighbors

问题：

我有 N (~100m) 个字符串，每个字符串有 D（例如 100）个字符长，字母表较低（例如 4 个可能的字符）。我想为这 N 个点（k ~ 0.1D）中的每一个找到 k-最近的邻居。相邻的字符串通过汉明距离定义。解决方案不一定是最好的，但越接近越好。

问题的思考

我有一种不好的感觉，这是一个不平凡的问题。我看过很多论文和算法，但是大多数在高维上效果不佳，并且在维数小于5时有效。例如this paper表示一种有效的算法，但其常数与维数呈指数关系。

目前，我正在研究如何以保留或计算汉明距离的方式减少维度。

另一种选择是locality sensitive hashing，在所选指标下彼此接近的点以高概率映射到同一个桶。有帮助吗？你更喜欢哪个选项？

之前问的一个问题讨论得很好，可以参考一下，

Nearest neighbors in high-dimensional data?

除此之外，你还可以看看，

很少有论文分析不同的方法，