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

在審

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

1.一種基于敏感哈希的并行最鄰近節(jié)點(diǎn)計(jì)算方法，其特征在于，所述方法包括：

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

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

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

2.如權(quán)利要求1所述方法，其特征在于，所述針對每一個數(shù)據(jù)子集，給定查詢數(shù)據(jù)集中的任一數(shù)據(jù)q，使用基于敏感哈希的串行最鄰近節(jié)點(diǎn)計(jì)算方法，獲取該數(shù)據(jù)子集上的K近鄰居集合步驟，具體包括：

生成一組局部敏感的哈希函數(shù)簇，共有L個哈希函數(shù)；

針對每一個數(shù)據(jù)子集，將數(shù)據(jù)子集中的數(shù)據(jù)分別使用L個哈希函數(shù)計(jì)算得到L個不同的桶B1，B2，…，BL；

給定查詢數(shù)據(jù)集中的任一數(shù)據(jù)q，分別使用L個哈希函數(shù)計(jì)算出L個哈希值h1，h2，…，hL；

從每個桶Bj中找出和哈希值hj相等的數(shù)據(jù)組成集合S（q），其中1≤j≤L；

從集合S（q）中找出K個最近的鄰居作為數(shù)據(jù)q的k近鄰居集合。

3.如權(quán)利要求1或2所述方法，其特征在于，采用大頂推方法從所述近鄰總集中選取K個最近的鄰居作為數(shù)據(jù)q的K近鄰居。

4.一種分布式系統(tǒng)，其特征在于，所述分布式系統(tǒng)包括一個主節(jié)點(diǎn)和與所述主節(jié)點(diǎn)連接的若干從節(jié)點(diǎn)，其中，所述主節(jié)點(diǎn)包括：

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

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

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

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

5.如權(quán)利要求4所述分布式系統(tǒng)，其特征在于，所述近鄰計(jì)算單元包括：

哈希函數(shù)生成模塊，用于生成一組局部敏感的哈希函數(shù)簇，共有L個哈希函數(shù)；

哈希第一處理模塊，用于針對每一個數(shù)據(jù)子集，將數(shù)據(jù)子集中的數(shù)據(jù)分別使用L個哈希函數(shù)計(jì)算得到L個不同的桶B1，B2，…，BL；

哈希第二處理模塊，用于給定查詢數(shù)據(jù)集中的任一數(shù)據(jù)q，分別使用L個哈希函數(shù)計(jì)算出L個哈希值h1，h2，…，hL；

集合生成模塊，用于從每個桶Bj中找出和哈希值hj相等的數(shù)據(jù)組成集合S（q），其中1≤j≤L；

近鄰計(jì)算模塊，用于從集合S（q）中找出K個最近的鄰居作為數(shù)據(jù)q的k近鄰居集合。

6.如權(quán)利要求4或5所述分布式系統(tǒng)，其特征在于，所述接收查找單元采用大頂推方法從所述近鄰總集中選取K個最近的鄰居作為數(shù)據(jù)q的K近鄰居。