二进制特征和局部敏感哈希（LSH）

Question

我正在学习FLANN，它是一种用于近似最近邻搜索的库。对于LSH方法，它们将对象（搜索空间中的点）表示为无符号整数数组。我不确定他们为什么这样做，而不是简单地将一个点表示为双精度数组（这将代表多维向量空间中的点）。也许是因为LSH用于二进制特征？有人可以分享更多关于在此情况下使用无符号整数的可能性吗？如果每个特征只需要0和1，为什么要使用无符号整数呢？谢谢。

- user1796942

Answer 1

请注意，我将引用最新的FLANN版本，即写作时的flann-1.8.3。

对于LSH方法，它们将对象（搜索空间中的点）表示为无符号整数数组。

不正确： LshIndex类包括一个buildIndexImpl方法，实现了LSH索引。由于LSH基本上是一组哈希表，因此有效的索引发生在LshTable类上。

基本索引方法，即逐个索引一个特征向量（也称为描述符或点）的方法为：

/** Add a feature to the table
 * @param value the value to store for that feature
 * @param feature the feature itself
 */
void add(unsigned int value, const ElementType* feature) {...}

注意：方法buildIndexImpl使用了另一种简单地遍历特征并在每个特征上调用上述方法的备选版本。

可以看到，该方法有两个参数，即一对(ID, descriptor)：

1. value是一个unsigned int类型的值，代表特征向量的唯一数字标识符（也称为特征索引）
2. feature表示特征向量本身

如果你查看实现代码，可以看到第一步是对描述符值进行哈希处理，以获得相关的桶键（即指向存储此描述符ID的桶的槽位的标识符）：

BucketKey key = getKey(feature);

实际上，getKey 哈希函数 只有 用于二进制描述符，即可表示为 unsigned char 数组的描述符：

// Specialization for unsigned char
template<>
inline size_t LshTable<unsigned char>::getKey(const unsigned char* feature) const {...}

也许是因为LSH被用于二进制特征？

是的，正如上面所述，FLANN LSH实现在二进制描述符的 海明空间 中工作。

如果您要使用具有实值（在R ** d 中）的描述符，则应参考原始论文，该论文包括有关如何将特征向量转换为二进制字符串以便使用海明空间和哈希函数的详细信息。

在这种情况下，可以分享更多关于使用无符号整数的可能性吗？如果每个特征仅需要0和1，为什么需要无符号整数？

请参见上文：仅使用unsigned int 值来存储每个特征向量的相关ID。

- deltheil