基于分布熵的局部敏感哈希高维索引方法

本发明提供了基于分布熵的局部敏感哈希高维索引方法。该方法首先生成局部敏感哈希函数候选集合。接着，根据训练数据集，计算局部敏感哈希函数候选集合中每个哈希函数的分布熵值，并从中选取分布熵值最高的L个哈希函数作为局部敏感哈希函数集合。然后，基于该局部敏感哈希函数集合，将待索引数据集存储到哈希表中。还可以采用基于三角不等式过滤和欧氏距离排序的查询算法查询上述哈希表，得到与查询数据相似的结果集。该方法通过选择分布熵值高的哈希函数，更好地适应了数据的分布，从而优化了哈希表索引结构，减小了索引的内存消耗，同时使得查询更加准确和高效。

1.一种局部敏感哈希高维索引方法，所述方法包括：步骤1)生成局部敏感哈希函数候选集合；步骤2)根据训练数据集，计算局部敏感哈希函数候选集合中每个哈希函数的分布熵值，并从中选取分布熵值最高的L个哈希函数作为局部敏感哈希函数集合；步骤3)基于该局部敏感哈希函数集合，将待索引数据集存储到哈希表中。
2.根据权利要求1所述的方法，在所述步骤1)中局部敏感哈希函数候选集合中包括L’个哈希函数g_i(x)，其中g_i(x)＝[h_i1(x)，...h_ij(x)，...h_ik(x)]，(1≤i≤L′，1≤j≤k)，x为d维数据，d为大于2的整数。
3.根据权利要求2所述的方法，所述步骤2)包括以下步骤：步骤21)依据局部敏感哈希函数候选集合中每个哈希函数g_i(x)执行如下操作：211)为训练数据集建立一个哈希表，具有相同哈希值的数据被存储到该哈希表的同一表项中，而具有不同哈希值的数据被存储到该哈希表的不同表项中；212)统计该哈希表中不为空的表项的个数m，以及表项r中存储的数据的个数N_r(1≤r≤m)；213)计算哈希函数g_i(x)的分布熵 E g i ( x ) = - Σ r = 1 m N r Σ r = 1 m N r * log ( N r Σ r = 1 m N r ) ]]> 步骤22)从局部敏感哈希函数候选集合中选取分布熵值最高的L个哈希函数作为局部敏感哈希函数集合。
4.根据权利要求2或3所述的方法，所述步骤3)包括以下步骤：步骤31)建立L个空哈希表，每个哈希表对应于局部敏感哈希函数集合中的一个哈希函数；步骤32)采用局部敏感哈希函数集合中的每个哈希函数执行下列操作：采用该哈希函数计算待索引的数据集中每个数据的哈希值，具有相同哈希值的数据将被存储到该哈希函数对应的哈希表的同一表项中，不同哈希值的将被存储到该哈希函数对应的哈希表的不同表项中。
5.根据权利要求2或3所述的索引方法，所述步骤3)包括以下步骤：步骤31)建立L个大小为tableSize的空哈希表{Table₁，...Table_L}；步骤32)对于待索引数据集中每个数据x，采用Q_gi(x)计算该数据x的哈希值，将x存储到Table_i的第Q_gi(x)个表项的链表中，其中Q_gi(x)为： Q gi ( x ) = ( ( Σ j = 1 k r j a j ) mod prime ) mod tableSize - - - ( 3 ) ]]> 其中a_j(1≤j≤k)是采用g_i(x)＝[h_i1(x)，...h_ik(x)]对数据x计算得到的k维哈希值中第j个哈希值；r_j是随机整数，prime是一个素数，取值为2³²-5。
6.根据权利要求2或3所述的方法，步骤1)中其中，p_ij是d维向量，其元素是满足高斯正态分布的随机数；正实数w是一个划分宽度值；b_ij是[0，w]内的随机数。
7.一种对采用上述任一权利要求所述的索引方法索引的数据集进行查询的方法，所述方法包括以下步骤：对于每个哈希表Table_i，采用Q_gi(q)计算查询数据q的哈希值，从哈希表Table_i中取出该哈希值对应的表项中所存储的数据；将从L个哈希表得到数据组成相似数据的候选集合；计算查询数据和该相似数据的候选集合中的每个候选数据的欧氏距离；根据所计算的欧氏距离取出与该查询数据最接近的n个数据作为该查询数据的近似最近邻数据集合。
8.根据权利要求7所述的查询方法，还包括以下步骤：设置查询半径R；对所述相似数据的候选集合中每个候选数据，如果其欧氏范数与所述查询数据的欧氏范数的差值的绝对值大于或等于所述查询半径R，则将该候选数据从所述相似数据的候选集合中删除。