[發明專利]用于搜索和存儲數據的系統和方法

有效

• 申請號: 200580039086.8
• 申請日: 2005-09-15
• 公開（公告）號: CN101084499A
• 公開（公告）日: 2007-12-05
• 發明（設計）人: 邁克爾·希爾施;海姆·比特內;萊爾·阿羅諾維什;羅恩·阿舍;埃坦·巴什馬特;什穆埃爾·T·克萊因
• 申請（專利權）人: 迪利根特技術公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中原信達知識產權代理有限責任公司
• 代理人: 張煥生;謝麗娜

1.一種在庫數據中識別輸入數據的方法，其中所述庫數據包括庫數據塊，所述輸入數據包括輸入數據塊，并且其中每個庫數據塊具有對應的含有一個或多個庫數據塊區別特征RDC的集，對于每個輸入數據塊，所述方法包括下列步驟：

確定含有一個或多個輸入數據塊區別特征IDC的集；

將所確定的IDC集與一個或多個RDC集進行比較；以及

根據所確定的IDC集與所述一個或多個RDC集的比較來識別與所述輸入數據塊相似的庫數據塊。

2.如權利要求1所述的方法，進一步包括：

通過比較相應各塊的所有數據，確定所述輸入數據塊和所識別的相似庫數據塊之間的一個或多個差異。

3.如權利要求1所述的方法，其中所述輸入數據位于第一位置，所述庫數據位于遠程位置，該方法進一步包括：

在所述第一位置確定所述IDC集；

將所述確定的IDC集從所述第一位置發送到所述遠程位置；以及

在所述遠程位置將所述確定的IDC集與所述一個或多個RDC集進行比較。

4.如權利要求3所述的方法，進一步包括：

在不需要把全部所述輸入數據塊發送到所述遠程位置且不需要把全部所述識別的相似庫數據塊發送到所述第一位置的情況下，確定所述輸入數據塊和所述識別的相似庫數據塊之間的一個或多個差異。

5.如權利要求4所述的方法，進一步包括：

用所述一個或多個確定的差異更新所述遠程位置。

6.如權利要求5所述的方法，其中：

所述第一位置是第一計算機，所述遠程位置是與所述第一計算機不同的遠程計算機，所述第一計算機和遠程計算機彼此網絡通信；以及

所述庫數據存儲在通過所述遠程計算機訪問的數據庫內。

7.如權利要求1所述的方法，其中識別IDC集與RDC集的相似性是相似性閥值的函數。

8.如權利要求7所述的方法，其中當在RDC集中找到所述IDC集中的預定數量的所述區別特征時，則滿足所述相似性閥值。

9.如權利要求8所述的方法，其中確定區別特征集包括：

在相應數據塊內識別一個或多個數據部分；以及

計算相應數據塊的一個或多個數據部分的每個的數學哈希值。

10.如權利要求9所述的方法，進一步包括：

確定某個集當中的k個最大數學哈希值，k是預定的數；

對所述k個最大哈希值的每個識別相應數據部分；以及

確定區別特征集是與每個所述k個最大數學哈希值所對應的每個數據部分相關的順序下一個數據部分。

11.如權利要求2所述的方法，進一步包括在庫中存儲所述確定的差異。

12.如權利要求11所述的方法，其中確定一個或多個差異至少包括：確定二進制差異；以及按字節分解。

13.如權利要求1所述的方法，其中所述區別特征由下列中的一個確定：哈希函數；滾動哈希函數；模數哈希函數。

14.如權利要求1所述的方法，其中至少以下列一種方式將所述RDC集存儲在索引中：二杈樹；B樹；排序表；以及哈希表。

15.如權利要求1所述的方法，其中每個所述庫數據塊和所述輸入數據塊包括多個種子，每個種子是基本元素的連續的序列并具有相同的種子大小；并且其中所述區別特征是相應塊的各種子的選定的子集的哈希值。

16.如權利要求15所述的方法，其中所述種子包括重疊的種子。

17.如權利要求1所述的方法，其中所述方法至少用于下列目的中的一個：數據分解；以及數據備份。

18.如權利要求1所述的方法，其中所述確定相似庫塊的步驟所花的時間與所述庫的大小無關，并與所述輸入數據的大小成線性。