[發明專利]云存儲系統中基于數據分布感知的近鄰查詢方法

有效

• 申請號: 201710822371.1
• 申請日: 2017-09-13
• 公開（公告）號: CN107656989B
• 公開（公告）日: 2019-09-13
• 發明（設計）人: 華宇;孫園園;馮丹;左鵬飛
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458;G06F16/28
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 廖盈春;李智

1.一種云存儲系統中基于數據分布感知的近鄰查詢方法，其特征在于，包括：

S1、從原始高維數據集中隨機抽取部分數據組成高維特征數據集；

S2、將高維特征數據集中的每一個元素表示為一個多維向量，以將高維特征數據集表示為由多個多維向量組成的矩陣，通過主成分分析來離線計算該矩陣的協方差矩陣，進而得到該矩陣的特征向量和特征值；

S3、獲取索引表中所需哈希表個數，每個哈希表中哈希函數個數以及沖突閾值；

S4、按照特征值的降序順序，將各特征值對應的特征向量一一對應的作為哈希函數的投影向量，并根據特征向量對應的特征值計算每個哈希表中每個哈希函數的權值，然后調整每個哈希表中哈希函數的切割間隔大小，最后將原始高維數據集通過優化得到的哈希函數映射到整個索引表中，產生哈希沖突的元素通過鏈表存儲；

S5、對于每一個查詢點，在每個哈希表中，通過優化后的哈希函數計算得到相應的哈希值，通過哈希值定位到哈希表中發生哈希沖突的位置，將該位置的鏈表中所有元素都存入結果候選集合中，記錄結果候選集合中每個元素與查詢點產生哈希沖突的次數，將小于預設沖突閾值的元素去除，得到近鄰查詢集合，通過將近鄰查詢集合中的每個點與查詢點進行距離計算比較，輸出所有與查詢點距離小于預設距離閾值的元素。

2.根據權利要求1所述的方法，其特征在于，步驟S2具體包括以下子步驟：

S2.1、將高維特征數據集X中的n個元素看作n個包含d個變量的向量，則將高維特征數據集X表示為由n個d維向量組成的矩陣：

S2.2、由得到協方差矩陣，其中，表示方差，同時協方差為根據協方差矩陣S計算得到特征向量組V和特征值組N；

S2.3、將特征值組N中特征值較大的前k×L個特征值對應的特征向量作為高維特征數據集X的主成分組V'，通過V'映射將高維特征數據集X表示為數據集Y，且Y＝XV'，其中，k表示每個哈希表中哈希函數的個數，L表示索引表中所需哈希表個數。

3.根據權利要求2所述的方法，其特征在于，步驟S3具體包括以下子步驟：

S3.1、由得到索引表中哈希表個數L，并得到每個哈希表中哈希函數的個數k，其中p₁表示兩個點為近似點且發生哈希沖突的概率，p₂表示兩個點不是近似點但發生哈希沖突的概率，α為沖突比例閾值且p₂＜α＜p₁，δ為近鄰查詢的成功率大小，β為局部靈敏哈希LSH的誤判率；

S3.2、得到哈希表個數L取值最小時對應的沖突比例閾值α，且其中

S3.3、由α的值得到

S3.4、根據α和L'的值，得到沖突閾值

4.根據權利要求3所述的方法，其特征在于，步驟S4具體包括以下子步驟：

S4.1、將LSH函數表示為：其中a為投影向量，p為高維特征數據集X中多維空間中任意一點，b為范圍[0,ω)中一個隨機選擇的實數，ω為投影切割間隔；

S4.2、將步驟S2.3選擇的k×L個特征向量按序一一對應的作為每個哈希函數的投影向量，假設每個哈希表中的k個特征向量對應的特征值按照降序排列依次為N＝[n₁,n₂,...,n_k]，則每個哈希函數的權值為：1≤i≤k，進而在每個哈希表中，點p的哈希值為

S4.3、在每個哈希表中，k個哈希函數的切割間隔ω相同，下一個哈希表中哈希函數的間隔ω是上一個哈希表中哈希函數的間隔ω的一半；

S4.4、根據每個哈希表中哈希函數的投影向量和切割間隔，來構建L個哈希表，每個哈希表都包含k個哈希函數，將高維特征數據集X中的所有多維空間的點都通過哈希映射插入到索引表中的每個哈希表中，發生哈希沖突的點通過鏈表存儲。

5.根據權利要求4所述的方法，其特征在于，步驟S5具體包括以下子步驟：

S5.1、對于查詢點q，計算其在每個哈希表中的哈希值g_i(q),1≤i≤L，將發生哈希沖突的對應哈希桶鏈表中的所有元素都保存到查詢結果集C(q)中，重復元素只保存一次，得到查詢點q在高維特征數據集X中的近似集；

S5.2、記錄查詢結果集C(q)中，每個點與查詢點q在索引表中發生沖突的次數，且對于查詢結果集C(q)中任意一點p，它與查詢點q的沖突次數為：假設沖突閾值為m，即查詢結果集C(q)中的某一點與查詢點q的沖突次數大于m時，才認為該點與查詢點q近似，并將該點存入精煉結果集C'(q)中；

S5.3、對于精煉結果集C'(q)中的所有點，依次與查詢點q進行歐氏距離計算，當兩點間的距離小于預設距離閾值時，則將該點作為查詢點q的近似點。