8

我正在研究 FLANN，一个用于近似最近邻搜索的库。

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

谢谢

4

1 回答 1

10

请注意，我将参考最新的 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方法使用了简单地迭代特征的替代版本，并在每个特征上调用上述方法。

如您所见，此方法有 2 个参数，它们是一对(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 实现在二进制描述符的汉明空间中工作。

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

有人可以分享更多关于在这种情况下可能使用 unsigned int 的信息吗？如果每个功能只需要 0 和 1，为什么要使用 unsigned int？

见上：该unsigned int值仅用于存储每个特征向量的相关ID。

于 2013-01-13T20:24:13.247 回答