[發明專利]一種基于位置敏感哈希的分布式索引方法

在審

• 申請號: 201310746690.0
• 申請日: 2013-12-30
• 公開（公告）號: CN103744934A
• 公開（公告）日: 2014-04-23
• 發明（設計）人: 武港山;徐向陽
• 申請（專利權）人: 南京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 黃明哲

1.一種基于位置敏感哈希的分布式索引方法，其特征是以多臺計算機作為節點，多機協同創建索引與搜索，包括以下步驟：

1)對原始海量數據利用聚類方法進行聚類，所述原始海量數據指被檢索的原始海量圖片或視頻特征數據；

2)聚類結束后，將每個聚類中心映射到不同計算機節點上；

3)將原始海量數據映射到所屬類對應的節點上，每個節點處理一個類，映射到節點上的數據作為該節點的特征數據點；

4)利用基于p-穩定分布的位置敏感哈希方法建立不同節點上的數據索引，即分布式索引，以供后續搜索；

5)根據得到的分布式索引，對查詢特征數據點進行分布式搜索，所述查詢特征數據點指待搜索的特征數據點。

2.根據權利要求1所述的一種基于位置敏感哈希的分布式索引方法，其特征是步驟1)對原始海量數據進行聚類時，首先對原始海量數據進行采樣，然后在樣本數據集上利用聚類算法進行聚類，進行聚類計算時，利用MapReduce對采樣數據進行并行聚類，得到聚類結果，所述聚類算法包括k-means，BIRCH，CLIQUE，SUBCLU，DBSCAN和近鄰傳播。

3.根據權利要求1或2所述的一種基于位置敏感哈希的分布式索引方法，其特征是步驟4)具體為：

4.1)生成基于p-穩定分布的位置敏感哈希的哈希函數i=1，...，N，其中N為哈希函數的個數，a_i為d維向量，其元素是服從高斯分布的隨機數，v表示d維特征數據點，b_i是隨機偏移，服從區間[0，w]上的均勻分布，w為一正整數，根據不同的應用場景設定；一共生成L×k個哈希函數對每個特征數據點利用生成的L×k個哈希函數進行哈希，供特征數據點所屬的節點使用，k和L的選擇對應于搜索結果質量和搜索反應速度，設定標準為p₁是位置敏感哈希函數族中近距離數據點的至少沖突概率，δ是搜索結果的最低召回率；

4.2)計算每個節點上的各特征數據點的哈希值g₀，…，g_L-1，得到節點的哈希表，其中g_f=(h_f0，…，h_f(k-1))，f=0，...，L-1，即對于每一特征數據點，將哈希得到的L×k個哈希結果每k個拼接到一起，組成一個k維向量g_f=(h_f0，…，h_f(k-1))，共L組k維向量，用這L組哈希結果向量來構成索引文件。