问题：
我有 N（~100m）个字符串，每个 D（例如 100）个字符长并且字母低（例如 4 个可能的字符）。我想为这些 N 点（k ~ 0.1D）中的每一个找到 k 最近邻。相邻字符串通过汉明距离定义。解决方案不一定是最好的，但越接近越好。
关于问题的想法
我有一种不好的感觉，这是一个不小的问题。我读过很多论文和算法，但是其中大多数在高维度上的结果很差，并且在维度小于 5 时有效。例如，本文提出了一种有效的算法，但它的常数与维度呈指数关系。
目前，我正在研究如何以保留或可以计算汉明距离的方式减少维度。
另一种选择是局部敏感散列，在所选度量下彼此靠近的点以高概率映射到同一个桶。有什么帮助吗？你更喜欢哪个选项？