我正在研究FLANN,这是一个用于搜索附近最近邻居的图书馆。

对于LSH方法,它们表示一个对象(搜索空间中的点),如
无符号int数组。我不确定他们为什么这样做,而不是
简单地将一个点表示为双精度数组(它将表示一个点
在多维向量空间中)。也许是因为LSH用于二进制
特征?有人可以分享更多有关in中可能使用unsigned int的信息吗?
这个案例?如果每个功能只需要0和1,为什么还要选择unsigned int?

谢谢

最佳答案

请注意,在撰写本文时,我将参考最新的FLANN版本,即flann-1.8.3


  对于LSH方法,它们表示一个对象(搜索空间中的点),
  作为unsigned int数组


不:这是错误的。 LshIndex类包括实现LSH索引的buildIndexImpl方法。由于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)


valueunsigned int表示特征向量唯一数字标识符(也称为特征索引)
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实现在Hamming space中适用于二进制描述符。

如果要使用带实值的描述符(在R**d中),则应参考original paper,其中包括有关如何将特征向量转换为二进制字符串以使用汉明空间和哈希函数的详细信息。


  有人可以在此分享更多有关unsigned int可能使用的信息吗?
  案件?如果每个功能只需要0和1,为什么还要选择unsigned int?


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

07-27 22:48