algorithm - 快速计算具有最小汉明距离的对

问题
假设有n个（约100k-1m）整数/位串，每个k（例如256）位长。算法应该返回最小成对汉明距离的k对。
例子

N = 4
K = 8
i1 = 00010011
i2 = 01010101
i3 = 11000000
i4 = 11000011


HammingDistance(i1,i2) = 3
HammingDistance(i1,i3) = 5
HammingDistance(i1,i4) = 3
HammingDistance(i2,i3) = 4
HammingDistance(i2,i4) = 4
HammingDistance(i3,i4) = 2

对于k=1，它应该返回pairlist{（i3，i4）}。对于k=3，它应该返回{（i1，i2），（i1，i4），（i3，i4）}。等等。
算法
naive实现计算所有成对距离，对成对进行排序，并返回距离最小的k:o（n^2）。有没有更好的数据结构或算法？似乎不能使用Efficiently find binary strings with low Hamming distance in large set中的思想，因为没有单个查询整数。

最佳答案

最近的论文“The Closest Pair Problem under the Hamming Metric”只有涉及n^2因子的算法（除非k非常大）。即使只找到一对。因此，除非对实例的结构做进一步的假设，否则很难改进这一点。例如，如果假设hamming距离不是很大，可以对一些列进行采样，在这些列完全匹配的假设下，根据这些列将字符串散列到bucket中，然后分别在每个bucket中进行成对比较。对另一组随机列重复此操作，以最小化丢失某些对的概率。