[發明專利]一種獲取數據流頻繁項的方法

有效

• 申請號: 201810857265.1
• 申請日: 2018-07-31
• 公開（公告）號: CN109165241B
• 公開（公告）日: 2023-06-30
• 發明（設計）人: 李文海;譚薇薇;謝晨陽
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06N5/025
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魯力

1.一種獲取數據流頻繁項的方法，其特征在于，包括：

從數據流中獲取數據項；

在預設數量的數據結構集中，根據所述數據項生成頻繁項的數據結構集,?具體包括

串行算法：針對單個的處理核對進行處理，得到若干分支結果；

并行算法：針對串行算法得到的分支結果進行合并處理，并得到整合結果；

并行算法包括數據分塊和概要合并兩大部分，定義輸入流S由n個數據元素構成，為并行處理核的個數，則并行算法步驟包括：

步驟SP1，數據分塊；在此部分，每一個處理核將遵循一定的規則，把當前到來的所有數據進行分塊，具體的分塊規則根據具體應用而定，具體步驟如下：

步驟SP11，若為二路并行，數據分塊按照數據項下標的奇偶次序進行均分，并使得每個處理核分到或個元素即可；

步驟SP12，若為N路并行，其中N＞2，數據分塊按照數據項下標次序的模運算結果進行劃分，并使得每個處理核分到到或個元素即可；

步驟SP2，每個處理核對分配到數據項，依照串行算法所描述的方法進行數據概要的提取，提取結果存入哈希表中以備后續匯合部分使用，按照數據結構存儲，數據項為關鍵字，另還包含該數據項對應的統計頻度以及累積誤差；

步驟SP3，令各路哈希表按照數據項的統計頻度進行排序，按照頻度排序，記錄下每張哈希表統計頻度最小項的頻度值，

，表示求最小值；

步驟SP4，對步驟SP2中提取的各路數據概要進行合并，分為二路并行和N路并行，N＞2；

步驟SP41，若為二路并行，具體步驟為：

步驟SP411，步驟SP2生成的兩張哈希表分別為、，概要合并策略描述為：首先遍歷掃描每一個數據項，檢查中的每一項是否出現在中；

步驟SP412，若中數據項同時出現在中，則將數據項相同的、的數據結構進行合并，對相應的統計頻次和累積誤差求和，并將數據結構中數據的求和結果存入結果哈希表，同時從中刪除剛進行求和運算的數據結構；

步驟SP413，若中數據項沒有出現在中，則將中該數據結構的統計頻次、累積誤差分別加上步驟SP3中所對應的值，最后將求和結果存入結果哈希表；

步驟SP42，若為N路并行，具體步驟為：

步驟SP421，步驟SP2生成的N張哈希表分別為，，…，“概要合并”策略描述為：首先遍歷掃描每一個數據項，檢查中的每一項是否出現在余下所有哈希表，…中；

步驟SP422，若中數據項同時出現在余下所有哈希表，…中，則將數據項相同的，，…的數據結構進行合并，對相應的統計頻次和累積誤差求和，并將數據結構中數據的求和結果存入結果哈希表中，同時從，…中刪除剛進行求和運算的數據結構；

步驟SP423，若中數據項沒有出現在，…之中某一個哈希表中，則將中該數據結構的統計頻次、累積誤差分別加上步驟SP3中所對應的值以及加上除以外其他哈希表對應的統計頻次和累積誤差，同時從除以外其他哈希表中刪除剛進行過求和運算的數據結構，最后將求和結果存入結果哈希表；

步驟SP5，進一步處理；

步驟SP51，若為二路并行，具體步驟為：

步驟SP511，全部數據項掃描完畢后，對進行類似的遍歷掃描，在步驟SP4操作中，由于中數據項與重復的數據結構已全部被刪除，故余下的數據項一定都是獨有的；

步驟SP512，對中剩下的每一個數據結構，只需在其統計頻次及累積誤差項上加上步驟SP3中所對應的值，最后將所有結果存入哈希表中即可；

步驟SP52，若為N路并行，具體步驟為：

步驟SP521，全部數據項掃描完畢后，對，…依次挨個進行類似的遍歷掃描；

步驟SP522，，…中任何表S_i遍歷掃描操作均與相同：

步驟SP5221，首先遍歷掃描S_i每一個數據項，檢查中的每一項是否出現在余下所有哈希表，，，…中

步驟SP5222，若S_i中數據項同時出現在余下所有哈希表，，，…中，則將數據項相同的，，…數據結構進行合并，將對應的統計頻次和累積誤差求和，并將數據結構的求和結果存入結果哈希表S_n+1中，同時從，，，…中刪除剛進行過求和運算的數據結構；

步驟SP5223，若中數據項沒有出現在，，，…之中某一個哈希表中，則將中該數據結構的統計頻次、累積誤差分別加上所對應的值以及加上除以外其他哈希表對應的統計頻次和累積誤差，同時從除以外其他哈希表中刪除剛進行過求和運算的數據結構，最后將求和結果存入結果哈希表；

步驟SP523，…全部數據項掃描完畢后，對進行類似的遍歷掃描，在步驟SP42、SP52操作中，由于Sn中數據項與…重復的數據結構已全部被刪除，故余下的數據項一定都是獨有的；

步驟SP524，對中剩下的每一個數據結構，只需在統計頻次及累積誤差項上加上步驟SP3中…各表所對應的值…，最后將所有結果存入哈希表中即可；

步驟SP6，分塊數據和概要合并過程完成；若對查詢語句的返回結果的數量進行限制，則按照限定獲得查詢結果；

其中，所述數據結構中包括與數據項相關聯的統計信息；

所述串行算法具體包括：

步驟SS2，對數據項的處理，具體如下：

步驟SS21，若數據結構集中的數據結構的數據項與所述獲取的數據項相同，則數據結構的統計頻度加1；

步驟SS22，若所述獲取的數據項沒有與數據結構集中的數據結構的數據項相同的，但存在空閑計數器，表示空，則將獲取的數據項分配給空閑的計數器，并設置統計頻度為1；

步驟SS23，若所述獲取的數據項沒有與數據結構集中的數據結構的數據項相同的，也不存在空閑計數器，則數據結構集中的所有數據結構的數據項的統計頻度均減1；

步驟SS3，整理數據結構集，具體步驟如下：

步驟SS31，如果數據結構集中的數據結構統計頻度，則對其累積誤差加1得到；

步驟SS32，如果數據結構集中的數據結構統計頻度，則使數據結構。

2.根據權利要求1所述的方法，其特征在于，所述數據結構，至少包括以下數據：數據項，數據項的統計頻度和累計誤差。