[發(fā)明專利]基于FPGA的FP?Growth算法的改進(jìn)方法及裝置

在審

• 申請?zhí)枺?/td>: 201710088020.2
• 申請日: 2017-02-19
• 公開（公告）號: CN106874479A
• 公開（公告）日: 2017-06-20
• 發(fā)明（設(shè)計）人: 曹芳;陳繼承;王洪偉
• 申請（專利權(quán)）人: 鄭州云海信息技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 鄭州大通專利商標(biāo)代理有限公司41111
• 代理人: 陳勇

1.一種基于FPGA的FP-Growth算法的改進(jìn)方法，其特征在于，包括以下步驟：

掃描Spark集群中的數(shù)據(jù)庫，獲取頻繁項集；

將頻繁項集進(jìn)行分組；

為Spark集群中的每個節(jié)點加配一塊FPGA板卡；

在FPGA板卡上對每一組的頻繁項集建FP樹；

在FPGA板卡上對每一組建的FP樹進(jìn)行遞歸挖掘；

將每一組遞歸挖掘的結(jié)果進(jìn)行合并。

2.根據(jù)權(quán)利要求1所述的基于FPGA的FP-Growth算法的改進(jìn)方法，其特征在于，將頻繁項集進(jìn)行分組，包括：

將其按頻繁1-項集順序遞減排列；

根據(jù)數(shù)據(jù)庫的大小確定分組個數(shù)，按照預(yù)先設(shè)定的分組規(guī)則將其分為若干組。

3.根據(jù)權(quán)利要求1所述的基于FPGA的FP-Growth算法的改進(jìn)方法，其特征在于，在FPGA板卡對每一組建FP樹，包括：

建立一個根節(jié)點為NULL的FP樹和一個存儲節(jié)點信息的Tab表；

將頻繁項表中的每條處理好的事務(wù)中的數(shù)據(jù)項按降序依次插入到FP樹中，構(gòu)建出FP樹的一條路徑；

在上述的插入過程中，同時用Tab的指針指向?qū)?yīng)項的節(jié)點，并將每個節(jié)點的計數(shù)增加1。

4.根據(jù)權(quán)利要求3所述的基于FPGA的FP-Growth算法的改進(jìn)方法，其特征在于，在FPGA板卡對每一組建的FP樹進(jìn)行遞歸挖掘，包括：

A：從Tab表的尾部的項開始向上遍歷FP樹，每次遍歷得到該項的條件模式基；

B：將其條件模式基轉(zhuǎn)化為條件FP樹；

C：迭代重復(fù)步驟A步驟B，直到FP樹包含一個元素項為止。

5.根據(jù)權(quán)利要求4所述的基于FPGA的FP-Growth算法的改進(jìn)方法，其特征在于，將每一組遞歸挖掘的結(jié)果進(jìn)行合并，包括：

將每一棵條件FP樹生成所有的從根節(jié)點到葉子節(jié)點的路徑，由路徑中的集合生成其所有的非空子集。

6.基于權(quán)利要求1~5所述的任一項基于FPGA的FP-Growth算法的改進(jìn)方法的基于FPGA的FP-Growth算法的改進(jìn)裝置，其特征在于，包括：

獲取模塊，用于掃描Spark集群中的數(shù)據(jù)庫，獲取頻繁項集；

分組模塊，用于將頻繁項集進(jìn)行分組；

板卡模塊，用于為Spark集群中的每個節(jié)點加配一塊FPGA板卡；

建樹模塊，用于在FPGA板卡上對每一組的頻繁項集建FP樹；

挖掘樹模塊，用于在FPGA板卡上對每一組建的FP樹進(jìn)行遞歸挖掘；

結(jié)果模塊，用于將每一組遞歸挖掘的結(jié)果進(jìn)行合并。