给出：大量N维向量-{V1，V2，V3，...，Vm}向量的示例：
[72, 100, 34, 45, 87, 123, 99, 32] // N = 8
输入：作为输入，我们将获得另一个向量，该向量的尺寸与上述集合的尺寸相同。我们将此向量称为X。
目标：从给定的向量X的给定集合中找到最相似的（或前K个相似的向量，K相对较小）。相似度定义为https://en.wikipedia.org/wiki/Euclidean_distance。
[我正在寻找一种可以给我O（log M）复杂度的方法，其中M是集合中的多个向量。
注意，N可能相对较大（例如100、500、1000）。 M很大（例如数百万或数十亿）。
我正在研究https://en.wikipedia.org/wiki/Locality-sensitive_hashing。
幼稚的方法是O(N.M)，所以这里有几个选择：
通过一个轴O(N.log(M))订购
（（索引）通过一个轴对列表进行排序
这是O(N.M.log(M))，但只完成一次。
二进制搜索的第一矢量，其中有序轴具有value>=x-threshold
这是O(N.log(M))
线性搜索向量，直到有序轴具有value<=x+threshold
这应该在O(N.K)附近，如果与您的选择一个。如果是，则将其添加到解决方案列表中。
按地区敏感的哈希排序O(N+log(M))
是的，这会导致出现O(N+log(M))，但是肯定和否定都是假的，因此除非您错过解决方案，否则这是不可行的，因为您必须测试所有向量才能确保。]]
按特征O(N+log(M))订购
这类似于＃2
，但不是使用散列，而是使用与相似性相关的数据特征。可以是任何有效的比较对象。幸好没有误报也没有误报。您未指定向量中的数据的含义，也不指定任何范围，因此我只能在这里猜测。但是您将相似性定义为欧几里德距离，因此我们的最佳特征将是位置。
因此您可以创建Octree来对数据进行空间重新排序。然后，您只需输入输入向量，即可找到存储桶所在的位置，并搜索所有存储桶附近的最大阈值距离...
如果将存储桶大小设置为阈值距离，则仅搜索最多第一个相邻的存储桶（总计8 + 1）。
从向量获取存储区索引应在O(N)中，将其转换为O(N+log(M))