给出： 大量的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 类似，但不是使用哈希，而是使用与相似性相关的数据功能。可以是任何有效的比较对象。幸好没有误报也没有误报。
您未指定vector中数据的含义，也不指定任何范围，因此我只能在这里猜测。但是您将相似性定义为欧几里得距离，所以我们最好的特征就是位置。
因此，您可以创建Octree来对数据进行空间重新排序。然后，您只需输入向量即可找到其所在的存储区，然后搜索所有存储区附近的某个阈值距离...
如果将存储桶大小设置为阈值距离，则最多只能搜索第一个相邻的存储桶（总计8 + 1）。
从向量中获取存储区索引应该在O(N)中，并将其转换为O(N+log(M))