[發明專利]一種高效去重的輕量級在線文件存儲方法及裝置

有效

• 申請號: 202011128003.5
• 申請日: 2020-10-21
• 公開（公告）號: CN111966649B
• 公開（公告）日: 2021-01-01
• 發明（設計）人: 郭得科;羅來龍;程葛瑤;夏俊旭;袁昊;武睿
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/174
• 分類號: G06F16/174;G06F16/182
• 代理公司: 北京風雅頌專利代理有限公司 11403
• 代理人: 曾志鵬

1.一種高效去重的輕量級在線文件存儲方法，其特征在于，包括：

將待存儲文件劃分為至少一個文件塊，計算各文件塊的哈希值，生成表示待存儲文件的基于布隆過濾器的哈希值；

基于至少一個待存儲文件的基于布隆過濾器的哈希值，進行位置敏感哈希算法處理，生成表示至少一個待存儲文件的表空間；其中，所述位置敏感哈希算法的哈希表中包括個哈希函數，所述哈希表中的哈希函數表示為：

（1）

其中，c為待存儲文件的基于布隆過濾器的哈希值，是遵循柯西分布的d維隨機向量，b是在區間內均勻選取的實數，其中是預設值；

將所述待存儲文件對應為投影點映射于所述表空間，所述投影點表示為，所述投影點服從的分布，服從柯西分布，其中，，對于n個文件，其數據向量表示為；

利用個哈希函數對文件的基于布隆過濾器的哈希值進行處理后，得到維度為的數據向量，表示為：

（2）

所述投影點按照公式（4）所示概率分布函數進行分布：

（4）

其中，i為整數，x是投影點的投影位置；

所述投影點的累積分布函數為:

（5）

將所述表空間劃分為至少一個桶區域，各桶區域內包括具有一定相似度的文件，根據各服務器的當前空閑存儲容量，將各桶區域內的文件存儲于容量匹配的服務器。

2.根據權利要求1所述的方法，其特征在于， 還包括：

對于所述服務器中存儲的具有一定相似度的文件，刪除重復的冗余數據。

3.根據權利要求1所述的方法，其特征在于，還包括：

當所述待存儲文件的數量到達預定數量時，更新所述表空間。

4.根據權利要求1所述的方法，其特征在于，根據所述表空間中投影點的概率分布函數和累計分布函數，將所述表空間劃分為與所述服務器的數量一致的桶區域。

5.根據權利要求4所述的方法，其特征在于，第j個桶區域的投影位置為：

（9）

其中，第j個服務器的當前空閑存儲容量為，為服務器的數量趨于無窮大時，所有文件對應的投影點的投影位置的均值的絕對值，為第j個桶區域內所有投影點的投影位置均值的絕對值，

（6）。

6.根據權利要求1所述的方法，其特征在于，所述待存儲文件順序存儲于服務器，所述方法的時間復雜度為，其中，為布隆過濾器的哈希函數的數量， 為位置敏感哈希算法的哈希函數的數量，布隆過濾器的長度，為文件塊的數量。