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

在審

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

本發明公開一種自修復的計數式摘要方法，包括以下步驟：構建自修復的計數式摘要結構；執行鍵值對插入操作：將一個鍵值對摻入到所述計數式摘要結構中；執行鍵值對刪除操作：利用所述鍵校驗域信息計算一個鍵對應的桶的集合，僅保留一個桶的值并從其他桶中刪除該鍵值對；執行鍵值對解碼操作：從所述計數式摘要結構中發現并修復多個鍵值對共用的桶；執行鍵值對查詢操作：查詢一個鍵值對是否記錄到所述計數式摘要結構中。本發明通過引入修復操作到計數式摘要數據結構，能有效降低甚至消除原有的查詢誤差，提升計數式摘要的信息記錄精度和查詢的有效性，并且保持常數級的插入和查詢操作，確保判斷的準確性。

技術領域

本發明涉及網絡通信技術領域，具體是一種自修復的計數式摘要方法。

背景技術

計數式摘要(count-sketch)是數據管理領域常用的精簡數據結構。記錄數據流的鍵-值(key-value)對，具有廣泛的抽象表示能力，得到了廣泛的應用。

常見的計數式摘要由一組數組構成，每個數組包含相同數目的桶(“桶”為邏輯概念，用于指代數組的一個位置)，每個桶用于記錄插入到該位置的鍵對應的值。當需要插入一個鍵值對(key,value)時，首先通過哈希函數從每個數組中均勻隨機選擇一個桶，然后通過哈希函數選擇+1或者-1對值進行加權，最后將值插入到選中的桶中。在查詢一個鍵對應的值時，首先利用相同的哈希函數從每個數組計算桶的位置，其次讀取每個桶的值，最終選取所有桶值的加權中間值作為該鍵對應的值返回。計數式摘要具有常數時間的維護和查詢開銷。

計數式摘要具有查詢誤差，如果多個鍵插入到相同的桶中，那么這個桶記錄各個鍵對應值的加權代數和，并不嚴格對應一個鍵的原始值。查詢誤差嚴重降低了計數式摘要的查詢有效性，應用查詢結果可能造成偏差，造成判斷錯誤。因此，有必要設計一種自修復的計數式摘要方法。

發明內容

本發明針對現有的計數式摘要存在查詢誤差的不足，提出一種自修復的計數式摘要方法，實現查詢誤差的降低甚至消除的目的。

為了解決上述技術問題，本發明是通過以下技術方案實現的：一種自修復的計數式摘要方法，包括以下步驟，

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

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

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

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

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

進一步的，步驟S1中，每個所述計數式摘要結構包括K個數組，每個所述數組包括m個桶，其中參數K和m是系統預先設置的參數，每個所述桶至少包括鍵校驗域KEYSUM，值域VALSUM。

進一步的，步驟S2之前，還需要預先選擇K個哈希函數作為哈希函數族，用于所述鍵值對的插入、解碼以及查詢過程。

進一步的，所述步驟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)