[發明專利]一種自修復的計數式摘要方法

在審

• 申請號: 202010219504.8
• 申請日: 2020-03-25
• 公開（公告）號: CN111460230A
• 公開（公告）日: 2020-07-28
• 發明（設計）人: 符永銓;沈思淇;王慶林;黃春;蘇華友;李榮春;姜晶菲;李東升;竇勇
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/90
• 分類號: G06F16/90;G06F16/901;G06F16/903
• 代理公司: 長沙國科天河知識產權代理有限公司 43225
• 代理人: 董惠文

1.一種自修復的計數式摘要方法，其特征在于，包括以下步驟，

S1，構建自修復的計數式摘要結構：對計數式摘要中的桶增加鍵校驗域；

S2，執行鍵值對插入操作：將一個鍵值對摻入到所述計數式摘要結構中，并在校驗域記錄插入到桶中的鍵校驗域；

S3，執行鍵值對刪除操作：利用所述鍵校驗域信息計算一個鍵對應的桶的集合，僅保留一個桶的值并從其他桶中刪除該鍵值對；

S4，執行鍵值對解碼操作：從所述計數式摘要結構中發現并修復多個鍵值對共用的桶；

S5，執行鍵值對查詢操作：查詢一個鍵值對是否記錄到所述計數式摘要結構中。

2.根據權利要求1所述的一種自修復的計數式摘要方法，其特征在于，步驟S1中，每個所述計數式摘要結構包括K個數組，每個所述數組包括m個桶，其中參數K和m是系統預先設置的參數，每個所述桶至少包括鍵校驗域KEYSUM，值域VALSUM。

3.根據權利要求1所述的一種自修復的計數式摘要方法，其特征在于，步驟S2之前，還需要預先選擇K個哈希函數作為哈希函數族，用于所述鍵值對的插入、解碼以及查詢過程。

4.根據權利要求3所述的一種自修復的計數式摘要方法，其特征在于，所述步驟S2包括：

S21，利用所述哈希函數族計算鍵key在K個數組中對應的位置，記為{h_i(key),i∈[1,k]}；

S22，對于第i個數組，選擇第h_i(key)個桶，利用哈希函數族計算鍵key的加權值，記為r_i(key),i∈[1,k]；

S23，記錄鍵值對(key,value)：

(231)

(232)VALSUM＝VALSUM+r_i(key)×value；

其中，(231)表示合并鍵的信息，(232)表示合并值的信息。

5.根據權利要求4所述的一種自修復的計數式摘要方法，其特征在于，執行步驟S2的同時維護一個緩沖stash，記錄C個鍵值對，用于初始化解碼過程。

6.根據權利要求5所述的一種自修復的計數式摘要方法，其特征在于，所述步驟S3包括：

S31，利用所述哈希函數族計算鍵在K個數組中對應的位置，記為{h_i(key),i∈[1,k]}；

S32，對于第i個數組，選擇第h_i(key)個桶，利用哈希函數族計算鍵的加權值，記為r_i(key),i∈[1,k]；

S33，記錄鍵值對(key,value)：

(331)

(332)VALSUM＝VALSUM-r_i(key)×value；

其中，(331)表示合并鍵的信息，(332)表示合并值的信息。

7.根據權利要求6所述的一種自修復的計數式摘要方法，其特征在于，所述步驟S4包括：

S41，初始化一個空的結果緩存集合RepairCache；

S42，遍歷K個數組的每一個桶，如果第i個數組的第j(j∈[1,m])個桶滿足：

h_i(KEYSUM)＝j；

那么將該桶的位置和結果記錄到結果緩存集合RepairCache＝RepairCache∪((i,j):(KEYSUM,r_i(KEYSUM)×VALSUM))

如果集合RepairCache為空，則結束；否則轉入S43；

S43，如果集合RepairCache非空，對于集合RepairCache中的每個元素，假設主鍵為(i,j)，讀取RepairCache主鍵為(i,j)的元素KEYSUM域和VALSUM域，計算鍵KEYSUM域在所有數組的位置：{h_i(KEYSUM),i∈[1,k]}；

對每個桶bucket(i,j)進行更新：

(431)

(432)

S44，返回步驟3。