[發(fā)明專利]經(jīng)由關(guān)聯(lián)相似性搜索的數(shù)據(jù)去重

在審

• 申請?zhí)枺?/td>: 202010800152.5
• 申請日: 2020-08-11
• 公開（公告）號: CN112395275A
• 公開（公告）日: 2021-02-23
• 發(fā)明（設(shè)計）人: A·奧凱里博;D·伊蘭;E·埃爾曼;E·埃雷茲
• 申請（專利權(quán)）人: GSI科技公司
• 主分類號: G06F16/215
• 分類號: G06F16/215;G06F16/22;G06F16/23;G06F16/245;G06F16/28
• 代理公司: 永新專利商標代理有限公司 72002
• 代理人: 劉瑜

1.一種去重系統(tǒng)，包括：

相似性搜索器，其用于在存儲多個指紋的指紋數(shù)據(jù)庫中搜索類似于輸入塊的新指紋的相似指紋；

差異計算器，其用于如果找到所述相似指紋，則計算在所述輸入塊與和所述相似指紋相關(guān)聯(lián)的相似塊之間的差異塊；以及

存儲管理器，其用于用所述新指紋來更新所述指紋數(shù)據(jù)庫，并且如果所述差異塊不為空，則用于將所述差異塊存儲在存儲單元中。

2.根據(jù)權(quán)利要求1所述的系統(tǒng)，其中，如果未找到相似指紋，則所述存儲管理器用于存儲所述輸入塊。

3.根據(jù)權(quán)利要求1所述的系統(tǒng)，其中，所述存儲管理器用于將指紋存儲在關(guān)聯(lián)存儲器設(shè)備的列中，并且其中，所述相似性搜索器在所述關(guān)聯(lián)存儲器設(shè)備內(nèi)部執(zhí)行所述搜索。

4.根據(jù)權(quán)利要求1所述的系統(tǒng)，還包括：

指紋創(chuàng)建器，其用于使用局部敏感散列(LSH)算法創(chuàng)建所述新指紋，以為略微不同的輸入塊創(chuàng)建略微不同的新指紋。

5.根據(jù)權(quán)利要求1所述的系統(tǒng)，其中，所述指紋數(shù)據(jù)庫以多級別結(jié)構(gòu)布置，其中，較高級別包括到較低級別中的集群的質(zhì)心，并且最低級別包括塊的指紋，所述質(zhì)心是根據(jù)所述指紋計算出的。

6.根據(jù)權(quán)利要求5所述的系統(tǒng)，其中，所述存儲管理器用于將最高級別的指紋存儲在關(guān)聯(lián)存儲器設(shè)備的列中，并且其中，在所述最高級別中的所述搜索是在所述關(guān)聯(lián)存儲器設(shè)備內(nèi)部執(zhí)行的，并且在較低級別中的所述搜索是在CPU中執(zhí)行的。

7.根據(jù)權(quán)利要求5所述的系統(tǒng)，還包括：

塊拆分器，其用于將所述輸入塊拆分為較小的子塊；

抗沖突指紋創(chuàng)建器，其用于針對所述子塊中的每一個創(chuàng)建抗沖突指紋；

精確搜索器，其用于在所述指紋數(shù)據(jù)庫中搜索與所述抗沖突指紋匹配的相同指紋；

其中，所述存儲管理器用于用所述抗沖突指紋來更新所述指紋數(shù)據(jù)庫，并且用于存儲未找到相同指紋的子塊。

8.一種用于去重的方法，包括：

在存儲多個指紋的指紋數(shù)據(jù)庫中搜索類似于輸入塊的新指紋的相似指紋；

如果找到所述相似指紋，則計算在所述輸入塊與和所述相似指紋相關(guān)聯(lián)的相似塊之間的差異塊；

用所述新指紋來更新所述指紋數(shù)據(jù)庫；以及

如果所述差異塊不為空，則將所述差異塊存儲在存儲單元中。

9.根據(jù)權(quán)利要求8所述的方法，其中，存儲的步驟還包括：如果未找到相似指紋，則存儲所述輸入塊。

10.根據(jù)權(quán)利要求8所述的方法，還包括將所述指紋加載到關(guān)聯(lián)存儲器設(shè)備的列中，并且其中，所述搜索是在所述關(guān)聯(lián)存儲器設(shè)備內(nèi)部執(zhí)行的。

11.根據(jù)權(quán)利要求8所述的方法，還包括：

使用局部敏感散列(LSH)算法創(chuàng)建所述新指紋，以為略微不同的輸入塊創(chuàng)建略微不同的新指紋。

12.根據(jù)權(quán)利要求10所述的方法，其中，所述指紋數(shù)據(jù)庫是以多級別結(jié)構(gòu)布置的層級數(shù)據(jù)庫，其中，較高級別包括到較低級別中的集群的質(zhì)心，并且最低級別包括塊的指紋，所述質(zhì)心是根據(jù)所述指紋計算出的。

13.根據(jù)權(quán)利要求12所述的方法，其中，所述加載包括將最高級別的指紋加載到關(guān)聯(lián)存儲器的列中，并且其中，所述搜索包括由關(guān)聯(lián)存儲器設(shè)備在所述最高級別中執(zhí)行搜索，以及由CPU在較低級別中執(zhí)行搜索。

14.根據(jù)權(quán)利要求13所述的方法，還包括：

將所述輸入塊拆分為較小的子塊；

針對所述子塊中的每一個創(chuàng)建抗沖突指紋；

執(zhí)行精確搜索以在指紋數(shù)據(jù)庫中查找與所述抗沖突指紋中的每一個的精確匹配；

用所述抗沖突指紋來更新所述指紋數(shù)據(jù)庫；以及

存儲未找到相同指紋的子塊。

15.根據(jù)權(quán)利要求8所述的方法，還包括：

在所述輸入塊的指紋與使用抗沖突算法創(chuàng)建的指紋的數(shù)據(jù)庫之間執(zhí)行精確搜索；以及

如果未找到精確匹配，則執(zhí)行所述搜索。