[發明專利]分類方法、查找方法和設備

有效

• 申請號: 201410373639.4
• 申請日: 2014-07-31
• 公開（公告）號: CN105302838B
• 公開（公告）日: 2019-01-15
• 發明（設計）人: 虞志益;周力君;施煒勁;周海捷
• 申請（專利權）人: 華為技術有限公司;復旦大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/27
• 代理公司: 北京龍雙利達知識產權代理有限公司 11329
• 代理人: 王君;肖鸝

本發明實施例提供了一種分類方法、查找方法和設備。該分類方法用于包括X個節點和一個主節點的分布式系統中，該分類方法包括：第一節點將主節點分配的待分類數據進行哈希編碼得到哈希碼，第一節點為該X個節點之一；第一節點將多個哈希碼根據高m位存儲到第一節點的s個第一存儲桶中，使得s個第一存儲桶中的每個第一存儲桶中的哈希碼的具有相同的高m位，并且s個第一存儲桶中的不同第一存儲桶中的哈希碼具有不同的高m位；第一節點與X個節點中的第二節點交換各自的s個第一存儲桶中的哈希碼，使得具有相同高m位的哈希碼唯一對應所述X個節點中的一個節點。本發明實施例的技術方案使得在查找時能夠提高查找速度。

技術領域

本發明涉及通信領域，尤其涉及分類方法、查找方法和設備。

背景技術

基于Mahout機器學習平臺的分布式集群文本分類技術，將任務切割給多個從機并行執行，由主機匯總詞頻。在Mahout平臺中文本查找使用哈希樹結構來完成新輸入單詞的詞頻查找過程，利用哈希函數對字符串生成32位(bits)的哈希編碼進行尋址。對于每個從機，采用雙重哈希線性探測的方法，來匹配特定單詞并統計詞頻。雙重哈希線性探查法使用兩個哈希函數在哈希表中形成一個探查序列。可以沿此探查序列逐個查找，直到找到給定的關鍵字。由于哈希樹是分布式地存放在集群各節點(即從機)中，探查序列對應的哈希地址跳躍地分布在整個分布式集群中各節點對應的哈希表中。因此在采用雙重哈希線性探查法查找存在沖突的關鍵字時，需要跨節點查找，查找速度較慢。

發明內容

本發明實施例提供了一種分類方法、查找方法和設備，使得在查找時能夠提高查找速度。

第一方面，提供了一種分類方法，分類方法用于分布式系統中，分布式系統包括一個主節點和X個節點，方法包括：第一節點將主節點分配的待分類數據進行哈希編碼得到多個哈希碼，第一節點為X個節點之一；第一節點將多個哈希碼根據高m位存儲到第一節點的s個第一存儲桶中，使得s個第一存儲桶中的每個第一存儲桶中的哈希碼具有相同的高m位，并且s個第一存儲桶中的不同第一存儲桶中的哈希碼具有不同的高m位；第一節點與X個節點中的第二節點交換各自的s個第一存儲桶中的哈希碼，使得X個節點中的每個節點的第二存儲桶存儲X個節點中的具有相同高m位的哈希碼，并且X個節點中的不同節點的第二存儲桶中存儲的哈希碼具有不同的高m位；第一節點將X個節點中與第一節點對應的具有相同高m位的哈希碼存儲到第一節點的第二存儲桶中。

結合第一方面，在第一種可能的實現方式中，第一節點與X個節點中的第二節點交換各自的s個第一存儲桶中的哈希碼，使得X個節點中的每個節點的第二存儲桶存儲X個節點中的具有相同高m位的哈希碼，包括：第一節點確定第二節點對應的哈希碼的高m位，將與第二節點對應的哈希碼的高m位相同的第一節點的第p個存儲桶中的哈希碼發送至第二節點，以便第二節點將第一節點的第p個存儲桶中的哈希碼與具有相同高m位的第二節點的第q個存儲桶中的哈希碼存儲在第二節點的第二存儲桶中；第一節點接收第二節點發送的第x個存儲桶中的哈希碼，其中，第一節點將X個節點中與第一節點對應的具有相同高m位的哈希碼存儲到第一節點的第二存儲桶中，包括：第一節點將第二節點發送的第x個存儲桶中的哈希碼與具有相同高m位的第一節點的第y個存儲桶中的哈希碼存儲在第一節點的第二存儲桶中，使得具有相同高m位的哈希碼唯一對應X個節點中的一個節點。

結合第一方面或第一種可能的實現方式，在第二種可能的實現方式中，該分類方法還包括：第一節點將第一節點的第二存儲桶中的哈希碼根據次高n位存儲到t個第三個存儲桶中，其中t個第三存儲桶中的每個第三存儲桶中的哈希碼具有相同的高m位和次高n位，并且t個第三存儲桶中的不同第三存儲桶中的哈希碼具有不同的高m位和次高n位。

結合第二種可能的實現方式，在第三種可能的實現方式中，該分類方法還包括：第一節點將t個第三存儲桶中的每個第三存儲桶中的哈希碼排序；第一節點獲取每個第三存儲桶中的預設哈希碼和預設哈希碼在第三存儲桶中的位置信息；第一節點根據每個第三存儲桶中的預設哈希碼和預設哈希碼在第三存儲桶中的位置信息生成查找表，以便第一節點根據查找表確定待查找的哈希碼在第三存儲桶中的位置。