[發(fā)明專利]基于敏感哈希的并行最鄰近節(jié)點計算方法及分布式系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201310655600.7
• 申請日: 2013-12-05
• 公開（公告）號: CN104699701A
• 公開（公告）日: 2015-06-10
• 發(fā)明（設(shè)計）人: 范成林;羅軍
• 申請（專利權(quán)）人: 深圳先進技術(shù)研究院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 深圳中一專利商標(biāo)事務(wù)所 44237
• 代理人: 張全文

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及一種基于敏感哈希的并行最鄰近節(jié)點計算方法及分布式系統(tǒng)。

背景技術(shù)

KNN（k-Nearest?Neighbor?algorithm,最鄰近節(jié)點算法）也稱為鄰近算法,是電子信息分類器算法的一種。KNN算法對包容型數(shù)據(jù)的特征變量篩選尤其有效。如圖1所示的KNN算法示意圖，給定查詢數(shù)據(jù)集R和被查詢數(shù)據(jù)集S，圖中實心點為集合R中的點，空心點為集合S中的點，對于集合R中的任意一點q，經(jīng)KNN算法處理后返回集合S中距離點q的k個最近的點，比如根據(jù)圖1所示，返回離點q最近的三個點：p1、p2、p3。

局部敏感哈希LSH算法是一種用于高效求解最近鄰搜索問題的Hash算法。LSH算法的基本思想是利用一個hash函數(shù)把集合中的元素映射成hash值，使得相似度越高的元素hash值相等的概率也越高。

基于敏感哈希的串行KNN計算方法步驟如下：

A.產(chǎn)生一組局部敏感的哈希函數(shù)簇，共L個哈希函數(shù)；

B.將被查詢數(shù)據(jù)集S中的數(shù)據(jù)分別使用L個哈希函數(shù)分別哈希到L個不同的桶B1，B2，B3,…，BL中，即桶中的每個哈希值對應(yīng)數(shù)據(jù)集S中的若干數(shù)據(jù)；

C.對于查詢數(shù)據(jù)集R中的任一數(shù)據(jù)q,分別使用L個哈希函數(shù)計算出L個哈希值h1，h2，h3，…，hL；

D.對于查詢數(shù)據(jù)集R中任意數(shù)據(jù)q，從每個桶Bj中找出和哈希值hj相等的數(shù)據(jù)（1<=j<=L），加入到集合S(q)中；

E.對于查詢數(shù)據(jù)集R中任意數(shù)據(jù)數(shù)據(jù)q，從集合S(q)中找出K個最近的鄰居作為q的K近鄰居。

現(xiàn)有局部敏感哈希的串行KNN算法無法處理海量數(shù)據(jù)，當(dāng)被查詢數(shù)據(jù)集S中數(shù)據(jù)量很大時，無法一次將S中的所有數(shù)據(jù)在單個計算機節(jié)點載入內(nèi)存，也就無法一次將全部數(shù)據(jù)哈希到桶中。當(dāng)數(shù)據(jù)量很大的時候，現(xiàn)有基于敏感哈希的串行KNN算法計算耗時長。

發(fā)明內(nèi)容

鑒于上述問題，本發(fā)明的目的在于提供一種基于敏感哈希的并行最鄰近節(jié)點計算方法及分布式系統(tǒng)，旨在解決現(xiàn)有基于敏感哈希的串行KNN算法處理海量數(shù)據(jù)耗時長的技術(shù)問題。

一方面，所述基于敏感哈希的并行最鄰近節(jié)點計算方法包括下述步驟：

將被查詢數(shù)據(jù)集劃分成若干數(shù)據(jù)子集；

針對每一個數(shù)據(jù)子集，給定查詢數(shù)據(jù)集中的任一數(shù)據(jù)q，使用基于敏感哈希的串行最鄰近節(jié)點計算方法，獲取該數(shù)據(jù)子集上的K近鄰居集合；

將所有獲取到的K近鄰居集合組成近鄰總集，從所述近鄰總集中選取K個最近的鄰居作為數(shù)據(jù)q的K近鄰居。

另一方面，分布式系統(tǒng)一個主節(jié)點和與所述主節(jié)點連接的若干從節(jié)點，其中，所述主節(jié)點包括：

數(shù)據(jù)劃分單元，用于將被查詢數(shù)據(jù)集劃分成若干數(shù)據(jù)子集；

接收查找單元，用于接收各個從節(jié)點返回的K近鄰居集合和數(shù)據(jù)q，并將所有接收到的K近鄰居集合組成近鄰總集，從所述近鄰總集中選取K個最近的鄰居作為數(shù)據(jù)q的K近鄰居；

所述從節(jié)點包括：

近鄰計算單元，用于針對每一個數(shù)據(jù)子集，給定查詢數(shù)據(jù)集中的任一數(shù)據(jù)q，使用基于敏感哈希的串行最鄰近節(jié)點計算方法，獲取該數(shù)據(jù)子集上的K近鄰居集合，以及將所述K近鄰居集合和數(shù)據(jù)q發(fā)送給主節(jié)點。

本發(fā)明的有益效果是：本發(fā)明將被查詢數(shù)據(jù)集中的海量數(shù)據(jù)分組劃分成多個數(shù)據(jù)子集，然后針對每個數(shù)據(jù)子集，對于給定的查詢數(shù)據(jù)集中的任一數(shù)據(jù)q，采用基于敏感哈希的串行KNN算法計算出的K近鄰居集合，最后將所有的K近鄰居集合組成近鄰總集，從所述近鄰總集中選取K個最近的鄰居作為數(shù)據(jù)q的K近鄰居，由于將海量數(shù)據(jù)劃分為多個數(shù)據(jù)子集，各個子節(jié)點進行并行KNN計算，提高了計算效率，大大縮短了查詢搜索時間。

附圖說明

圖1是本發(fā)明實施例提供的基于敏感哈希的并行最鄰近節(jié)點計算方法的流程圖；

圖2是圖1中步驟S102的優(yōu)選流程圖；

圖3是本發(fā)明實施例提供分布式系統(tǒng)的結(jié)構(gòu)圖；

圖4是本發(fā)明實施例提供的近鄰計算單元的優(yōu)選結(jié)構(gòu)圖。

具體實施方式

為了使本發(fā)明的目的、技術(shù)方案及優(yōu)點更加清楚明白，以下結(jié)合附圖及實施例，對本發(fā)明進行進一步詳細(xì)說明。應(yīng)當(dāng)理解，此處所描述的具體實施例僅僅用以解釋本發(fā)明，并不用于限定本發(fā)明。

為了說明本發(fā)明所述的技術(shù)方案，下面通過具體實施例來進行說明。

圖1示出了本發(fā)明實施例提供的基于敏感哈希的并行最鄰近節(jié)點計算方法的流程，為了便于說明僅示出了與本發(fā)明實施例相關(guān)的部分。