索引N维向量

Question

给定：一组巨大的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可能相对较大(如1005001000(M是巨大的(像数百万或数十亿(。

我正在调查https://en.wikipedia.org/wiki/Locality-sensitive_hashing.

Answer 1

天真的方法是O(N.M)，所以这里有几个选项：

1. 单轴O(N.log(M))排序

   1. (索引(按一个轴对列表进行排序

      其为CCD_ 3，但仅进行一次。

   2. 二进制搜索第一个矢量，其中有序轴具有value>=x-threshold

      这是O(N.log(M))

   3. 线性搜索矢量，直到有序轴具有value<=x+threshold

      这应该在O(N.K)附近，如果与您的选择一个。如果是，请将其添加到解决方案列表中。

2. 通过位置敏感哈希O(N+log(M))排序

   是的，这会导致O(N+log(M))，但会出现假阳性和假阴性，所以除非你能错过解决方案，否则这是不可能的，因为你需要测试所有向量才能确定。

3. 按功能O(N+log(M))排序

   这类似于#2，但您使用的不是散列，而是和相似性相关的数据特性。它可以是用于比较的任何有效值。正因为如此，才没有假阳性，也没有假阴性。

   您没有指定矢量中数据的含义，也没有指定任何范围，所以我只能在这里猜测。但你把相似性定义为欧氏距离，所以我们最好的特征是位置。

   因此，您可以创建八叉树来对数据进行空间重新排序。从那里你只需要输入向量，找到它所在的桶，并搜索附近的所有桶，直到某个阈值距离。。。

   如果将存储桶大小设置为阈值距离，则最多只搜索第一个相邻存储桶(总共8+1个(。

   从向量中获取bucket索引应该在O(N)中，将其转换为O(N+log(M))