(57)【要約】【課題】  本発明により、リモート差分圧縮のため候補オブジェクトを見つける機能を提供すること。【解決手段】  オブジェクトは、必要なデータ転送が最小限に抑えられるようにリモート差分圧縮（ＲＤＣ）技術を使用して２つまたはそれ以上のコンピューティング装置間で更新される。受信者が送信者から転送される必要のあるオブジェクトに類似しているオブジェクトの集合を特定できるように、アルゴリズムにより効率を高める。この類似オブジェクトの集合が見つかった後、受信者は、ＲＤＣアルゴリズムの実行時にそれらのオブジェクトからのチャンクを再利用することができる。【選択図】  図１２
2006092558.tif 000002
【特許請求の範囲】
【請求項１】
リモート差分圧縮のためオブジェクトを識別する方法であって、
オブジェクトの特性を計算するステップと、
前記特性を使用して前記オブジェクトに少なくともいくらかは類似している候補オブジェクトを識別するステップと、
前記識別された候補オブジェクトから最終オブジェクトを選択するステップとを備えたことを特徴とする方法。
【請求項２】
前記オブジェクトの特性を計算するステップは、
前記オブジェクトを複数のチャンクに分割するステップと、
前記オブジェクトチャンクのそれぞれについてシグネチャを計算するステップと、
前記シグネチャを複数のシングルにグループ分けするステップと、
前記シングルのそれぞれについて少なくとも１つのシングルシグネチャを計算するステップと、
前記シングルシグネチャを複数のイメージ集合にマッピングするステップと、
前記イメージ集合から事前特性を計算するステップと、
前記事前特性を使用して特性を計算するステップであって、前記特性は、前記事前特性に比べてサイズが小さい特性を計算するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
リモート差分圧縮法を実行する際に候補オブジェクトの前記集合を使用するステップをさらに備えたことを特徴とする請求項２に記載の方法。
【請求項４】
それぞれの位置を中心とする小さなウィンドウ内の前記バイトの値を使用することにより前記オブジェクトのそれぞれのバイト位置でフィンガープリントを生成するステップをさらに備えたことを特徴とする請求項２に記載の方法。
【請求項５】
前記オブジェクトを複数のチャンクに分割するステップは、前記フィンガープリントに基づき前記オブジェクトをチャンキングするステップを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記シグネチャを複数のシングルにグループ分けするステップは、ｑ個の連続するシグネチャを連結して１つのシングルを形成するステップからなることを特徴とする請求項２に記載の方法。
【請求項７】
前記シングルをイメージ集合にマッピングするステップは、ｔ個のハッシュ関数をそれぞれのシングルに次々に適用し、それによってｔ個のイメージ集合を作成するステップを含むことを特徴とする請求項２に記載の方法。
【請求項８】
前記イメージ集合から前記事前特性を計算するステップは、それぞれのイメージ集合から前記計算されたハッシュ値の１つを選択する決定論的数学関数を適用するステップを含むことを特徴とする請求項２に記載の方法。
【請求項９】
前記決定論的数学関数は、最大値関数と最小値関数とから選択されることを特徴とする請求項８に記載の方法。
【請求項１０】
前記事前特性を使用して前記特性を計算するステップは、各前記特性よりも小さい所定のビット数を有する特性を作成する前記事前特性の各々に決定論的関数を適用するステップを含むことを特徴とする請求項７に記載の方法。
【請求項１１】
前記決定論的関数は、各事前特性からｂ個のビットからなる指定集合を選択するステップを含むことを特徴とする請求項９に記載の方法。
【請求項１２】
前記特性を使用して前記オブジェクトに少なくともいくらかは類似している候補オブジェクトを識別するステップは、前記２つのオブジェクトの間で一致する特性の前記個数を計算するステップを含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記特性類似度の前記値に誘導されるｋ個の最も良く一致するオブジェクトを選択するステップをさらに備えたことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記リモート差分圧縮法は、
ｋ個の最も良く一致するローカルオブジェクトを複数のローカルチャンクに分割するステップと、
それぞれのローカルチャンクについてローカルシグネチャを計算するステップと、
リモート装置から受信されたリモートシグネチャと前記ローカルシグネチャとを比較するステップと、
前記シグネチャ比較により前記ローカルチャンクが再利用可能であることがわかった場合に、ローカルチャンクを再利用して、前記リモートオブジェクトを再構成するステップとを含むことを特徴とする請求項３に記載の方法。
【請求項１５】
前記特性をコンパクトに符号化することにより装置の揮発性メモリ内に前記特性を格納するステップをさらに備えたことを特徴とする請求項２に記載の方法。
【請求項１６】
前記特性の選択された部分集合のみを装置の揮発性メモリ内に格納することをさらに備えたことを特徴とする請求項１５に記載の方法。
【請求項１７】
装置の永続的メモリ内に前記特性を格納するステップをさらに備えたことを特徴とする請求項２に記載の方法。
【請求項１８】
前記特性の選択された部分集合のみを装置の永続的メモリ内に格納するステップをさらに備えたことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記オブジェクトＩＤをコンパクトに表すオブジェクトマップを装置上に作成し、それぞれのコンパクトな表現が所定のサイズを使用して表されるステップと、
特性番号および特性値から特性集合にマッピングする少なくとも２レベルインデックスを形成する特性テーブルを作成するステップと
をさらに備えたことを特徴とする請求項１５に記載の方法。
【請求項２０】
前記オブジェクトマップが疎であると判定された場合に前記オブジェクトマップを再構築するステップをさらに備えたことを特徴とする請求項１９に記載の方法。
【請求項２１】
バケット（ＯＢx．．．．ＯＢt）を作成して、リモートオブジェクトＯBの少なくともｘ個の特性と一致するローカルオブジェクトを格納するステップと、
オブジェクトＯBのｔ個の特性に対応するｔ個のＴｒａｉｔＳｅｔｓ（ＴＳ1．．．ＴＳt）を選択するステップと、
インデックス（Ｐ1．．．Ｐt）を初期化して、ＴＳk［Ｐk］がＰkによって指されている前記オブジェクトＩＤの表記である場合に、それぞれ、ＴＳ1．．．ＴＳtの第１の要素を指すようにするステップと、
Ｐ1．．．ＰtのそれぞれがそのＴｒａｉｔＳｅｔ配列ＴＳ1．．．ＴＳtの最後の要素を越えてそれぞれ指すと判定された場合に所望の数の類似のオブジェクトを選択するステップと、
前記最小オブジェクトＩＤを指すインデックスの集合である、ＭｉｎＰ集合を選択するステップと、
ＭｉｎＩＤをＭｉｎＰ内のすべてのインデックスによって指される最小オブジェクトＩＤとして設定するステップと、
一致する特性の数に対応する、ｋ＝｜ＭｉｎＰ｜の場合に、ｋ≧ｘおよびＯｂｊｅｃｔＭａｐ（ＭｉｎＰ）はデッドエントリでないと判定された場合にＭｉｎＩＤをＯＢkに付加するステップと、
ＭｉｎＰ内のすべてのインデックスＰkをそれぞれのＴｒａｉｔＳｅｔ配列ＴＳk内の次のオブジェクトＩＤに進めるステップと
を含む類似の特性を持つオブジェクトを検出するステップをさらに備えたことを特徴とする請求項１９に記載の方法。
【請求項２２】
前記所望の数の類似のオブジェクトを選択するステップは、まずＯＢtから複数のオブジェクトを選択し、そして、ｔをデクリメントし、ＯＢtから選択するステップを、前記所望の数の類似のオブジェクトが選択されるまで繰り返すステップを含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
前記所望の数の類似のオブジェクトを選択するステップは、まずＯＢtから複数のオブジェクトを選択し、そして、ｔをデクリメントし、ＯＢtから選択するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項２４】
リモート差分圧縮のためオブジェクトを識別するコンピュータ実行可能命令を格納するコンピュータ読み取り可能媒体であって、
オブジェクトを複数のチャンクに分割するステップと、
前記オブジェクトチャンクのそれぞれについてシグネチャを計算するステップと、
前記シグネチャを複数のシングルにグループ分けするステップと、
前記シングルのそれぞれについて少なくとも１つのシングルシグネチャを計算するステップと、
前記シングルシグネチャを複数のイメージ集合にマッピングするステップと、
前記イメージ集合から事前特性を計算するステップと、
前記事前特性を使用して前記特性を計算するステップであって、前記特性は、前記特性を使用して、前記オブジェクトに少なくともいくらかは類似している候補オブジェクトを識別する前記事前特性と比較してサイズが小さい前記特性を計算するステップと、
前記識別された候補オブジェクトから最終オブジェクトを選択するステップと
を備えたことを特徴とするコンピュータ読み取り可能媒体。
【請求項２５】
前記オブジェクトを複数のチャンクに分割するステップは、それぞれの位置を中心とする小さなウィンドウ内の前記バイトの前記値を使用することにより前記オブジェクトのそれぞれのバイト位置でフィンガープリントを生成し、前記フィンガープリントに基づき前記オブジェクトをチャンキングするステップを含むことを特徴とする請求項２４に記載のコンピュータ読み取り可能媒体。
【請求項２６】
前記シグネチャを複数のシングルにグループ分けするステップは、シグネチャを連結して１つのシングルを形成するステップからなることを特徴とする請求項２４に記載のコンピュータ読み取り可能媒体。
【請求項２７】
前記前記シングルを複数のイメージ集合にマッピングするステップは、少なくとも１つのハッシュ関数をそれぞれのシングルに適用するステップを含むことを特徴とする請求項２４に記載のコンピュータ読み取り可能媒体。
【請求項２８】
前記イメージ集合から前記事前特性を計算するステップは、各イメージ集合から前記計算されたハッシュ値のうちの１つを選択する決定論的数学関数を適用するステップであって、前記決定論的数学関数は、最大値関数および最小値関数から選択される決定論的数学関数を適用するステップを含むことを特徴とする請求項２４に記載のコンピュータ読み取り可能媒体。
【請求項２９】
前記事前特性を使用して前記特性を計算するステップは、各前記特性よりも小さい所定のビット数を持つ特性を作成する前記事前特性のそれぞれに決定論的関数を適用するステップを含むことを特徴とする請求項２８に記載のコンピュータ読み取り可能媒体。
【請求項３０】
前記特性を使用して前記オブジェクトに少なくともいくらかは類似している候補オブジェクトを識別するステップは、前記２つのオブジェクトの間で一致する特性の前記個数を計算するステップを含むことを特徴とする請求項２４に記載のコンピュータ読み取り可能媒体。
【請求項３１】
前記オブジェクトＩＤをコンパクトに表すオブジェクトマップを装置上に作成し、各コンパクトな表現が所定のサイズを使用して表されるステップと、
特性番号および特性値から特性集合にマッピングする少なくとも２レベルインデックスを形成する特性テーブルを作成するステップと
をさらに備えたことを特徴とする請求項２４に記載のコンピュータ読み取り可能媒体。
【請求項３２】
前記オブジェクトマップが疎であると判定された場合に前記オブジェクトマップを再構築するステップをさらに備えたことを特徴とする請求項３１に記載のコンピュータ読み取り可能媒体。
【請求項３３】
バケット（ＯＢx．．．．ＯＢt）を作成して、リモートオブジェクトＯBの少なくともｘ個の特性と一致するローカルオブジェクトを格納するステップと、
オブジェクトＯＢのｔ個の特性に対応するｔ個のＴｒａｉｔＳｅｔｓ（ＴＳ1．．．ＴＳt）を選択するステップと、
インデックス（Ｐ1．．．Ｐt）を初期化して、ＴＳk［Ｐk］がＰkによって指されている前記オブジェクトＩＤの表記である場合に、それぞれ、ＴＳ1．．．ＴＳtの第１の要素を指すようにするステップと、
Ｐ1．．．Ｐtの各々がそのＴｒａｉｔＳｅｔ配列ＴＳ1．．．ＴＳtの最後の要素を越えてそれぞれ指すと判定された場合に所望の数の類似のオブジェクトを選択するステップと、
前記最小オブジェクトＩＤを指すインデックスの集合である、ＭｉｎＰ集合を選択するステップと、
ＭｉｎＩＤをＭｉｎＰ内のすべてのインデックスによって指される最小オブジェクトＩＤとして設定するステップと、
一致する特性の数に対応する、ｋ＝｜ＭｉｎＰ｜の場合に、ｋ≧ｘおよびＯｂｊｅｃｔＭａｐ（ＭｉｎＰ）はデッドエントリでないと判定された場合にＭｉｎＩＤをＯＢkに付加するステップと、
ＭｉｎＰ内のすべてのインデックスＰkをそれぞれのＴｒａｉｔＳｅｔ配列ＴＳk内の次のオブジェクトＩＤに進めるステップであって、類似の特性を持つオブジェクトを見つける次のオブジェクトＩＤに進めるステップと
を含む類似の特性を持つオブジェクトを検出するステップをさらに備えたことを特徴とする請求項３１に記載のコンピュータ読み取り可能媒体。
【請求項３４】
リモート装置であって、
オブジェクトＯBの要求を受信するステップと、
オブジェクトＯBの特性の集合をローカル装置に送信するステップと、
オブジェクトＯBを複数のチャンクに分割し、前記チャンクのそれぞれについてシグネチャを計算するステップと、
チャンクシグネチャの前記リストを前記ローカル装置に送信するステップと、
要求時に要求された複数のチャンクを提供するステップとを含むステップを実行するように構成されたリモート装置と、
ローカル装置であって、
前記リモート装置にオブジェクトＯBを要求するステップと、
オブジェクトＯBの特性の前記集合を前記リモート装置から受信するステップと、
オブジェクトＯBの特性の前記集合を使用して、前記ローカル装置にすでに格納されている類似のオブジェクトを識別するステップと、
前記類似のオブジェクトを複数のチャンクに分割するステップと、
前記類似のオブジェクトチャンクの各々についてシグネチャを計算するステップと、
チャンクシグネチャの前記リストを前記リモート装置から受信するステップと、
前記受信されたシグネチャを前記ローカルで計算されたシグネチャと突き合わせて比較するステップと、
前記比較で一致しなかったチャンクを前記リモート装置に要求するステップと、
前記要求されたチャンクを受信するステップと、
前記受信されたチャンクおよび前記類似のオブジェクトから再利用されるチャンクを使用してオブジェクトＯBを再構成するステップとを含むステップを実行するように構成されているローカル装置と
を備えたことを特徴とするリモート差分圧縮のためオブジェクトを識別するシステム。
【請求項３５】
前記ローカル装置は、
前記シグネチャを複数のシングルにグループ分するステップと、
前記シングルの各々について少なくとも１つのシングルシグネチャを計算するステップと、
前記シングルシグネチャを複数のイメージ集合にマッピングするステップと、
前記イメージ集合から事前特性を計算するステップと、
前記事前特性を使用して前記特性を計算するステップであって、前記特性は、前記オブジェクトに少なくともいくらかは類似している候補オブジェクトを識別するために前記特性を使用する前記事前特性と比較してサイズが小さい前記特性を計算するステップとをさらに含み、
前記識別された候補オブジェクトから最終オブジェクトを選択するように構成されることを特徴とする請求項３４に記載のシステム。
【請求項３６】
前記オブジェクトを複数のチャンクに分割するステップは、それぞれの位置を中心とする小さなウィンドウ内の前記バイトの値を使用することにより前記オブジェクトのそれぞれのバイト位置でフィンガープリントを生成し、前記フィンガープリントに基づき前記オブジェクトをチャンキングするステップを含むことを特徴とする請求項３５に記載のシステム。
【請求項３７】
前記シングルを前記ローカル装置上の複数のイメージ集合にマッピングするステップは、少なくとも１つのハッシュ関数をそれぞれのシングルに適用するステップを含むことを特徴とする請求項３６に記載のシステム。
【請求項３８】
前記イメージ集合から前記事前特性を計算するステップは、それぞれのイメージ集合から前記計算されたハッシュ値のうちの１つを選択する決定論的数学関数を適用するステップを含み、前記決定論的数学関数は、最大値関数および最小値関数から選択されることを特徴とする請求項３７に記載のシステム。
【請求項３９】
前記事前特性を使用して前記特性を計算するステップは、それぞれ前記特性よりも小さい所定のビット数を持つ特性を作成する前記事前特性の各々に決定論的関数を適用するステップを含むことを特徴とする請求項３８に記載のシステム。
【請求項４０】
前記特性を使用して前記オブジェクトに少なくともいくらかは類似している候補オブジェクトを識別するステップは、前記２つのオブジェクトの間で一致する特性の前記個数を計算するステップを含むことを特徴とする請求項３６に記載のシステム。
【請求項４１】
前記ローカル装置は、
前記オブジェクトＩＤをコンパクトに表すオブジェクトマップを前記ローカル装置上に作成し、それぞれのコンパクトな表現が所定のサイズを使用して表され、
特性番号および特性値から特性集合にマッピングする少なくとも２レベルインデックスを形成する特性テーブルを作成するようにさらに構成されることを特徴とする請求項３６にシステム。
【請求項４２】
前記オブジェクトマップが疎であると判定された場合に前記オブジェクトマップを再構築するステップをさらに備えたことを特徴とする請求項４１に記載のシステム。
【請求項４３】
バケット（ＯＢx．．．．ＯＢt）を作成して、リモートオブジェクトＯBの少なくともｘ個の特性と一致するローカルオブジェクトを格納するステップと、
オブジェクトＯＢのｔ個の特性に対応するｔ個のＴｒａｉｔＳｅｔｓ（ＴＳ1．．．ＴＳt）を選択するステップと、
インデックス（Ｐ1．．．Ｐt）を初期化して、ＴＳk［Ｐk］がＰｋによって指されている前記オブジェクトＩＤの表記である場合に、それぞれ、ＴＳ1．．．ＴＳtの第１の要素を指すようにするステップと、
Ｐ1．．．ＰtのそれぞれがそのＴｒａｉｔＳｅｔ配列ＴＳ1．．．ＴＳtの最後の要素を越えてそれぞれ指すと判定された場合に所望の数の類似のオブジェクトを選択するステップと、
前記最小オブジェクトＩＤを指すインデックスの集合である、ＭｉｎＰ集合を選択するステップと、
ＭｉｎＩＤをＭｉｎＰ内のすべてのインデックスによって指される最小オブジェクトＩＤとして設定するステップと、
一致する特性の数に対応する、ｋ＝｜ＭｉｎＰ｜の場合に、ｋ≧ｘおよびＯｂｊｅｃｔＭａｐ（ＭｉｎＰ）はデッドエントリでないと判定された場合にＭｉｎＩＤをＯＢkに付加するステップと、
ＭｉｎＰ内のすべてのインデックスＰkをそれぞれのＴｒａｉｔＳｅｔ配列ＴＳk内の次のオブジェクトＩＤに進めるステップと
を含む類似の特性を持つオブジェクトを検出するステップをさらに備えたことを特徴とする請求項４１に記載のシステム。
【請求項４４】
前記所望の数の類似のオブジェクトを選択するステップは、まずＯＢtから複数のオブジェクトを選択し、そして、ｔをデクリメントし、ＯＢtから選択することを、前記所望の数の類似のオブジェクトが選択されるまで繰り返すステップを含むことを特徴とする請求項４３に記載のシステム。
【請求項４５】
前記所望の数の類似のオブジェクトを選択するステップは、まずＯＢtから複数のオブジェクトを選択し、そして、ｔをデクリメントし、ＯＢtから選択するステップを含むことを特徴とする請求項４３に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リモート差分圧縮の候補オブジェクトを見つけるための方法およびシステムに関する。
【背景技術】
【０００２】
イントラネット、エクストラネット、およびインターネットなどのネットワークの急増により、広域ネットワーク間で情報を共有するユーザ数の増大をもたらした。最大データ転送速度は、伝送媒体に関連する帯域幅とともに他のインフラ関係の制限に基づいてそれぞれの物理ネットワークに関連付けられる。ネットワーク帯域幅が制限されている結果として、ユーザは、ネットワーク間で大量のデータの取り出しおよび転送を行っているときに長い遅延を経験することがある。
【０００３】
データ圧縮技術は、帯域幅が限られているネットワーク間で大量のデータを転送する手段として広く受け入れられている。データ圧縮は、一般に、可逆圧縮または非可逆圧縮のいずれかで特徴付けられる。可逆圧縮は、圧縮解除変換を適用することによりデータセットの正確な再現を取り出せるようにデータセットを変換することを伴う。可逆圧縮は、正確なレプリカが必要とされる場合に、データをコンパクトにする場合に使用されることが最も多い。
【０００４】
データオブジェクトの受信者がそのオブジェクトの旧バージョンつまり古いバージョンをすでに持っている場合、リモート差分圧縮（Ｒｅｍｏｔｅ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｃｏｍｐｒｅｓｓｉｏｎ）（ＲＤＣ）と呼ばれる可逆圧縮方式を使用すると、オブジェクトの新バージョンと旧バージョンとの差分を決定し、転送するだけでよい。ＲＤＣ転送では新バージョンと旧バージョンとの観察された差分を伝達するだけでよいので（例えば、ファイルの場合には、ファイル変更または最終アクセス日時、ファイル属性、またはファイル内容に対する小さな変更）、転送されるデータの総量を大幅に減らせる。ＲＤＣを他の可逆圧縮アルゴリズムと併用することにより、ネットワークトラフィックをさらに低減することができる。ＲＤＣの利点は、大きなオブジェクトをコンピューティング装置間で頻繁にやり取りする必要があり、それらのオブジェクトの古いコピーを保持することが困難であるか、または実現不可能であり、ローカル差分アルゴリズムを使用できない場合に最も顕著である。
【発明の開示】
【課題を解決するための手段】
【０００５】
オブジェクトは、必要なデータ転送が最小限に抑えられるようにリモート差分圧縮（ＲＤＣ）技術を使用して２つまたはそれ以上のコンピューティング装置間で更新される。一態様では、送信者が少量のメタデータを受信者に伝達し、受信者がこのメタデータを使用して送信者から転送される必要があるオブジェクトに類似のオブジェクトの集合を特定できるようにすることにより効率を高めるアルゴルズムを実現する。この類似オブジェクトの集合が見つかった後、受信者は、ＲＤＣアルゴリズムの実行時に必要に応じてそれらのオブジェクトの一部を再利用することができる。
【０００６】
本発明およびその改良のより詳しい評価は、後の方で簡単に概要が説明されている付属の図面、本発明の実施例の以下の詳細な説明、および添付の特許請求の範囲を参照することにより得られる。
【０００７】
本発明の限定されない、包括的ではない実施形態は、以下の図面を参照しつつ説明される。
【発明を実施するための最良の形態】
【０００８】
本発明の様々な実施形態は、複数の図面にわたって類似の参照番号は類似の部分およびアセンブリを表す図面を参照しつつ詳しく説明される。様々な実施形態を参照しても、本発明の範囲を限定することにはならず、本発明は添付の特許請求の範囲の範囲によってのみ限定される。さらに、本明細書で述べられている実施例は、限定することを意図しておらず、請求されている発明の多くの可能な実施形態の一部を述べているにすぎない。
【０００９】
本発明は、１つまたは複数の通常関連付けられているオブジェクトが格納されるローカルおよびリモートのコンピューティング装置（または、簡単に「装置」と呼ぶ）の文脈において説明される。「ローカル」および「リモート」という用語は、この方法の１つの状況を指す。しかし、同じ装置で、異なる状況において「ローカル」および「リモート」の両方の役割を果たすこともできる。リモート差分圧縮（ＲＤＣ）法は、帯域幅が制限されているネットワーク上で通常関連付けられているオブジェクトを効率よく更新するために使用される。オブジェクトの新しいコピーを有する装置が同じオブジェクトの古いコピー、または類似のオブジェクトの古いコピーを有する装置を更新する必要がある場合、ＲＤＣ法を使用して、ネットワーク上でオブジェクト間の差分の送信のみを行う。説明されているＲＤＣ法の実施例では、（１）ＲＤＣメタデータの伝送を行う再帰的方式を使用して、大きなオブジェクトの場合に転送されるメタデータの量を低減し、（２）ローカル最大ベースのチャンキング法を使用して、帯域幅利用が最小になるようにオブジェクト差分抽出に関連する精度を高める。説明されているＲＤＣ法を利用するアプリケーションのいくつかの例として、ピアツーピアレプリケーションサービス、ＳＭＢなどのファイル転送プロトコル、大きなイメージを転送する仮想サーバ、電子メールサーバ、携帯電話およびＰＤＡ同期、データベースサーバレプリケーションがある。
【００１０】
（動作環境）
図１に、本発明の動作環境例を示す。図に例示されているように、装置はネットワーク上で通信を行うように構成されている。これらの装置は、汎用コンピューティング装置、専用コンピューティング装置、またはネットワークに接続される他の適切な装置とすることができる。ネットワーク１０２は、限定はしないが、直接配線接続（例えば、パラレルポート、シリアルポート、ＵＳＢ、ＩＥＥＥ  １３９４など）、無線接続（例えば、ＩＲポート、Ｂｌｕｅｔｏｏｔｈポートなど）、有線ネットワーク、無線ネットワーク、ローカルエリアネットワーク、ワイドエリアネットワーク、ウルトラワイドエリアネットワーク、インターネット、イントラネット、およびエクストラネットを含む、接続トポロジに対応しうる。
【００１１】
装置Ａ（１００）と装置Ｂ（１０１）との間のやり取りの例では、異なるバージョンのオブジェクトつまり１００上のオブジェクトＯAおよび１０１上のオブジェクトＯBがローカルの２つの装置に格納される。ある時点において、装置Ａ（１００）は、オブジェクトＯAのコピーを装置Ｂ（１０１）上に格納されているコピー（オブジェクトＯB）で更新することを決定し、ＲＤＣ法を開始する要求を装置Ｂ（１０１）に送信する。他の実施形態では、ＲＤＣ法は、装置Ｂ（１０１）により開始することも可能である。
【００１２】
装置Ａ（１００）および装置Ｂ（１０１）は、両方とも、ローカルに格納されたオブジェクトを処理し、関連付けられたデータをデータ依存の方法で可変個数のチャンクに分割する（例えば、オブジェクトＯBに対してはチャンク１〜ｎ、オブジェクトＯAに対してはチャンク１〜ｋ）。複数のチャンクに対する強いハッシュ（ＳＨＡ）などのシグネチャの集合は、両方の装置によりローカルに計算される。装置は両方とも、シグネチャの別個のリストをコンパイルする。ＲＤＣ法の次のステップで、装置Ｂ（１０１）は、ネットワーク１０２を介してシグネチャおよびチャンク長１〜ｎの計算されたリストを装置Ａ（１００）に送信する。装置Ａ（１００）は、各受信したシグネチャを装置Ａ側の生成されたシグネチャリスト１〜ｋと比較する。シグネチャリストの不一致は、オブジェクト内に是正を必要とする１つまたは複数の相違点のあることを示す。装置Ａ（１００）は、装置Ｂ（１０１）がシグネチャリスト内の不一致により識別されたチャンクを送信するように要求を送信する。装置Ｂ（１０１）は、その後、要求されたチャンクを圧縮して送信し、その後、それらのチャンクは、受信および圧縮解除の実行後、装置Ａ（１００）により再び組み立てられる。装置Ａ（１００）は、受信チャンクをその装置の一致する自チャンクと合わせて再び組み立て、オブジェクトＯBのローカルコピーを得る。
【００１３】
（コンピューティング装置の実施例）
図２に、本発明により用意されるコンピューティング装置の一実施例を示す。基本的な構成では、コンピューティング装置２００は、通常、少なくとも１つの演算処理装置（２０２）およびシステムメモリ（２０４）を備える。コンピューティング装置の正確な構成と種類に応じて、システムメモリ２０４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またはこれら２つの何らかの組合せとすることができる。システムメモリ２０４は、通常、オペレーティングシステム（２０５）、１つまたは複数のプログラムモジュール（２０６）を格納し、プログラムデータ（２０７）を含む場合もある。この基本構成は、図２において点線２０８内のコンポーネントにより示されている。
【００１４】
コンピューティング装置２００は、さらに特徴または機能を追加することもできる。例えば、コンピューティング装置２００は、磁気ディスク、光ディスク、またはテープなどの追加データ記憶装置（取り外し可能および／または固定）を備えることもできる。このような追加記憶装置は、図２では、取り外し可能記憶装置２０９および固定の記憶装置２１０により例示されている。コンピュータ記憶媒体は、コンピュータ読み取り可能命令、データ構造体、プログラムモジュール、またはその他のデータなどの情報を格納する方法または技術で実装される揮発性および不揮発性、取り外し可能および固定の媒体を含むことができる。システムメモリ２０４、取り外し可能記憶装置２０９、および固定の記憶装置２１０は、すべてコンピュータ記憶媒体の実施例である。コンピュータ記憶媒体としては、限定はしないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）またはその他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置またはその他の磁気記憶装置、または所望の情報を格納するために使用することができコンピューティング装置２００によりアクセスできるその他の媒体がある。このような任意のコンピュータ記憶媒体を装置２００の一部とすることができる。さらにコンピューティング装置２００は、キーボード、マウス、ペン、音声入力装置、タッチ入力装置などの（複数の）入力装置２１２を備えることもできる。ディスプレイ、スピーカ、プリンタなどの（複数の）出力装置２１４を備えることもできる。これらの装置はすべて、当業で知られているため、本明細書でさらに詳しい説明をする必要はない。
【００１５】
また、コンピューティング装置２００は、装置がネットワークなどを経由して他のコンピューティング装置２１８と通信するために使用する（複数の）通信接続２１６も含むことができる。（複数の）通信接続２１６は、通信媒体の一実施例である。通信媒体は、通常、コンピュータ読み取り可能命令、データ構造体、プログラムモジュール、または搬送波もしくはその他のトランスポートメカニズムなどの変調データ信号によるその他のデータを具現するものであり、任意の情報配信媒体を含む。「変調データ信号」という用語は、信号内に情報を符号化するような方法で特性のうちの１つまたは複数が設定または変更された信号を意味する。例えば、限定はしないが、通信媒体としては、有線ネットワークまたは直接配線接続などの有線媒体、ならびに、音響、ＲＦ、マイクロ波、衛星、赤外線、およびその他の無線媒体などの無線媒体がある。本明細書で使用されているコンピュータ読み取り可能媒体という用語は、記憶媒体と通信媒体との両方を含む。
【００１６】
様々な手順およびインターフェースは、システムメモリ２０４内に常駐する１つまたは複数のアプリケーションプログラムで実装することができる。一実施例では、アプリケーションプログラムは、コンピューティング装置（例えば、クライアント）と他のリモートに置かれているコンピューティング装置（例えば、サーバ）との間のファイル同期化をスケジュールするリモート差分圧縮アルゴリズムである。他の実施例では、アプリケーションプログラムは、圧縮および圧縮解除データ用のシステムメモリ２０４内に用意されている圧縮／圧縮解除手順である。さらに他の実施例では、アプリケーションプログラムは、クライアント装置のシステムメモリ２０４内に用意されている暗号解読手順である。
【００１７】
（リモート差分圧縮（ＲＤＣ））
図３Ａおよび３Ｂは、本発明の少なくとも１つの態様によるＲＤＣ手順例を示す図である。チャンクの個数は、特に、実際のオブジェクトＯAおよびＯBに応じてインスタンス毎に異なることがある。
【００１８】
図３Ａを参照すると、基本ＲＤＣプロトコルは、２つのコンピューティング装置（装置Ａおよび装置Ｂ）の間で折衝される。ＲＤＣプロトコルでは、暗黙のうちに、装置ＡおよびＢが、オブジェクトインスタンス（またはバージョン）ＯAおよびＯBによりそれぞれ示される同じオブジェクトまたはリソースの２つの異なるインスタンス（またはバージョン）を有すると想定している。この図に示されている実施例では、装置Ａは、リソースＯAの旧バージョンを持つが、装置Ｂは、リソースに関連付けられたコンテンツ（またはデータ）がわずかに（または付加的に）異なるバージョンＯBを持つ。
【００１９】
以下では、更新されたＯBを装置Ｂから装置Ａに転送するプロトコルについて説明する。類似のプロトコルを使用して、オブジェクトを装置Ａから装置Ｂに転送することができ、後述のプロトコルを著しく変更せずに、装置Ａまたは装置Ｂのいずれかからの命令により転送を開始できる。
【００２０】
１．装置Ａは、ＲＤＣプロトコルを使用してオブジェクトＯBを転送する要求を装置Ｂに送信する。他の実施形態では、装置Ｂは転送を開始し、この場合、プロトコルはステップ１をスキップし、以下のステップ２から開始する。
【００２１】
２．装置Ａは、オブジェクトＯAをチャンク１〜ｋに分割し、オブジェクトＯAのそれぞれのチャンク１．．ｋについてシグネチャＳｉｇAiおよび長さ（またはバイトで表されるサイズ）ＬｅｎAiを計算する。複数のチャンクへの分割について、以下で詳述する。装置Ａは、シグネチャおよびチャンク長のリスト（（ＳｉｇA1，ＬｅｎA1）．．．（ＳｉｇAk，ＬｅｎAk））を格納する。
【００２２】
３．装置Ｂは、オブジェクトＯBをチャンク１〜ｎに分割し、オブジェクトＯBのそれぞれのチャンク１．．ｎについてシグネチャＳｉｇBiおよび長さＬｅｎBiを計算する。ステップ３で使用される分割化アルゴリズムは、上記のステップ２のアルゴリズムと一致していなければならない。
【００２３】
４．装置Ｂは、オブジェクトＯBに関連付けられている計算されたチャンクシグネチャおよびチャンク長（（ＳｉｇB1，ＬｅｎB1）．．．（ＳｉｇBn，ＬｅｎBn））を装置Ａに送信する。チャンク長情報は、その後装置Ａによって使用され、チャンクの特定の集合をその開始オフセットおよび長さで識別することによりチャンクの特定の集合を要求することができる。リストの順次的性質のため、リスト内の先行するすべてのチャンクの長さを足し合わせて、各チャンクＢiのバイト単位の開始オフセットを計算することが可能である。
【００２４】
他の実施形態では、チャンクシグネチャおよびチャンク長のリストは、コンパクトになるように符号化され、可逆圧縮アルゴリズムを使用してさらに圧縮された後、装置Ａに送信される。
【００２５】
５．このデータを受信した後、装置Ａは、受信されたシグネチャリストを、コンテンツの旧バージョンに関連付けられている、ステップ２でオブジェクトＯAについて計算されたシグネチャＳｉｇA1．．ＳｉｇAkと突き合わせて比較する。
【００２６】
６．装置Ａは、ステップ４で装置Ｂから受信したシグネチャがステップ２で装置Ａにより計算されたシグネチャのどれとも一致しなかったすべてのチャンクについて装置Ｂに要求を送信する。要求されたチャンクＢi毎に、要求は、ステップ４で装置Ａにより計算されたチャンク開始オフセットおよびチャンク長を含む。
【００２７】
７．装置Ｂは、すべての要求されたチャンクに関連付けられているコンテンツを装置Ａに送信する。装置Ｂにより送信されるコンテンツは、さらに、可逆圧縮アルゴリズムを使用して圧縮した後に、装置Ａに送信することができる。
【００２８】
８．装置Ａは、ステップ７で装置Ｂから受信されるチャンクとともに、ステップ４で装置Ｂにより送信されるシグネチャと一致したオブジェクトＯAの装置Ａのチャンクを使用することにより、オブジェクトＯBのローカルコピーを再構成する。ローカルおよびリモートチャンクが装置Ａ上に再配列される順序は、ステップ４で装置Ａにより受信されるチャンクシグネチャのリストにより決定される。
【００２９】
パーティション分割ステップ２および３は、関連付けられたオブジェクト（それぞれ、ＯAおよびＯB）内のすべてのバイト位置で計算されるフィンガープリント関数を使用するデータ依存の方法で実行することができる。所定の位置について、フィンガープリント関数は、オブジェクト内のその位置を囲む小さなデータウィンドウを使用して計算され、フィンガープリント関数の値は、そのウィンドウに含まれるオブジェクトのすべてのバイトに依存する。フィンガープリント関数は、例えば、ハッシュ関数またはラビン多項式（Ｒａｂｉｎ  ｐｏｌｙｎｏｍｉａｌ）などの適切な関数とすることができる。
【００３０】
チャンク境界は、選択された条件を満たすようにフィンガープリント関数によって計算されるオブジェクト内の位置に決定される。チャンクシグネチャは、暗号的に安全なハッシュ関数（ＳＨＡ）また衝突困難なハッシュ関数などの他の何らかのハッシュ関数を使用して計算することができる。
【００３１】
ステップ４で送信されるシグネチャおよびチャンク長リストは、オリジナルのチャンクおよび識別された更新済みまたは新規チャンクの両方を使用してオブジェクトを再構成する基盤となる。ステップ６で要求されるチャンクは、そのオフセットおよび長さにより識別される。オブジェクトは、シグネチャがステップ４で装置Ａにより受信されたシグネチャと同じ順序で一致するローカルおよびリモートチャンクを使用することにより装置Ａ上に再構成される。
【００３２】
再構成ステップが装置Ａによって実行された後、オブジェクトＯAは、装置Ａ上に再構成されたオブジェクトＯBのコピーにより削除され、および置き換えられることが可能である。他の実施形態では、装置Ａは、将来のＲＤＣ転送時にチャンクの潜在的「再利用」のため、オブジェクトＯAを保持することができる。
【００３３】
大きなオブジェクトについては、図３Ａに例示されている基本的なＲＤＣプロトコルインスタンスだと、オブジェクトＯAおよびオブジェクトＯBが非常に近い、または同一であっても、ステップ４で著しい固定オーバーヘッドが生じる。平均チャンクサイズＣが与えられると、ステップ４においてネットワーク経由で伝送される情報の量は、オブジェクトＯBのサイズに比例し、特に、オブジェクトＯBのサイズを、オブジェクトＢのチャンクの個数である、したがってステップ４で送信される（チャンクシグネチャ、チャンク長）ペアの個数であるＣで割った値に比例する。
【００３４】
例えば、図６を参照すると、大きなイメージ（例えば、Ｍｉｃｒｏｓｏｆｔ  Ｖｉｒｔｕａｌ  Ｓｅｒｖｅｒなどの仮想マシンモニタにより使用される仮想ハードディスクイメージ）では、サイズが９．１ＧＢのオブジェクト（ＯB）が生じる可能性がある。平均的チャンクサイズＣが３ＫＢに等しいと、９ＧＢのオブジェクトでは、オブジェクトＯBに対し３００万個のチャンクが生成される可能性があり、ステップ４で４２ＭＢの関連するシグネチャおよびチャンク長情報をネットワーク経由で送信する必要がある。オブジェクトＯAとオブジェクトＯBとの間の差分（およびステップ７で送信する必要があるデータの量）は非常に小さくてもネットワーク上で４２ＭＢのシグネチャ情報が送信されなければならないため、プロトコルの固定オーバーヘッドコストは過度に高い。
【００３５】
ステップ４でのシグネチャ情報転送の代わりにＲＤＣプロトコルの再帰的適用を使用することにより、この固定オーバーヘッドコストを著しく低減できる。図３Ｂを参照すると、追加ステップ４．２〜４．８は、基本的なＲＤＣアルゴリズムのその置換ステップ４の下で以下のように説明されている。ステップ４．２〜４．８は、上述の基本的なＲＤＣプロトコルのステップ２〜８の再帰的適用に対応する。再帰的適用は、以下のステップ４．４に適用し、というように、所望の再帰の深さまで適用を続けることができる。
【００３６】
４．２．装置Ａは、再帰的シグネチャチャンクの中へのシグネチャおよびチャンク長リスト（（ＳｉｇA1，ＬｅｎA1）．．．（ＳｉｇAk，ＬｅｎAk））の再帰的チャンキングを実行し、ｓ＜＜ｋの場合、再帰的シグネチャおよび再帰的チャンク長の他のリスト（（ＲＳｉｇA1，ＲＬｅｎA1）．．．（ＲＳｉｇAs，ＲＬｅｎAs））を取得する。
【００３７】
４．３．装置Ｂは、シグネチャおよびチャンク長のリスト（（ＳｉｇB1，ＬｅｎB1）．．．（ＳｉｇBn，ＬｅｎBn））を再帰的にチャンクアップして、ｒ＜＜ｎの場合、再帰的シグネチャおよび再帰的チャンク長のリスト（（ＲＳｉｇB1，ＲＬｅｎB1）．．．（ＲＳｉｇBr，ＲＬｅｎBr））を生成する。
【００３８】
４．４．装置Ｂは、再帰的シグネチャおよび再帰的チャンク長の順序付きリスト（（ＲＳｉｇB1，ＲＬｅｎB1）．．．（ＲＳｉｇBr，ＲＬｅｎBr））を装置Ａに送信する。再帰的チャンクシグネチャおよび再帰的チャンク長のリストは、コンパクトになるように符号化され、可逆圧縮アルゴリズムを使用してさらに圧縮された後、装置Ａに送信される。
【００３９】
４．５．装置Ａは、装置Ｂから受信された再帰的シグネチャをステップ４．２で計算された再帰的シグネチャの装置Ａのリストとを比較する。
【００４０】
４．６．装置Ａは、装置Ａがその集合（ＲＳｉｇA1．．．ＲＳｉｇAs）内に一致する再帰的シグネチャを持たないすべての異なる再帰的シグネチャチャンク（再帰的シグネチャＲＳｉｇBkがある）に関する要求を装置Ｂに送信する。
【００４１】
４．７．装置Ｂは、要求された再帰的シグネチャチャンクを装置Ａに送信する。要求された再帰的シグネチャチャンクは、可逆圧縮アルゴリズムを使用してさらに圧縮した後に、装置Ａに送信することができる。
【００４２】
４．８．装置Ａは、ローカルで一致する再帰的シグネチャチャンクおよびステップ４．７で装置Ｂから受信された再帰的チャンクを使用して、シグネチャおよびチャンク情報のリスト（（ＳｉｇB1，ＬｅｎB1）．．．（ＳｉｇBn，ＬｅｎBn））を再構成する。
【００４３】
上記のステップ４．８が完了した後、実行は、図３Ａに例示されている、上述の基本的なＲＤＣプロトコルのステップ５に続く。
【００４４】
再帰的チャンクキング動作の結果として、オブジェクトに関連付けられている再帰的シグネチャの個数は、平均チャンクサイズＣに等しい割合で減らされ、再帰的シグネチャの個数が著しく減る（それぞれ、オブジェクトＯAについてはｒ＜＜ｎおよびオブジェクトＯBについてはｓ＜＜ｋ）。一実施形態では、同じチャンキングパラメータは、オリジナルのオブジェクトＯAおよびＯBをチャンキングする場合のようにシグネチャをチャンキングするために使用することが可能である。他の実施形態では、再帰的ステップに、他のチャンキングパラメータを使用することができる。
【００４５】
非常に大きなオブジェクトについては、上記の再帰的ステップを、ｋ≧１としてｋ回適用することができる。Ｃの平均チャンクサイズについては、再帰的チャンキングにより、ネットワーク上のシグネチャトラフィックのサイズ（ステップ４．２から４．８）をＣkにほぼ対応する分だけ小さくできる。Ｃは、比較的大きいので、１を超える再帰の深さは、非常に大きなオブジェクトの場合にのみ必要と考えられる。
【００４６】
一実施形態では、再帰的ステップの数は、予想平均チャンクサイズ、オブジェクトＯAおよび／またはＯBのサイズ、オブジェクトＯAおよび／またはＯBのデータ形式、装置Ａおよび装置Ｂを接続するネットワークの待ち時間および帯域幅特性のうちの１つまたは複数を含むパラメータを考慮することにより動的に決定することができる。
【００４７】
ステップ２で使用されるフィンガープリント関数は、ステップ３で使用されるフィンガープリント関数に一致する。同様に、ステップ４．２で使用されるフィンガープリント関数は、ステップ４．３で使用されるフィンガープリント関数に一致する。ステップ２〜３が提供するフィンガープリント関数は、オプションにより、ステップ４．２〜４．３が提供するフィンガープリント関数に一致させることができる。
【００４８】
前述のように、各フィンガープリント関数は、オブジェクト内の位置を囲む小さなデータウィンドウを使用し、その場合、フィンガープリント関数に関連付けられている値は、データウィンドウ内に含まれるオブジェクトのすべてのバイトに依存する。データウィンドウのサイズは、１つまたは複数の基準に基づいて動的に調整することができる。さらに、チャンキング手順では、フィンガープリント関数の値および１つまたは複数の追加チャンキングパラメータを使用して、ステップ２〜３および上記の４．２〜４．３でチャンク境界を決定する。
【００４９】
ウィンドウサイズおよびチャンキングパラメータを動的に変更することにより、利用可能な帯域幅の消費を最小限に抑えつつ、必要なデータ転送が実行されるようにチャンク境界が調整される。
【００５０】
ウィンドウサイズおよびチャンキングパラメータを調整する基準例は、オブジェクトに関連付けられたデータ型、環境制約条件、使用モデル、装置Ａおよび装置Ｂを接続するネットワークの待ち時間および帯域幅特性、および平均データ転送ブロックサイズを決定するのに適している他のモデルを含む。データ型の例として、ワードプロセッシングファイル、データベースイメージ、スプレッドシート、プレゼンテーションスライドショー、およびグラフィックイメージがある。使用モデル例として、標準的なデータ転送で必要なバイトの平均個数が監視される場合が挙げられる。
【００５１】
アプリケーションプログラム内の１つの要素に変更を加えただけで、関連するデータムおよび／またはファイルへの変更も多数生じる可能性がある。ほとんどのアプリケーションプログラムは、関連付けされたファイルタイプを持つので、ファイルタイプは、ウィンドウサイズおよびチャンキングパラメータを調整する際に考慮に値する有力な基準の１つである。一実施例では、ワープロ文書内のたった１つの文字を修正するだけで、関連するファイル内の約１００バイトが変更される。他の実施例では、データベースアプリケーション内のたった１つの要素を修正するだけで、データベースインデックスファイル内の１０００バイトが変更される。それぞれの実施例について、適切なウィンドウサイズおよびチャンキングパラメータは異なることがあり、チャンキング手順は特定のアプリケーションに基づいて最適化された適切な粒度を持つ。
【００５２】
（プロセスの流れの例）
図４Ａおよび４Ｂに、本発明の少なくとも一態様により用意されるＲＤＣ手順の実施例実行時にローカル装置（例えば、装置Ａ）とリモート装置（例えば、装置Ｂ）との間のやり取りのプロセスの流れを例示する。図４Ａの左側は、ローカル装置Ａに作用するステップ４００〜４１３を示し、図４Ａの右側は、リモート装置Ｂに作用するステップ４５０〜４５６を示している。
【００５３】
図４Ａに例示されているように、やり取りは、装置Ａがステップ４００内のオブジェクトＯBのＲＤＣ転送を要求し、装置Ｂがステップ４５０でこの要求を受信することにより始まる。この後、ローカル装置Ａおよびリモート装置Ｂは両方とも、ステップ４０１および４５１内のフィンガープリントを独立に計算し、ステップ４０２および４５２でそれぞれのオブジェクトを複数のチャンクに分割し、ステップ４０３および４５３においてそれぞれのチャンクについてシグネチャ（例えば、ＳＨＡ）を計算する。
【００５４】
ステップ４５４で、装置Ｂは、ステップ４５２および４５３で計算されたシグネチャおよびチャンク長リストを装置Ａに送信し、装置Ａは、ステップ４０４でこの情報を受信する。
【００５５】
ステップ４０５で、ローカル装置Ａは、要求されたチャンクのリストを空リストに初期化し、リモートチャンクの追跡オフセットを０に初期化する。ステップ４０６で、次の（シグネチャ、チャンク長）ペア（ＳｉｇBi、ＬｅｎBi）は、ステップ４０４で受信されたリストから考慮対象として選択される。ステップ４０７で、装置Ａは、ステップ４０６で選択されたシグネチャＳｉｇBiがステップ４０３で計算されたシグネチャのいずれかと一致するか否かをチェックする。一致する場合、実行はステップ４０９に続く。一致しない場合、追跡リモートチャンクオフセットおよびバイト単位の長さＬｅｎBiがステップ４０８で要求リストに追加される。ステップ４０９で、追跡オフセットは、現在のチャンクＬｅｎBiの長さだけインクリメントされる。
【００５６】
ステップ４１０で、ローカル装置Ａは、ステップ４０４で受信されたすべての（シグネチャ、チャンク長）ペアがすでに処理されているか否かを検査する。処理済みでない場合、実行はステップ４０６に続く。そうでない場合、ステップ４１１で、チャンク要求リストは、小さくなるように適宜符号化され、圧縮され、リモート装置Ｂに送信される。
【００５７】
リモート装置Ｂは、ステップ４５５でチャンクの圧縮されたリストを受信し、それを圧縮解除し、その後、ステップ４５６で圧縮してチャンクデータを送り返す。
【００５８】
ローカル装置は、ステップ４１２で、要求されたチャンクデータを受信し、圧縮解除する。ローカル装置では、オブジェクトＯAのローカルコピーおよび受信されたチャンクデータを用いて、ステップ４１３でＯBのローカルコピーを組み立て直す。
【００５９】
図４Ｂは、図４Ａからのステップ４１３の詳細な例を示している。処理はステップ４１４に続き、そこで、ローカル装置Ａは、再構成されたオブジェクトを空に初期化する。
【００６０】
ステップ４１５で、次の（シグネチャ、チャンク長）ペア（ＳｉｇBi、ＬｅｎBi）は、ステップ４０４で受信されたリストから考慮対象として選択される。ステップ４１６で、装置Ａは、ステップ４１７で選択されたシグネチャＳｉｇBiがステップ４０３で計算されたシグネチャのいずれかと一致するか否かをチェックする。
【００６１】
一致した場合、実行はステップ４１７に続き、そこで、対応するローカルチャンクが再構成されたオブジェクトに付加される。一致しない場合、受信され圧縮解除されたリモートチャンクは、ステップ４１８で、再構成されたオブジェクトに付加される。
【００６２】
ステップ４１９で、ローカル装置Ａは、ステップ４０４で受信されたすべての（シグネチャ、チャンク長）ペアがすでに処理されているか否かを検査する。処理済みでない場合、実行はステップ４１５に続く。処理済みの場合、再構成されたオブジェクトは、ステップ４２０で、装置Ａ上のオブジェクトＯAの古いコピーを置き換えるために使用される。
【００６３】
（再帰的シグネチャ転送プロセスの流れの例）
図５Ａおよび５Ｂに、本発明の少なくとも一態様に従って用意されるＲＤＣ手順例でシグネチャおよびチャンク長リストの再帰的転送を行うプロセスの流れを例示する。後述の手順は、通常関連付けられているオブジェクトを更新することを試みるローカル装置とリモート装置の両方に適用することができる。
【００６４】
図５Ａの左側は、ローカル装置Ａに作用するステップ５０１〜５１３を示し、図５Ａの右側は、リモート装置Ｂに作用するステップ５５１〜５５６を示している。ステップ５０１〜５１３は、図４Ａのステップ４０４を置き換えたものであるが、ステップ５５１〜５５６は図４Ａのステップ４５４を置き換えたものである。
【００６５】
ステップ５０１および５５１では、ローカル装置Ａとリモート装置Ｂは両方とも、それぞれ、ステップ４０２／４０３および４５２／４５３で計算されたシグネチャおよびチャンク長リスト（（ＳｉｇA1，ＬｅｎA1），．．．（ＳｉｇAk，ＬｅｎAk））および（ＳｉｇB1，ＬｅｎB1），．．．（ＳｉｇBn，ＬｅｎBn）の再帰的フィンガープリントを独立に計算する。ステップ５０２および５５２で、これらの装置は、それぞれのシグネチャおよびチャンク長リストを複数の再帰的チャンクに分割し、ステップ５０３および５５３で、それぞれ、再帰的チャンク毎に再帰的シグネチャ（例えば、ＳＨＡ）を計算する。
【００６６】
ステップ５５４で、装置Ｂは、ステップ５５２および５５３で計算された再帰的シグネチャおよびチャンク長リストを装置Ａに送信し、装置Ａは、ステップ５０４でこの情報を受信する。
【００６７】
ステップ５０５で、ローカル装置Ａは、要求された再帰的チャンクのリストを空リストに初期化し、リモート再帰的チャンクの追跡リモート再帰的オフセットを０に初期化する。ステップ５０６で、次の（再帰的シグネチャ、再帰的チャンク長）ペア（ＲＳｉｇBi、ＲＬｅｎBi）は、ステップ５０４で受信されたリストから考慮対象として選択される。ステップ５０７で、装置Ａは、ステップ５０６で選択された再帰的シグネチャＲＳｉｇBiがステップ５０３で計算された再帰的シグネチャのどれかと一致するか否かをチェックする。一致する場合、実行はステップ５０９に続く。一致しない場合、追跡リモート再帰的チャンクオフセットおよびバイト単位の長さＲＬｅｎBiがステップ５０８で要求リストに追加される。ステップ５０９で、追跡リモート再帰的オフセットは、現在の再帰的チャンクＲＬｅｎBiの長さだけインクリメントされる。
【００６８】
ステップ５１０で、ローカル装置Ａは、ステップ５０４で受信されたすべての（再帰的シグネチャ、再帰的チャンク長）ペアがすでに処理されているか否かを検査する。処理済みでない場合、実行はステップ５０６に続く。そうでない場合、ステップ５１１で、再帰的チャンク要求リストは、小さくなるように符号化され、圧縮され、リモート装置Ｂに送信される。
【００６９】
リモート装置Ｂは、ステップ５５５で再帰的チャンクの圧縮されたリストを受信し、そのリストを圧縮解除し、その後、ステップ５５６で、圧縮して再帰的チャンクデータを送り返す。
【００７０】
ローカル装置は、ステップ５１２で、要求された再帰的チャンクデータを受信し、圧縮解除する。ローカル装置は、シグネチャおよびチャンク長リスト（（ＳｉｇA1，ＬｅｎA1），．．．（ＳｉｇAk，ＬｅｎAk））のローカルコピーおよび受信された再帰的チャンクデータを用いて、ステップ５１３で、シグネチャおよびチャンク長リスト（（ＳｉｇB1，ＬｅｎB1），（ＳｉｇBk，ＬｅｎBn））のローカルコピーを組み立て直す。その後、実行は図４Ａのブロック４０５に続く。
【００７１】
図５Ｂに、図５Ａのステップ５１３の詳細な例を示す。処理はステップ５１４に続き、そこで、ローカル装置Ａは、リモートシグネチャおよびチャンク長のリストＳＩＧＣＬを空リストに初期化する。
【００７２】
ステップ５１５で、次の（再帰的シグネチャ、再帰的チャンク長）ペア（ＲＳｉｇBi、ＲＬｅｎBi）は、ステップ５０４で受信されたリストから考慮対象として選択される。ステップ５１６で、装置Ａは、ステップ５１５で選択された再帰的シグネチャＲＳｉｇＢｉがステップ５０３で計算された再帰的シグネチャのいずれかと一致するか否かをチェックする。
【００７３】
一致する場合、実行はステップ５１７に続き、そこで装置Ａは、対応するローカル再帰的チャンクをＳＩＧＣＬに付加する。一致しない場合、受信されたリモート再帰的チャンクは、ステップ５１８で、ＳＩＧＣＬに付加される。
【００７４】
ステップ５１９で、ローカル装置Ａは、ステップ５０４で受信されたすべての（再帰的シグネチャ、再帰的チャンク長）ペアがすでに処理されているか否かを検査する。処理済みでない場合、実行はステップ５１５に続く。処理済みの場合、シグネチャおよびチャンク長リスト（（ＳｉｇB1，ＬｅｎB1），．．．（ＳｉｇBk，ＬｅｎBn））は、ステップ５２０でＳＩＧＣＬの値に設定される。その後、実行は図４Ａのブロック４０５に戻って続く。
【００７５】
状況に応じて、再帰的シグネチャおよびチャンク長リストを評価し、前述のように帯域幅利用度を最小にするためにさらに再帰的リモート差分圧縮が必要か否かを判定することができる。再帰的シグネチャおよびチャンク長リストは、所望の圧縮レベルが得られるまで、ステップ５０４および５５４をＲＤＣ手順の他のインスタンスに置き換える操作を続けて行くことにより前述のチャンキング手順を使用して再帰的に圧縮することができる。再帰的シグネチャリストが十分に圧縮された後、前述のようにリモート装置とローカル装置との間の伝送のために再帰的シグネチャリストが返される。
【００７６】
図６は、一実施例により用意されたＲＤＣシーケンス例における再帰的圧縮の例をグラフィックで例示する図である。図６に示されている実施例では、オリジナルのオブジェクトは９．１ＧＢ分のデータである。シグネチャおよびチャンク長リストは、チャンキング手順を使用してコンパイルされ、そこで、シグネチャおよびチャンク長リストから３００万個のチャンク（または４２ＭＢのサイズ）が得られる。第１の再帰的ステップの後、シグネチャリストは、３３０００個のチャンクに分割され、サイズ３３ＫＢの再帰的シグネチャおよび再帰的チャンク長リストに減らされる。シグネチャリストを再帰的に圧縮することにより、シグネチャリストを転送するための帯域幅利用度は、これにより、４２ＭＢから約３９５ＫＢに劇的に縮小される。
【００７７】
（オブジェクト更新の例）
図７は、本発明の少なくとも一態様により用意されるＲＤＣ手順例を使用してクライアントおよびサーバアプリケーションのやり取りを例示する図である。サーバおよびクライアントの両方にあるオリジナルのファイルは、「The quick fox jumped over the lazy brown dog.  The dog was so lazy that he didn't notice the fox jumping over him.」という文を含んでいた。
【００７８】
その後に、サーバ上のファイルは、「The quick fox jumped over the lazy brown dog.  The brown dog was so lazy that he didn't notice the fox jumping over him.」に更新される。
【００７９】
すでに説明されているように、クライアントは、ファイルを更新するよう定期的に要求する。クライアントおよびサーバは両方とも、オブジェクト（テキスト）を例示されているように複数のチャンクに切り分ける。クライアント上では、それらのチャンクは、「Ｔｈｅ  ｑｕｉｃｋ  ｆｏｘ  ｊｕｍｐｅｄ」、「ｏｖｅｒ  ｔｈｅ  ｌａｚｙ  ｂｒｏｗｎ  ｄｏｇ．」、「Ｔｈｅ  ｄｏｇ  ｗａｓ  ｓｏ  ｌａｚｙ  ｔｈａｔ  ｈｅ  ｄｉｄｎ’ｔ  ｎｏｔｉｃｅ」、および「ｔｈｅ  ｆｏｘ  ｊｕｍｐｉｎｇ  ｏｖｅｒ  ｈｉｍ．」であり、クライアントシグネチャリストは、ＳＨＡ11、ＳＨＡ12、ＳＨＡ13、およびＳＨＡ14として生成される。サーバ上では、それらのチャンクは、「Ｔｈｅ  ｑｕｉｃｋ  ｆｏｘ  ｊｕｍｐｅｄ」、「ｏｖｅｒ  ｔｈｅ  ｌａｚｙ  ｂｒｏｗｎ  ｄｏｇ．」、「Ｔｈｅ  ｂｒｏｗｎ  ｄｏｇ  ｗａｓ」、「ｓｏ  ｌａｚｙ  ｔｈａｔ  ｈｅ  ｄｉｄｎ’ｔ  ｎｏｔｉｃｅ」、および「ｔｈｅ  ｆｏｘ  ｊｕｍｐｉｎｇ  ｏｖｅｒ  ｈｉｍ．」であり、サーバシグネチャリストは、ＳＨＡ21、ＳＨＡ22、ＳＨＡ23、ＳＨＡ24、およびＳＨＡ25として生成される。
【００８０】
サーバは、前述のように再帰シグネチャ圧縮技術を使用してシグネチャリスト（ＳＨＡ21〜ＳＨＡ25）を送信する。クライアントは、ローカルに格納されているシグネチャリスト（ＳＨＡ11〜ＳＨＡ14）が受信されたシグネチャリスト（ＳＨＡ21〜ＳＨＡ25）と一致しないことを認識し、欠落しているチャンク３および４をサーバに要求する。サーバは、チャンク３および４（「Ｔｈｅ  ｂｒｏｗｎ  ｄｏｇ  ｗａｓ」、および「ｓｏ  ｌａｚｙ  ｔｈａｔ  ｈｅ  ｄｉｄｎ’ｔ  ｎｏｔｉｃｅ」）を圧縮し、送信する。クライアントは、圧縮されたチャンクを受信し、それらを圧縮解除して、図７に例示されているようにファイルを更新する。
【００８１】
（チャンキング分析）
上述の基本的なＲＤＣ手順の有効性は、オブジェクトデータをチャンクに分ける、および／またはシグネチャおよびチャンク長リストをチャンクに分けるために使用されるチャンキング手順を最適化することにより高められる。
【００８２】
基本的なＲＤＣ手順は、以下の総和により識別されるネットワーク通信オーバーヘッドコストを持つ。
【００８３】
（Ｓ１）｜Ｂからのシグネチャおよびチャンク長｜＝｜ＯB｜＊｜ＳｉｇＬｅｎ｜／Ｃ、ただし、｜ＯB｜はオブジェクトＯBのバイト単位のサイズであり、ＳｉｇＬｅｎは（シグネチャ，チャンク長）ペアのバイト単位のサイズであり、Ｃはバイト単位の予想平均チャンクサイズである。
【００８４】
（Ｓ２）Σｃｈｕｎｋ＿ｌｅｎｇｔｈ、ただし、（ｓｉｇｎａｔｕｒｅ，ｃｈｕｎｋ＿ｌｅｎｇｔｈ）∈Ｂからのシグネチャ、
およびｓｉｇｎａｔｕｒｅ
【００８５】
【数１】
2006092558.tif 000003
【００８６】
Ａからのシグネチャ。
【００８７】
通信コストは、大きな平均チャンクサイズおよびリモートチャンクとローカルチャンクとの間の大きな共通集合から恩恵を受ける。オブジェクトを複数のチャンクに切り分ける方法の選択により、プロトコルの品質が決定される。ローカルおよびリモート装置は、事前の通信なしで、オブジェクトを切り分ける場所について合意していなければならない。以下では、切り分けを見つける様々な方法を説明し、分析する。
【００８８】
切り分けアルゴリズムについては、以下の特徴が知られていると仮定する。
【００８９】
１．スラック：ファイル差分の帳尻を合わせるためにチャンクに必要なバイト数。シーケンスｓ１、ｓ２、およびｓ３を考え、２つのシーケンスｓ１ｓ３、ｓ２ｓ３を連結により形成する。２つのシーケンスＣｈｕｎｋｓ１、およびＣｈｕｎｋｓ２のチャンクを生成する。Ｃｈｕｎｋｓ１’およびＣｈｕｎｋｓ２’が、Ｃｈｕｎｋｓ１およびＣｈｕｎｋｓ２からそれぞれ第１の共通接尾辞に達するまでのチャンク長の総和である場合、バイト単位のスラックは以下の公式により与えられる。
【００９０】
ｓｌａｃｋ＝Ｃｈｕｎｋｓ1’−｜ｓ1｜＝Ｃｈｕｎｋｓ2’−｜ｓ2｜
２．平均チャンクサイズＣ：
オブジェクトＯAおよびＯBが平均サイズＫと共通のＳ個のセグメントを持つ場合、ローカルのクライアント上で得られるチャンクの個数は以下の式で与えられ、
【００９１】
【数２】
2006092558.tif 000004
【００９２】
上記の（Ｓ２）は以下のように書き換えられる。
【００９３】
【数３】
2006092558.tif 000005
【００９４】
そのため、ｓｌａｃｋを最小にするチャンキングアルゴリズムにより、電話回線で送信されるバイト数は最小にされる。したがって、予想されるスラックを最小にするチャンキングアルゴリズムを使用すると都合がよい。
【００９５】
（フィンガープリント関数）
すべてのチャンキングアルゴリズムは、小さなウィンドウ、つまり、バイトの制限されたシーケンスに依存するフィンガープリント関数、またはハッシュを使用する。チャンキングに使用されるハッシュアルゴリズムの実行時間は、それらのアルゴリズムが有限差分（強度削減）最適化の影響を受けやすいとき、ハッシュウィンドウサイズと無関係である。したがって、サイズｋのハッシュウィンドウについては、ｂ0、ｂk、および＃［ｂ0，ｂ1，．．．，ｂk-1］のみを使用してハッシュ＃［ｂ1，．．．，ｂk-1，ｂk］を計算するのは容易であろう（一定数のステップのみを必要とする）。ラビン多項式を使用するハッシュ関数とともに事前計算された乱数の表に基づく計算効率の高いと思われる他のハッシュ関数などの様々なハッシュ関数を採用することができる。
【００９６】
一実施例では、ローリングチェックサムに基づく３２ビットＡｄｌｅｒハッシュは、フィンガープリントのハッシュ関数として使用することができる。この手順は、それぞれが事前計算された１６ビットの乱数である、２５６個のエントリを持つ固定テーブルを使用することにより十分に良好なランダムハッシュ関数を実現する。このテーブルは、フィンガープリントバイトを１６ビットの乱数に変換するために使用される。３２ビットハッシュは、２つの１６ビット数ｓｕｍ１とｓｕｍ２に分割され、以下の手順で更新される。
【００９７】
ｓｕｍ１＋＝ｔａｂｌｅ［ｂk］−ｔａｂｌｅ［ｂ0］
ｓｕｍ２＋＝ｓｕｍ１−ｋ＊ｔａｂｌｅ［ｂ0］
他の実施例では、循環シフトを使用する６４ビットランダムハッシュは、フィンガープリントのためのハッシュ関数として使用することができる。循環シフトの周期は、ハッシュ値のサイズにより制限される。そのため、６４ビットハッシュ値を使用すると、ハッシュの周期は６４に設定される。ハッシュを更新する手順は以下のとおりである。
【００９８】
ｈａｓｈ＝ｈａｓｈ∧（（ｔａｂｌｅ［ｂ0］＜＜１）｜（ｔａｂｌｅ［ｂ0］＞＞ｕ））∧ｔａｂｌｅ［ｂk］；
ｈａｓｈ＝（ｈａｓｈ＜＜１）｜（ｈａｓｈ＞＞６３）；
ただし、１＝ｋ％６４およびｕ＝６４−１
さらに他の実施例では、他のシフト方法を使用して、フィンガープリントを実現できる。直接的な循環シフトは、制限された長さの周期を生成し、ハッシュ値のサイズにより制限される。他の順列は周期がそれよりも長い。例えば、循環（１  ２  ３  ０）（５  ６  ７  ８  ９  １０  １１  １２  １３  １４  ４）（１６  １７  １８  １９  ２０  ２１  １５）（２３  ２４  ２５  ２６  ２２）（２８  ２９  ２７）（３１  ３０）により与えられる順列は、長さ４＊３＊５＊７＊１１＝４６２０の周期を有する。右へのシフトの後に各区間の始めの位置を修正する演算を使用して、この順列の例の単一の適用を計算することができる。
【００９９】
（所定のパターンでのチャンキングに対する従来技術の分析）
以前のチャンキング方法は、所定のウィンドウサイズｋ（＝４８）のフィンガープリントハッシュを計算し、ハッシュビットの部分集合が所定のパターンと一致するか否かに基づいて切点を識別することにより決定される。ランダムハッシュ値を使用すると、このパターンは０とすることもでき、関連する部分集合も、ハッシュの接頭辞とすることができる。基本命令では、これは、以下の形式の述部に翻訳される。
【０１００】
ＣｕｔＰｏｉｎｔ（ｈａｓｈ）≡０＝＝（ｈａｓｈ＆（（１＜＜ｃ）−１））
ただし、ｃは、照合されるべきビットの個数である。
【０１０１】
ランダムハッシュ関数が与えられた場合の一致に対する確率が２-cなので、平均チャンクサイズＣ＝２cが結果として得られる。しかし、最小、または最大チャンクサイズはいずれも、この手順では決定されない。ｍの最小チャンク長が課された場合、平均チャンクサイズは以下のようになる。
【０１０２】
Ｃ＝ｍ＋２c
予想されるスラックの概算は、ストリームｓ1ｓ3およびｓ2ｓ3を考慮することにより得られる。ｓ1およびｓ2における切点は、任意の桁に出現できる。平均チャンク長はＣ＝ｍ＋２cなので、ｓ1およびｓ2の最後の切点の約（２c／Ｃ）2は、距離ｍを超える。これらは、約２cのところでスラックに寄与する。残りの１−（２c／Ｃ）2は、長さ約Ｃのスラックとともに関わる。その後、予想されるスラックは、（２c／Ｃ）3＋（１−（２c／Ｃ）2）＊（Ｃ／Ｃ）＝（２c／Ｃ）3＋１−（２c／Ｃ）2程度となり、ｍ＝２c-1に対し大域的な最小値を持ち、値は約２３／２７＝０．８５である。より正確な分析により、残り１−（２c／Ｃ）2の端数に対しいくらか低い推定値が得られるが、ｓ3の内側の距離ｍの範囲内の切断を補正する必要もあり、より高い推定値の一因となる。
【０１０３】
そのため、従来技術の予想されるスラックは約０．８５＊Ｃである。
【０１０４】
（フィルタでのチャンキング（新しい技術））
フィルタでのチャンキングは、フィルタを固定することに基づいており、これは、長さｍのパターン列であり、フィンガープリントハッシュのシーケンスをフィルタと照合する。このフィルタで、ハッシュのシーケンスをフィルタの接頭辞と接尾辞の両方に一致させることができない場合、２つの一致の間の最小距離は少なくともｍでなければならないと推論することができる。フィルタ例は、最初のｍ−１個のパターンを
０！＝（ｈａｓｈ＆（（１＜＜ｃ）−１））
に設定し、最後のパターンを
０＝＝（ｈａｓｈ＆（（１＜＜ｃ）−１））
に設定することにより、従来技術で使用されるＣｕｔＰｏｉｎｔ述部から得られる。
【０１０５】
このフィルタの一致の確率は、ｐが２-cとすると、（１−ｐ）m-1ｐで与えられる。予想されるチャンク長は、フィルタの一致の確率の逆数をとることにより与えられ（フィルタで、シーケンスが接頭辞と接尾辞との両方と一致しないようにすることが必要である）、したがって、フィルタ例の予想される長さは（１−ｐ）-m+1ｐ-1である。この長さは、ｐ：＝１／ｍに設定した場合に最小になり、約（ｅ＊ｍ）であることが分かる。平均スラックは、０．８を中心として変動するが、当業者であれば検証可能である。この方法の他の実施形態では、ｒａｗ入力と直接連携するパターンを使用し、ローリングハッシュを使用しない。
【０１０６】
（局所最大値でのチャンキング（新しい技術））
局所最大値でのチャンキングは、有界な水平軸の範囲内にある切点として選択することに基づく。以下では、水平軸の値に対しｈを使用することにする。オフセットｏｆｆｓｅｔ−ｈ、．．．、ｏｆｆｓｅｔ−１とともにｏｆｆｓｅｔ＋１、．．．、ｏｆｆｓｅｔ＋ｈでのハッシュ値がすべてｏｆｆｓｅｔでのハッシュ値よりも小さい場合に、位置ｏｆｆｓｅｔのハッシュはｈ局所最大であるという。つまり、左にｈステップ、および右にｈステップのすべての位置は、より小さなハッシュ値を持つ。当業者であれば、局所最大値は、局所最小値または他の測定基準ベースの比較（「ハッシュ値の中央値に最も近い」など）で置き換えられることを理解するであろう。
【０１０７】
サイズｎのオブジェクトに対する局所最大値の集合は、２・ｎ回の演算を限界とする時間で計算することができ、局所最大値の集合を計算するコストは、独立のチャンキングに基づいて切点を計算するコストに近いか、または同じである。局所最大値を使用して生成されたチャンクは、常に、ｈに対応する最小サイズを持ち、平均サイズは約２ｈ＋１である。ＣｕｔＰｏｉｎｔ手順は、図８および９に例示されており、以下のように説明される。
【０１０８】
１．エントリがレコード｛ｉｓＭａｘ＝ｆａｌｓｅ，ｈａｓｈ＝０，ｏｆｆｓｅｔ＝０｝で初期化された長さｈの配列Ｍを割り当てる。各フィールド内の第１のエントリ（ｉｓＭａｘ）は、候補が局所最大値とすることが可能か否かを示す。第２のフィールドのエントリ（ｈａｓｈ）は、そのエントリに関連付けられたハッシュ値を示し、０（またはそれとは別に、可能な最大ハッシュ値）に初期化される。エントリ内の最後のフィールド（ｏｆｆｓｅｔ）は、フィンガープリントオブジェクトの中への候補までのバイト単位の絶対オフセットを示す。
【０１０９】
２．配列Ｍの中へのオフセットｍｉｎおよびｍａｘを０に初期化する。これらの変数は、現在使用されている配列の最初の要素と最後の要素を指す。
【０１１０】
３．ＣｕｔＰｏｉｎｔ（ｈａｓｈ，ｏｆｆｓｅｔ）は、図８のステップ８００から始まり、オブジェクトのそれぞれのオフセットで呼び出され、Ｍを更新し、特定のオフセットが切点であるか否かを示す結果を返す。
【０１１１】
この手順は、ステップ８０１でｒｅｓｕｌｔ＝ｆａｌｓｅに設定することから開始する。
【０１１２】
ステップ８０３で、この手順では、Ｍ［ｍａｘ］．ｏｆｆｓｅｔ＋ｈ＋１＝ｏｆｆｓｅｔか否かをチェックする。この条件が真の場合、実行はステップ８０４に続き、そこで、以下の割り当てが実行され、結果はＭ［ｍａｘ］．ｉｓＭａｘに設定され、ｍａｘはｍａｘ−１％ｈに設定される。次に、実行は、ステップ８０５に続く。ステップ８０３での条件が偽であれば、実行はステップ８０５に続く。ステップ８０５で、この手順では、Ｍ［ｍｉｎ］．ｈａｓｈ＞ｈａｓｈか否かをチェックする。条件が真の場合、実行はステップ８０６に続き、ｍｉｎは（ｍｉｎ−１）％ｈに設定される。実行はステップ８０７に続き、そこで、Ｍ［ｍｉｎ］は、｛ｉｓＭａｘ＝ｆａｌｓｅ，ｈａｓｈ＝ｈａｓｈ，ｏｆｆｓｅｔ＝ｏｆｆｓｅｔ｝に設定され、ステップ８１１に続いて、そこで、計算された結果が返される。
【０１１３】
ステップ８０５で条件が偽の場合、実行はステップ８０８に続き、そこで、手順により、Ｍ［ｍｉｎ］．ｈａｓｈ＝ｈａｓｈか否かがチェックされる。この条件が真の場合、実行はステップ８０７に続く。
【０１１４】
ステップ８０８で条件が偽の場合、実行はステップ８０９に続き、そこで、手順により、ｍｉｎ＝ｍａｘか否かがチェックされる。この条件が真の場合、実行はステップ８１０に続き、そこで、Ｍ［ｍｉｎ］は｛ｉｓＭａｘ＝ｔｒｕｅ，ｈａｓｈ＝ｈａｓｈ，ｏｆｆｓｅｔ＝ｏｆｆｓｅｔ｝に設定される。その後、実行はステップ８１１に続き、そこで、計算された結果が返される。
【０１１５】
ステップ８０９で条件が偽の場合、実行はステップ８１１に続き、そこで、ｍｉｎは（ｍｉｎ＋１）％ｈに設定される。次に、実行は、ステップ８０５に戻って続く。
【０１１６】
４．ＣｕｔＰｏｉｎｔ（ｈａｓｈ，ｏｆｆｓｅｔ）が真を返す場合、これは位置ｏｆｆｓｅｔ−ｈ−１が新しい切点である場合となる。
【０１１７】
（局所最大値手順の分析）
ｎバイトのオブジェクトは、与えられたオブジェクトについて高々ｎ個のエントリが挿入されるように、ＣｕｔＰｏｉｎｔをｎ回呼び出すことにより処理される。削除されるエントリがｎ個以下となるように、ステップ８０５で開始するループが繰り返される毎に１つのエントリが削除される。そのため、この処理ループには、エントリ毎に１回入ることができ、繰り返しの組み合わせた回数は高々ｎとすることができる、これは、ＣｕｔＰｏｉｎｔの各呼び出しでのループ内のステップの平均数は、２よりも少し小さく、切点を計算するステップの数は、ｈと無関係であることを意味する。
【０１１８】
これらの要素からのハッシュ値は、ｍｉｎとｍａｘとの間の下降する連鎖を形成するので、ｍｉｎとｍａｘとの間の平均距離（｜ｍｉｎ−ｍａｘ｜％ｈ）は、ｈの自然対数により与えられることが分かる。Ｍ内の２つの隣接するエントリ間に含まれないオフセットは、２つのエントリよりも小さいか、または等しいハッシュ値を有する。そのような連鎖の平均長は、漸化式ｆ（ｎ）＝１＋１／ｎ＊Σk<nｆ（ｋ）で与えられる。長さｎの区間の最長下降連鎖の平均長は、最長要素の位置から始まる最長下降連鎖の平均長よりも１大きく、最長要素は１／ｎの確率で任意の位置に見つかる。この漸化式は、調和級数Ｈn＝１＋１／２＋１／３＋１／４＋．．．＋１／ｎに対応する解を持ち、これはＨnを式の中に代入し、ｎについての帰納法を実行することにより妥当性を確認することができる。Ｈnは、ｎの自然対数に比例する。したがって、配列Ｍはサイズｈのものが割り当てられるが、サイズの小数部ｌｎ（ｈ）のみが、どの時点においても使用される。
【０１１９】
係数ｈとともにｍｉｎおよびｍａｘを計算することで、数値間の距離がｈの範囲内にある限りは、Ｍの使用される区間を任意に拡大することができる。
【０１２０】
Ｍに対する初期値の選択は、切点を第１のｈ個のオフセットの範囲内で生成できることを意味している。このアルゴリズムは、それらの最初のｈ個のオフセットでの切点を回避するように適合できる。
【０１２１】
この手順で生成されるチャンクの予想サイズは、２ｈ＋１程度である。この数値は、与えられた位置が切点である確率から求められる。ハッシュは、ｍ個の異なる可能な値を持つと仮定する。すると、この確率は以下の式で決定される。
【０１２２】
Σ0≦k<m１／ｍ（ｋ／ｍ）2h
積分∫0≦x<m１／ｍ（ｘ／ｍ）2hｄｘ＝１／（２ｈ＋１）を使用して近似を行うと、ｍが十分に大きい場合の確率が示される。
【０１２３】
この確率は、まず、総和を式
（１／ｍ）2h+1Σ0≦k<mｋ2h，
に簡略化し、これは、ベルヌーイ数Ｂkの展開を使用して、
（１／ｍ）2h+1１／（２ｈ＋１）Σ0≦k<2h（２ｈ＋１）！／ｋ！（２ｈ＋１−ｋ）！Ｂkｍ2h+1-k
にすることにより、より正確に計算することができる。
【０１２４】
ゼロでない唯一の奇数のベルヌーイ数はＢ1であり、対応する値は−１／２である。偶数のベルヌーイ数は、以下の式を満たす。
【０１２５】
Ｈ∞(2n)＝（−１）n-1２2n-1π2nＢ2n／（２ｎ）！
左辺は、無限和１＋（１／２）２ｎ＋（１／３）２ｎ＋．．．を表し、これは、ｎが控えめな値であっても、１に非常に近い。
【０１２６】
ｍがｈよりもかなり大きい場合、積分により分かるように、最初の項を除いてすべての項を無視することができる。これらは、０から１の範囲の定数により与えられ、これにｈk-1／ｍkに比例する項を掛ける。第１の項（Ｂ0＝１）は１／（２ｈ＋１）に簡約される。（第２の項は−１／（２ｍ）であり、第３の項はｈ／（６ｍ2）である）。
【０１２７】
予想されるスラックの概算について、ストリームｓ1ｓ3およびｓ2ｓ3を考慮する。ｓ1およびｓ2の内側の最後の切点は、任意の桁に出現できる。平均チャンク長は約２ｈ＋１なので、最後の切点の約１／４は、ｓ1およびｓ2内の距離ｈの範囲内にある。これらは、約７／８ｈのところで切点に寄与する。この場合の次の１／２では、一方の切点は距離ｈ内にあり、他方の切点は距離ｈを超えたところにある。これらは、３／４ｈの周りの切点に寄与する。ｓ1およびｓ2内の最後の切点の残り１／４部分は、ｈを超える距離内にある。したがって、予想されるスラックは、約１／４＊７／８＋１／２＊３／４＋１／４＊１／４＝０．６６となる。
【０１２８】
そのため、この独立のチャンキング方式の予想されるスラックは０．６６＊Ｃであり、従来技術（０．８５＊Ｃ）に比べて改善されている。
【０１２９】
高々ｈに比例するか、またはｈ内の平均で空間を使用しながら、平均して比較的少ない命令で実行することを必要とする切点を識別する他の手段がある。上記の手順では、長さｎのストリーム内に、すべての位置０．．ｎ−１に対するエントリを挿入する。代替の手順における基本的な考え方は、長さｈの区間内の上昇連鎖の要素に遭遇した場合のみ更新するというものである。平均して区間毎にｌｎ  ｈのそのような更新のみがあることが観察される。さらに、長さｈの２つの連続する区間内の局所最大値を比較することにより、２つの局所最大値のそれぞれがさらにｈ局所最大値にもなりうるかを判定することができる。代替の手順には奇妙な点が１つあるが、それは、それぞれのブロックが逆方向にトラバースされる、サイズｈのブロック単位でストリームをトラバースすることにより上昇連鎖を計算することを必要とする。
【０１３０】
他の手順（図１０および１１を参照）では、簡単のため、ハッシュのストリームは１つのシーケンスとして与えられていると仮定する。サブルーチンＣｕｔＰｏｉｎｔは、（図では「水平」に展開されている）長さｈの部分シーケンス毎に呼び出される。これは、切点であると判定された０個または１個のオフセットを返す。Ｉｎｓｅｒｔの呼び出しｌｎ（ｈ）のみが最初のテストに通る。
【０１３１】
Ａの中への挿入は、Ａでそれまでに最大のエントリと突き合わせてオフセットでのハッシュ値を検査することにより達成される。
【０１３２】
Ａ［ｋ］およびＢ［ｋ］．ｉｓＭａｘの両方を更新するループは、平均して１回の検査のみがループ本体の中で実行されるように最適化することができる。Ｂ［１］．ｈａｓｈ＜＝Ａ［ｋ］．ｈａｓｈおよびＢ［１］．ｉｓＭａｘが２つのループ内で処理される場合、それが小さくない限り第１のループでＢ［１］．ｈａｓｈと突き合わせてハッシュ値をチェックし、第２のループでＡ［ｋ］を更新する。他の場合は、Ａ［ｋ］を更新し、その後、Ｂ［１］．ｉｓＭａｘを更新するだけのループを使用して処理することができる。
【０１３３】
ＣｕｔＰｏｉｎｔを呼び出す毎に、平均してＡへのｌｎ  ｈ回のメモリ書き込み、およびループの昇降（ｈｏｉｓｔｉｎｇ）による、最大値を見つけることに関連しているｈ＋ｌｎ  ｈ回の比較を行う必要がある。Ａ［ｋ］．ｉｓＭａｘの最後の更新は、二分探索法を使用するか、または平均して高々対数ｌｎ  ｈステップでインデックス０から始まるＢをトラバースすることにより実行することができる。また、ＣｕｔＰｏｉｎｔを呼び出す毎に、更新されるウィンドウ内の最後の位置でローリングハッシュを再計算する必要がある。これは、ローリングハッシュウィンドウのサイズと同じだけのステップを要する。
【０１３４】
（改善されたチャンキングアルゴリズムの観察された利点）
最小チャンクサイズは、局所最大値および上述のフィルタ方法の両方の中に組み込まれている。従来の実装では、最小チャンクサイズを付加的パラメータと別に供給する必要がある。
【０１３５】
局所最大値（または数学）ベースの方法では、測定可能な比較的良好なスラック推定値が得られ、ネットワーク経由でさらに圧縮したものに変換される。フィルタ方法では、さらに、従来方法に比べて良好なスラック効率が得られる。
【０１３６】
新しい方法は両方とも、切点の局所性の特性を持つ。水平を越えるｓ3の内側のすべての切点は、ストリームｓ1ｓ3およびｓ2ｓ3の両方の切点となる。（つまり、ストリームｓ1ｓ3を考察し、ｐが位置≧｜ｓ１｜＋水平であり、ｐがｓ1ｓ3内の切点である場合、これはさらに、ｓ2ｓ3内の切点でもある。この同じ特性は、他の方向も保持し（対称的に）、ｐがｓ2ｓ3内の切点の場合、ｓ1ｓ3内の切点でもある）。このようなことは従来の方法にはなく、切断が何らかの最小チャンクサイズを超えるべきという要求条件は干渉し悪影響を及ぼす可能性がある。
【０１３７】
（他の数学関数）
上述のチャンキングの手順では、局所最大値計算を使用して切点を特定する手段を説明しているが、本発明はそれに限定されるわけではない。潜在的切点を調べられるように数学関数を用意することができる。それぞれの潜在的切点は、考察される切点を中心とする水平ウィンドウ内に置かれているハッシュ値を評価することにより評価される。ハッシュ値の評価は、これは、水平内の最大値を特定すること、水平内の最小値を特定すること、ハッシュ値間の差を評価すること、ハッシュ値の差異を評価すること、任意の定数と突き合わせてその結果を比較することのうちの少なくとも１つを含むことができる数学関数だけでなく、他の何らかの数学または統計関数により実行される。
【０１３８】
局所最大値についてすでに説明されている特定の数学関数は、２値述部「＿＞＿」である。ｐがオブジェクト内のオフセットである場合、ｐは、すべてのｋについて、ｐ−ｈｏｒｉｚｏｎ≦ｋ＜ｐ、またはｐ＜ｋ≦ｐ＋ｈｏｒｉｚｏｎとして、ｈａｓｈp＞ｈａｓｈkであれば切点として選択される。しかし、２値述部＞は、本発明の精神から逸脱することなく他の数学関数で置き換えることができる。
【０１３９】
（リモート差分圧縮の候補オブジェクトの検出）
上述の基本的なＲＤＣ手順の有効性は、ＲＤＣアルゴリズムのステップ４および８でシグネチャおよびチャンク再利用についてそれぞれレシーバ上の候補オブジェクトを見つけることにより高めることができる。このアルゴリズムは、装置Ａが、ＲＤＣアルゴリズムを使用して装置Ｂから転送される必要のあるオブジェクトＯBに類似のＯA1、ＯA2、．．．、ＯAnにより表されるオブジェクトの小さな部分集合を識別するのを助ける。ＯA1、ＯA2、．．．、ＯAnは、装置Ａ上にすでに格納されているオブジェクトの一部である。
【０１４０】
２つのオブジェクトＯBとＯAとの類似性は、割った２つのオブジェクトが共有する異なるチャンクの数を第１のオブジェクト内の異なるチャンクの総数で割った値に関して測定される。そのため、Ｃｈｕｎｋｓ（ＯB）およびＣｈｕｎｋｓ（ＯA）がそれぞれＲＤＣアルゴリズムのＯBおよびＯAについて計算されたチャンクの集合である場合、表記｜Ｘ｜を使用して、集合Ｘの濃度、つまり要素の個数を表すと、以下の式が得られる。
【０１４１】
【数４】
2006092558.tif 000006
【０１４２】
チャンク等式の代わりとして、チャンクのシグネチャに関する等式が使用される。これは、ハッシュ衝突の確率がきわめて低く、暗号的に安全なハッシュ関数（ＳＨＡ−１またはＭＤ５など）を使用してシグネチャを計算した場合に非常に正確である。したがって、Ｓｉｇｎａｔｕｒｅｓ（ＯB）およびＳｉｇｎａｔｕｒｅｓ（ＯA）がＲＤＣアルゴリズムのチャンキング部分の中のＯBおよびＯAについて計算されたチャンクシグネチャの集合である場合、以下の式が得られる。
【０１４３】
【数５】
2006092558.tif 000007
【０１４４】
オブジェクトＯBおよび装置Ａ上に格納されているオブジェクトＯｂｊｅｃｔｓAの集合が与えられた場合、ＯBとの類似度が与えられた閾値ｓを超えるＯｂｊｅｃｔｓAのメンバが識別される。ｓの標準的な値は、ｓ＝０．５（５０％の類似度）である、つまり、ＯBと共通のチャンクの少なくとも半分を持つオブジェクトに関心があるということである。しかし、ｓの値は、アプリケーションにとって意味のある値であればどのような値にも設定できる。例えば、ｓは０．０１から１．０（１％の類似度から１００％の類似度まで）の範囲で設定可能である。オブジェクトのこの集合は以下のように定義される。
【０１４５】
Ｓｉｍｉｌａｒ（ＯB，ＯｂｊｅｃｔｓA，ｓ）＝｛ＯA｜ＯA∈ＯｂｊｅｃｔｓA∧Ｓｉｍｉｌａｒｉｔｙ（ＯB，ＯA）≧ｓ｝
オブジェクトＯA1、ＯA2、．．．、ＯAnの集合は、最も良いｎの一致をとることによりＳｉｍｉｌａｒ（ＯB，ＯｂｊｅｃｔｓA，ｓ）の部分集合として計算される。
【０１４６】
上述の基本的なＲＤＣアルゴリズムは、類似のオブジェクトＯA1、ＯA2、．．．、ＯAnの集合を識別し、使用するように以下のように修正される。
【０１４７】
図１２に、本発明のいくつかの態様による、候補オブジェクトを見つけて使用するように修正されたＲＤＣアルゴリズムを例示する。装置Ａ上の候補オブジェクトを見つけ、使用するプロトコル、および更新されたオブジェクトＯBを装置Ｂから装置Ａに転送することについて説明する。類似のプロトコルを使用して、オブジェクトを装置Ａから装置Ｂに転送することができ、転送は、後述のプロトコルを著しく変更せずに装置Ａまたは装置Ｂのいずれかからの命令により開始できる。
【０１４８】
１．装置Ａは、ＲＤＣプロトコルを使用してオブジェクトＯBを転送する要求を装置Ｂに送信する。
【０１４９】
１．５．装置Ｂは、装置ＡにオブジェクトＯBの特性の集合Ｔｒａｉｔｓ（ＯB）を送信する。一般に、これらの特性は、オブジェクトＯBに関係する特性のコンパクトな表現である。後述のように、装置Ｂは、装置Ａに送信する前に再計算する必要がないように、ＯBの特性をキャッシュすることができる。
【０１５０】
１．６．装置ＡはＴｒａｉｔｓ（ＯB）を使用して、オブジェクトＯBに類似の、すでに格納されているオブジェクトの部分集合である、ＯA1、ＯA2、．．．、ＯAnを識別する。この決定は、確率論的に実行される。
【０１５１】
２．装置Ａは、識別されたオブジェクトＯA1、ＯA2、．．．、ＯAnを複数のチャンクに分割する。このパーティション分割は、オブジェクトのすべてのバイト位置で計算されるフィンガープリント関数を使用することによりデータに依存する形で実行される。チャンク境界は、フィンガープリント関数が所定の条件を満たす位置で決定される。チャンクへのパーティション分割に続いて、装置Ａは、各オブジェクトＯAiの各チャンクｋについてシグネチャＳｉｇAikを計算する。
【０１５２】
３．ステップ２と類似の方式を使用して、装置Ｂは、オブジェクトＯBを複数のチャンクに分割し、それらのチャンクのそれぞれについてシグネチャＳｉｇBjを計算する。ステップ３で使用されるパーティション分割アルゴリズムは、上記のステップ２のアルゴリズムと一致していなければならない。
【０１５３】
４．装置Ｂは、チャンクシグネチャのリスト（ＳｉｇB1．．．ＳｉｇBn）を装置Ａに送信する。このリストは、装置ＡでオブジェクトＯBを再構成できるための基盤となる。チャンクシグネチャＳｉｇBjに加えて、オブジェクトＯB内の各チャンクのオフセットおよび長さに関する情報が送信される。
【０１５４】
５．装置Ａが装置Ｂからチャンクシグネチャを受信すると、ステップ２で計算されたシグネチャの集合（ＳｉｇA11，．．．ＳｉｇA1m，．．．，ＳｉｇAn1，．．．ＳｉｇAn1）と突き合わせて受信されたシグネチャを比較する。この比較の一部として、装置Ａは、オブジェクトＯA1，ＯA2，．．．，ＯAnのチャンクについて計算された自シグネチャの１つＳｉｇAikと一致しない、装置Ｂから受信したすべての異なるシグネチャ値を記録する。
【０１５５】
６．装置Ａは、シグネチャが前のステップで装置Ｂから受信されたが、装置Ａ上で一致するシグネチャを持たなかったすべてのチャンクについて装置Ｂに要求を送信する。これらのチャンクは、ステップ４で送信された対応する情報に基づき、オブジェクトＯB内のオフセットおよび長さにより要求される。
【０１５６】
７．装置Ｂは、要求されたすべてのチャンクに関連付けられているコンテンツを装置Ａに送信する。
【０１５７】
８．装置Ａは、ステップ６で装置Ｂから受信されたチャンクとともに、ステップ４で装置Ｂにより送信されたシグネチャと一致したオブジェクトＯA1、ＯA2、．．．、ＯAnの自チャンクをも使用することにより、オブジェクトＯBを再構成する。この再構成ステップが完了した後、装置Ａは、次に、オブジェクトＯBの再構成されたコピーをそのすでに格納されているオブジェクトに追加することができる。
【０１５８】
ネットワークトラフィックおよびＣＰＵオーバーヘッドを最小にするために、Ｔｒａｉｔｓ（ＯB）は、非常に小さくなければならず、類似のオブジェクトＯA1，ＯA2，．．．，ＯAnの集合の決定は、装置Ａ上のごく少数の演算で実行すべきである。
【０１５９】
（オブジェクトの特性の集合の計算）
オブジェクトＯの特性の集合Ｔｒａｉｔｓ（Ｏ）は、それぞれ、ＲＤＣアルゴリズムのステップ２または３について説明されているように、Ｏについて計算されたチャンクシグネチャに基づき計算される。
【０１６０】
図１３および１４に、本発明の態様による、特性計算のプロセスおよび例を示す。
【０１６１】
類似のオブジェクトを識別するためのアルゴリズムは、以下に簡単に説明する４つの主要パラメータ（ｑ、ｂ、ｔ、ｘ）を持つ。
【０１６２】
ｑ：シングルサイズ
ｂ：特性毎のビット数
ｔ：オブジェクト毎の特性数
ｘ：一致する特性の最小個数
以下のステップは、オブジェクトＯの特性Ｔｒａｉｔｓ（Ｏ）を計算するために使用される。
【０１６３】
１．ブロック１３１０で、Ｏ、Ｓｉｇ1．．．Ｓｉｇnは、サイズｑの重なり合うシングルのグループにまとめられ、そこでは、すべてのシングルは、ｑ個未満のシグネチャを含む、最後のｑ−１個のシングルを除く、ｑ個のチャンクシグネチャを含む。他のグループ分け（不連続部分集合、非連結部分集合など）も可能であるが、付加的なシグネチャを挿入して前に考察された部分集合のすべてがそのまま考察されるようにすることが実用上有益である。
【０１６４】
２．ブロック１３２０では、各シングル１．．．ｎに対し、シングルシグネチャＳｈｉｎｇｌｅ1．．．Ｓｈｉｎｇｌｅnは、ｑ個のチャンクシグネチャを連結してシングルを形成することにより計算される。ｑ＝１の場合、Ｓｈｉｎｇｌｅ1＝Ｓｉｇ1，．．．，Ｓｈｉｎｇｌｅn＝Ｓｉｇn。
【０１６５】
３．ブロック１３３０では、シングル集合｛Ｓｈｉｎｇｌｅ1．．．Ｓｈｉｎｇｌｅn｝は、ｔ個のハッシュ関数Ｈ1．．．Ｈtを適用することによりｔ個のイメージ集合にマッピングされる。これは、以下のように、それぞれｎ個の要素を含むｔ個のイメージ集合を生成する。
【０１６６】
ＩＳ1＝｛Ｈ1（Ｓｈｉｎｇｌｅ1），Ｈ1（Ｓｈｉｎｇｌｅ2），．．．，Ｈ1（Ｓｈｉｎｇｌｅn）｝
．．．
ＩＳt＝｛Ｈt（Ｓｈｉｎｇｌｅ1），Ｈt（Ｓｈｉｎｇｌｅ2），．．．，Ｈt（Ｓｈｉｎｇｌｅn）
４．ブロック１３４０では、事前特性ＰＴ1．．．ＰＴtは、それぞれのイメージ集合の最小要素をとることにより計算される。
【０１６７】
ＰＴ1＝ｍｉｎ（ＩＳ1）
．．．
ＰＴt＝ｍｉｎ（ＩＳt）
他の決定論的数学関数も、事前特性を計算するのに使用できる。例えば、事前特性ＰＴ1．．．ＰＴtは、それぞれのイメージ集合の最大要素をとることにより計算される。
【０１６８】
ＰＴ1＝ｍａｘ（ＩＳ1）
．．．
ＰＴt＝ｍａｘ（ＩＳt）
数学的には、値を適切に順序付けられた集合に移すマッピングは、２つの単純な実現（ｒｅａｌｉｚａｔｉｏｎ）となる有界整数上の最大値および最小値を満たす。
【０１６９】
５．ブロック１３５０では、特性Ｔ1．．．Ｔtは、それぞれの事前特性ＰＴ1．．．ＰＴtからｂビットを選択することにより計算される。サンプルの独立性を保持するために、事前特性が十分に長ければ、ビットの重なり合わないスライスを、第１については０．．ｂ−１、第２についてはｂ．．２ｂ−１というように選択するのがよい。
【０１７０】
Ｔ1＝ｓｅｌｅｃｔ0..b-1（ＰＴ1）
．．．
Ｔt＝ｓｅｌｅｃｔ(t-1)b..tb-1（ＰＴt）
事前特性よりもサイズの小さい特性を作成するために、いかなる決定論的関数でも使用できる。例えば、ハッシュ関数は、結果のサイズが事前特性よりも小さい限り事前特性のそれぞれに適用することが可能であり、必要なビット総数（ｔｂ）が事前特性を超える場合、いくつかのハッシュ関数は、部分集合を選択する前にビットの数を拡大するために使用されるべきである。
【０１７１】
特性の個数ｔおよび特性サイズｂは、オブジェクトの特性を表すビットの総数（ｔ＊ｂ）が小さいものだけ選択される。これは、後述のように特性が装置Ａにより事前に計算されキャッシュされる場合には都合がよい。一実施形態によれば、適切に機能することがわかっている（ｂ，ｔ）パラメータのいくつかの典型的な組合せは、例えば、オブジェクト毎に合計９６ビットについて（４，２４）および（６，１６）である。他の組合せも使用できる。説明のために、オブジェクトＡのｉ番目の特性は、Ｔi（Ａ）で表される。
【０１７２】
（事前特性の効率的な選択）
事前特性ＰＴ1．．．ＰＴtを効率よく選択するために、以下の方式を使用し、シングルの部分評価を行って、事前特性を選択するための計算要件を低減することができる。論理的には、各Ｈiは、２つの部分ＨｉｇｈiとＬｏｗiに分割される。それぞれのイメージ集合の最小要素のみが選択されるので、Ｈｉｇｈiは、すべてのチャンクシグネチャについて計算され、Ｌｏｗiは、Ｈｉｇｈiについてこれまでに得られた最小値を与えるチャンクシグネチャについてのみ計算される。Ｈｉｇｈ値が比較的小さな空間から引き出される場合、これは計算を節約できる。さらに、いくつかのＨｉｇｈ値が１つにまとめられれば、かなりの計算を節約できる。例えば、それぞれのＨｉｇｈ値が８ビット長であると仮定する。これらのうち８つを長整数にパックすることができ、シグネチャから単一の８バイトハッシュを計算するのと引き換えに、その値を８つの独立の１バイトスライスに刻むことができる。Ｈｉｇｈ値しか必要なかった場合には、計算コストは１／８に低減される。しかし、平均２５６回に１回、対応するＬｏｗ値を計算し、等しいＨｉｇｈ値に対応する他のＬｏｗ値と比較する必要がある。
【０１７３】
（特性の集合を使用した類似のオブジェクトの検出）
このアルゴリズムは、ＯBと類似の特性を持つオブジェクトの集合を計算することにより与えられたオブジェクトＯBに類似のオブジェクトの集合を近似する。
【０１７４】
ＴｒａｉｔＳｉｍｉａｒｉｔｙ（ＯB，ＯA）＝｜｛ｉ｜Ｔi（Ａ）＝Ｔi（Ｂ）｝｜
ＳｉｍｉｌａｒＴｒａｉｔｓ（ＯB，ＯｂｊｅｃｔｓA，ｘ）＝｛ＯA｜ＯA∈ＯｂｊｅｃｔｓA∧ＴｒａｉｔＳｉｍｉｉａｒｉｔｙ（ＯB，ＯA）≧ｔ｝
これらの値を導き出せる他の計算もうまくゆく。
【０１７５】
与えられたオブジェクトＯBに最も類似しているｎ個のオブジェクトを選択するために、ＳｉｍｉｌａｒＴｒａｉｔｓ（ＯB，ＯｂｊｅｃｔｓA，ｘ）が計算され、その集合からｎ個の最も良く一致したオブジェクトが取り出される。ＳｉｍｉｌａｒＴｒａｉｔｓ（ＯB，ＯｂｊｅｃｔｓA，ｘ）のサイズがｎよりも小さい場合、集合全体が取り出される。その結果のオブジェクトの集合は、図１２に例示されている修正されたＲＤＣアルゴリズムのステップ１．６で識別されたオブジェクトＯA1，ＯA2，．．．，ＯAnの潜在的集合を形成する。実施形態によれば、オブジェクトは、類似度に従って選択することができるが、ターゲットに類似であるが、互いに似ていないオブジェクトを選択するか、または類似の特性を持つオブジェクトの集合から他の選択を行うことにより、オブジェクトの集合内の多様性を高めることを試みることもできる。
【０１７６】
一実施形態によれば、パラメータ（ｑ，ｂ，ｔ，ｘ）の組合せとして、（ｑ＝１，ｂ＝４，ｔ＝２４，ｘ＝９）および（ｑ＝１，ｂ＝６，ｔ＝１６，ｘ＝５）を使用することができる。
【０１７７】
図１５および１６は、本発明の態様により、ｂおよびｔに対するパラメータを選択する場合に使用することができる。一致を検出する確率と、まず（ｂ＝４，ｔ＝２４）に対する偽陽性とに対する曲線が図１５に示され、次に（ｂ＝６，ｔ＝１６）に対する曲線が図１６に示されている。類似度曲線（１５１０および１６１０）の両方の集合により、真の類似度が０〜１００％の範囲内にある類似のオブジェクトに対する確率論的検出を実行できる。一実施形態では、表示１５２０および１６２０に例示されている偽陽性率は、おおよそ２４のうちの１０（真の一致の４０ビットを与える）、および１６のうちの６（一致の３６ビット）程度の許容可能なレベルに低下する。ビットの必要な個数の差は、主に、より小さな集合から引き出された組合せの数が少ないことによる。大きな集合の効果（ａｄｖａｎｔａｇｅ）は、リコールの増大である。つまり、有用な一致が少ないほど気付かれず、誤って検出された一致の割合が増える。精度とリコールの両方を改善するために、ビットの総数を増やすことができる。例えば、（ｂ＝５，ｔ＝２４）に切り換えると、オブジェクト特性に対するメモリ消費量の増大と引き換えに、精度は劇的に改善される。
【０１７８】
（特性の集合に対するコンパクトな表現）
装置Ａおよび装置Ｂの両方で格納されているオブジェクトのすべてに対する特性の集合をキャッシュし、修正されたＲＤＣアルゴリズムのステップ１．６および１．５をそれぞれ実行するときに毎回その特性を再計算しなくて済むようにすると都合がよい（図１２および関連する説明を参照）。ＲＤＣ計算をスピードアップするために、特性情報を装置Ａおよび装置Ｂのメモリにそれぞれ格納することができる。
【０１７９】
後述の表現では、ｔを特性の個数、ｐをオブジェクトへの参照またはポインタを格納するために必要なバイト数としたときにオブジェクト毎にｔ＋ｐ個のメモリバイト順を使用する。参照例として、ファイルパス、ファイル識別子、またはオブジェクト識別子がある。ｔおよびｐの典型的な値に対し、この方式では、５０ＭＢ未満のメインメモリを使用して１００万個のオブジェクトをサポートすることができる。装置にさらに多くのオブジェクトを格納する場合、発見的手法を使用して類似度計算に関わるオブジェクトの個数を切り詰めることができる。例えば、非常に小さなオブジェクトは、図１２に例示されているＲＤＣアルゴリズムのステップ４および８で多くのチャンクを与えすぎるということがありえないため先験的に排除することができる。
【０１８０】
図１７に、本発明のいくつかの態様による、ＯｂｊｅｃｔＭａｐおよびｔ個の特性テーブルの集合のコンパクトな表現を構成するデータ構造を例示する。
【０１８１】
最初に、短い識別子、つまりオブジェクトＩＤがすべてのオブジェクトに割り当てられる。一実施形態では、これらの識別子は連続する非負４バイト整数であり、したがって、最大４０億個のオブジェクトを表すことができる。
【０１８２】
データ構造体（ＯｂｊｅｃｔＭａｐ）では、オブジェクトＩＤからオブジェクト参照へのマッピングを保持する。これは、装置上に格納されているオブジェクトが割り当てられたオブジェクトＩＤをどの順序で取得するかは問題でない。最初に、この割り当ては、単に格納されているオブジェクトのその装置側のリストをスキャンすることにより実行できる。オブジェクトが削除された場合、ＯｂｊｅｃｔＭａｐ内の対応するエントリは、（オブジェクト参照用に予約されている値を使用することにより）デッドエントリというマークが付けられる。オブジェクトが修正されると、ＯｂｊｅｃｔＭａｐ内の対応するエントリはデッドエントリのマークを付けられ、そのオブジェクトは、次に高い未使用オブジェクトＩＤを割り当てられる。
【０１８３】
ＯｂｊｅｃｔＭａｐがあまりにも疎らになる場合（デッドエントリの合計サイズおよび個数を追跡することにより容易に決定できる何か）、ＯｂｊｅｃｔＭａｐおよび特性テーブルは両方とも破棄され、最初から作り直される。
【０１８４】
特性テーブルは、特性番号（１からｔまで）および特性値（０から２b−１まで）から、その特定の特性を持つオブジェクトに対するオブジェクトＩＤの集合である、ＴｒａｉｔＳｅｔにマッピングする２レベルインデックスを形成する。ＴｒａｉｔＳｅｔは、新しいオブジェクトを格納するため最後にいくつかの未使用エントリを含む配列として表される。インデックスＩＸi,kは、付加できるように各ＴｒａｉｔＳｅｔ配列内の第１の未使用エントリを追跡する。
【０１８５】
ＴｒａｉｔＳｅｔ内では、オブジェクトの特定の集合がオブジェクトＩＤの昇順で格納される。オブジェクトＩＤの空間は密に保たれるため、ＴｒａｉｔＳｅｔｓ内の連続するエントリは、オブジェクトＩＤ空間内で互いに「近い」と予期することができる−平均して、２個の連続するエントリは約ｔ＊２b（ただし、少なくとも１）だけ異なるであろう。ｔ＊２b＜＜２５５となるようにｔおよびｂの値を選択した場合、連続するエントリは、図１７に示されているように、２つのオブジェクトＩＤの間の差を表す符号なしバイトを平均して１つだけ使用することにより符号化できる。２つの連続するオブジェクトＩＤが２５６以上異なる稀な場合について、０×００バイトを使用して、次に完全な４バイトオブジェクトＩＤが続くことを示すエスケープメカニズムが用意されている。
【０１８６】
異なる実施形態では、オブジェクトＩＤの差が２５６よりも小さい場合、これは、単一バイトとして表すことができ、そうでない場合、例えば「８つのうちの７つ」表現を使用することにより、後続バイトが差分−２５６を表す値０が予約される。すると、ｂ＝６の場合、差分の９８％が１バイトに収まり、９９．７％が２バイトに収まり、１０億にほとんど２つが３バイトに収まる。このスキームではオブジェクト毎に平均１．０２バイトを使用するが、それに対して、図１７に示されているスキームではオブジェクト毎に１．０８バイトを使用する。
【０１８７】
デッドオブジェクトＩＤに対応する特性テーブル内のエントリは、特性テーブル内に残すことができる。新しいエントリが末尾に付加される（インデックスＩＸ1,0．．．ＩＸt,2b-1を使用して）。
【０１８８】
（コンパクト表現を使用した類似オブジェクトの検出）
図１８に、本発明の様々な態様による類似の特性を持つオブジェクトを見つけるプロセスを例示する。一実施形態によれば、ＳｉｍｉｌａｒＴｒａｉｔｓ（ＯB，ＯｂｊｅｃｔｓA，ｘ）を計算する場合、これらのステップはマージソートアルゴリズムに似ている。このアルゴリズムでは、ＯBの少なくともｘおよびｔ個までの特性にそれぞれ一致するＯｂｊｅｃｔｓAに属しているオブジェクトを格納するために使用される（ｔ−ｘ＋１）個のオブジェクトバケット、ＯＢx．．．ＯＢtを使用する。
【０１８９】
１．ブロック１８１０で、ＯBのｔ個の特性ＴＳ1．．．ＴＳtに対応するｔ個のＴｒａｉｔＳｅｔｓを選択する。ＯＢx．．．ＯＢtを空に初期化する。インデックスＰ1．．．Ｐtを初期化して、それぞれ、ＴＳ1．．．ＴＳtの第１の要素を指すようにする。ＴＳk［Ｐk］は、Ｐkによって指されるオブジェクトＩＤの表記である。
【０１９０】
２．決定ブロック１８２０で、Ｐ1．．．ＰtのすべてがそのＴｒａｉｔＳｅｔ配列ＴＳ1．．．ＴＳtの最後の要素を越えてそれぞれ指す場合、ステップ６（ブロック１８６０）に進む。
【０１９１】
３．ブロック１８３０で、以下のように、最小オブジェクトＩＤを指すインデックスの集合であるＭｉｎＰ集合が選択される。
【０１９２】
【数６】
2006092558.tif 000008
【０１９３】
ＭｉｎＩＤをＭｉｎＰすべてのインデックスによって指される最小オブジェクトＩＤとする。
【０１９４】
４．ブロック１８４０で、ｋ＝｜ＭｉｎＰ｜とするが、これは一致する特性の個数に対応する。ｋ≧ｘであり、ＯｂｊｅｃｔＭａｐ（ＭｉｎＰ）がデッドエントリでない場合、ＭｉｎＩＤをＯＢkに付加する。
【０１９５】
５．ＭｉｎＰ内のすべてのインデックスＰkをそれぞれのＴｒａｉｔＳｅｔ配列ＴＳk内の次のオブジェクトＩＤに進める。ステップ２（ブロック１８２０）に進む。
【０１９６】
６．ブロック１８６０で、まずＯＢ1からオブジェクトを選択し、次にＯＢt-1からオブジェクトを選択し、というように、所望の個数の類似オブジェクトが選択されてしまうか、またはＯＢx内にオブジェクトが残らなくなるまで繰り返す。上記のステップで得られたオブジェクトＩＤは、ＯｂｊｅｃｔＭａｐを使用することによりオブジェクト参照に容易にマッピングすることができる。
【０１９７】
上記の明細、実施例、およびデータは、本発明の構成の製造および使用に関する完全な説明となっている。本発明の多くの実施形態は、本発明の精神と範囲を逸脱することなく実装できるため、本発明は添付の特許請求の範囲によって定められる。
【図面の簡単な説明】
【０１９８】
【図１】動作環境を例示する図である。
【図２】コンピューティング装置の例を示す図である。
【図３Ａ】ＲＤＣ手順例を示す図である。
【図３Ｂ】ＲＤＣ手順例を示す図である。
【図４Ａ】ＲＤＣ手順例を実施したときのローカル装置とリモート装置との間のやり取りに対するプロセスの流れを例示する図である。
【図４Ｂ】ＲＤＣ手順例を実施したときのローカル装置とリモート装置との間のやり取りに対するプロセスの流れを例示する図である。
【図５Ａ】ＲＤＣ手順を実施したときのやり取りの例におけるシグネチャおよびチャンク長のリストの再帰的リモート差分圧縮に対するプロセスの流れを例示する図である。
【図５Ｂ】ＲＤＣ手順を実施したときのやり取りの例におけるシグネチャおよびチャンク長のリストの再帰的リモート差分圧縮に対するプロセスの流れを例示する図である。
【図６】ＲＤＣシーケンス例における再帰的圧縮の例をグラフィックで例示する図である。
【図７】ＲＤＣ手順例を使用してクライアントおよびサーバアプリケーションのやり取りを例示する図である。
【図８】チャンキング手順例のプロセスの流れを例示する図である。
【図９】チャンキング手順例の命令コード例を示す図である。
【図１０】他のチャンキング手順例の命令コード例を示す図である。
【図１１】他のチャンキング手順例の命令コード例を示す図である。
【図１２】候補オブジェクトを見つけて使用するように修正されたＲＤＣアルゴリズムを例示する図である。
【図１３】特性計算（ｔｒａｉｔ  ｃｏｍｐｕｔａｔｉｏｎ）のプロセスおよび例を示す図である。
【図１４】特性計算のプロセスおよび例を示す図である。
【図１５】ｂおよびｔに対するパラメータを選択する際に使用できる図である。
【図１６】ｂおよびｔに対するパラメータを選択する際に使用できる図である。
【図１７】オブジェクトマップおよび特性テーブルの集合のコンパクトな表現を構成するデータ構造を例示する図である。
【図１８】本発明の様々な態様による類似の特性を計算するためのプロセスを例示する図である。
【図１】
2006092558.tif 000009
【図２】
2006092558.tif 000010
【図３Ａ】
2006092558.tif 000011
【図３Ｂ】
2006092558.tif 000012
【図４Ａ】
2006092558.tif 000013
【図４Ｂ】
2006092558.tif 000014
【図５Ａ】
2006092558.tif 000015
【図５Ｂ】
2006092558.tif 000016
【図６】
2006092558.tif 000017
【図７】
2006092558.tif 000018
【図８】
2006092558.tif 000019
【図９】
2006092558.tif 000020
【図１０】
2006092558.tif 000021
【図１１】
2006092558.tif 000022
【図１２】
2006092558.tif 000023
【図１３】
2006092558.tif 000024
【図１４】
2006092558.tif 000025
【図１５】
2006092558.tif 000026
【図１６】
2006092558.tif 000027
【図１７】
2006092558.tif 000028
【図１８】
2006092558.tif 000029