(57)【要約】【課題】【解決手段】  システム及び方法は、リモート端末に向けて送信すべき更新データセットを生成する。更新データセットは、リモート端末が古いデータセットをより新しいデータセットに変換できるように、２つのデータセット間の差分を記述する演算子を含む。システムは、データセット内のデータ要素を比較するコンパレータと、メモリに格納された変更パラメータに基づいて演算子を選択するセレクタとを含む。【選択図】  図１
2010514035.tif 000002
【特許請求の範囲】
【請求項１】
リモート端末に向けて送信すべき更新データセットを生成するコンピュータシステムであって、前記更新データセットは、ソート済みのデータ要素を含む第１のデータセットとソート済みのデータ要素を含む第２のデータセットとの差分を記述する演算子を含み、
前記コンピュータシステムは、
前記第１のデータセット及び前記第２のデータセットを含むメモリと、
前記メモリに接続可能なコンパレータであって、前記第２のデータセット内のデータ要素と前記第１のデータセット内のデータ要素とを順次比較し、先の比較結果が、前記第１のデータセット内のどのデータ要素と前記第２のデータセット内のどのデータ要素が次の比較において比較されるかを制御し、各比較の後に前記メモリ内の変更パラメータを更新し、前記第２のデータセット内のデータ要素が前記第１のデータセット内のデータ要素に一致することを検出するとセレクタを起動するコンパレータと、
前記メモリ内に格納された前記変更パラメータに基づいて演算子を決定し、前記メモリ内に前記決定した演算子を格納する前記メモリ及び前記コンパレータに接続可能なセレクタと
を含み、
前記第２のデータセット及び前記第１のデータセットの差分を記述する演算子を含む前記リモート端末に送信すべき更新データセットを生成する
ことを特徴とするコンピュータシステム。
【請求項２】
前記更新データセットを含む更新メッセージを生成及び送信するセレクタに関連するコミュニケータ
を更に含むことを特徴とする請求項１記載のコンピュータシステム。
【請求項３】
前記第１のデータセット及び前記第２のデータセットは、
時間とともに変化する動的データ要素
を含むことを特徴とする請求項１記載のコンピュータシステム。
【請求項４】
前記第２のデータセットは、
前記第１のデータセットよりも新しいバージョンである
ことを特徴とする請求項１記載のコンピュータシステム。
【請求項５】
前記演算子は、
追加演算子、削除演算子、置換演算子を含むグループから決められる
ことを特徴とする請求項１記載のコンピュータシステム。
【請求項６】
前記変更パラメータは、
前記第１のデータセットに関連する第１のカウンタと、前記第２のデータセットに関連する第２のカウンタとを含む
ことを特徴とする請求項１記載のコンピュータシステム。
【請求項７】
前記セレクタは、
前記第１のデータセットに関連する前記第１のカウンタと、前記第２のデータセットに関連する前記第２のカウンタとの関係に基づいて演算子を選択する
ことを特徴とする請求項６記載のコンピュータシステム。
【請求項８】
前記変更パラメータは、
前記第１のデータセット及び前記第２のデータセット内の前記コンパレータの位置の追跡を維持するために、前記第１のデータセットに関連する第１の位置パラメータと、前記第２のデータセットに関連する第２の位置パラメータとを更に含む
ことを特徴とする請求項１記載のコンピュータシステム。
【請求項９】
前記演算子は、差分変更を含む
ことを特徴とする請求項１記載のコンピュータシステム。
【請求項１０】
各データ要素は、キー及びデータ部分を含む
ことを特徴とする請求項１記載のコンピュータシステム。
【請求項１１】
請求項１に係わるコンピュータシステムを含む電子商取引システム。
【請求項１２】
リモート端末に向けて送信すべき更新データセットを生成する方法であって、前記更新データセットは、ソート済みのデータ要素を含む第１のデータセットとソート済みのデータ要素を含む第２のデータセットとの差分を記述する演算子を含み、
前記方法は、
前記第１のデータセット内のデータ要素と前記第２のデータセット内のデータ要素とを順次比較するステップであって、先の比較結果が、前記第１のデータセット内のどのデータ要素と前記第２のデータセット内のどのデータ要素が次の比較において比較されるかを制御するステップと、
各比較の後にメモリ内の変更パラメータを更新するステップと、
前記第２のデータセット内のデータ要素が前記第１のデータセット内のデータ要素に一致することを検出すると、前記メモリに格納された前記変更パラメータに基づいて演算子を決定する選択処理を開始するステップと、
前記決定された演算子を前記メモリに格納するステップと
を含み、
前記第１のデータセット及び前記第２のデータセットの差分を記述する演算子を含む前記リモート端末に送信すべき更新データセットを生成する
ことを特徴とする方法。
【請求項１３】
前記決定された演算子と比較済みのデータ要素とを関連付けるステップ
を更に含むことを特徴とする請求項１２記載の方法。
【請求項１４】
追加演算子、削除演算子、置換演算子を含むグループから少なくとも１つの演算子を決定するステップ
を更に含むことを特徴とする請求項１２記載の方法。
【請求項１５】
前記変更パラメータは、
前記第１のデータセットに関連する第１のカウンタと、前記第２のデータセットに関連する第２のカウンタと
を含み、
前記第１のデータセットに関連する前記第１のカウンタと、前記第２のデータセットに関連する前記第２のカウンタとの関係に基づいて演算子を決定するステップ
を更に含むことを特徴とする請求項１２記載の方法。
【請求項１６】
各データ要素は、キー及びデータ部分を含み、
前記第１のデータセットの要素のキー及びデータ部分の少なくとも１つと、前記第２のデータセットの要素のキー及びデータ部分の少なくとも１つとを比較するステップ
を更に含むことを特徴とする請求項１２記載の方法。
【請求項１７】
前記第１のデータセット及び前記第２のデータセットは、時間とともに変化する動的情報を含む
ことを特徴とする請求項１２記載の方法。
【請求項１８】
記憶媒体に格納される請求項１２に係わるコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ環境におけるデータ配布に関し、特に、コンピュータネットワーク内の変更の配布用データセットにおける変更の抽出に関する。
【背景技術】
【０００２】
今日、ごく一般的に、コンピュータネットワークを介したデータの送信が行なわれている。技術の進歩により送信データ量が急激に増加している。この技術の進歩は、従来に比べてより速い速度でより多くのデータの送信及び処理を可能にしている。また更に、新たなアプリケーションは、より複雑になり、より多くのデータを必要とする。データ配布技術が最も不可欠な部分の一つであるコンピュータシステムの例として、電子商取引システムがある。
【０００３】
電子商取引における証券、デリバティブ、コモデティやその他の金融商品においては、ユーザに向けて配布する必要のあるデータが大量となっている。これは、取引の決定、統計的計算やその他アセスメントを行なうために、ユーザがデータを必要とするためである。高いパフォーマンスのコンピュータシステムにおいて、この情報全てを抽出及び送信する処理は、プロセッサへの要求が極めて高くなる。ＣＰＵ時間の量は、回避されうる実行ステップにおいて、無駄にすべきでないわずかなリソースである。
【０００４】
更に、中央集権化商取引等に接続するユーザは、一般に、できる限り速く情報の取得を所望する。このようなケースにおいては、例えば、ハードウェアの更新により中央システムのパフォーマンスを上げるだけでは十分ではない場合がある。
【０００５】
システム内において、ボトルネック又は他のレイテンシの問題を取り除くために、更なる技術が用いられる必要がある。
【０００６】
ここで、プロセッサの処理をより効率化するための更なる技術の一つとして、例えば、ユーザ端末側でのデータセットの更新時に種々の手法が存在する。
【０００７】
一般的に使用され且つ明らかな解決策としては、古いデータセットを置換する完全な新しいデータセットを常に送信する。この場合、データセットにおけるデータの一部のみが変更される時には非効率である。そのため、より効率的な手法では、変更されるデータセットの部分のみを送信する場合がある。更なる効率化では、差分変更（delta change）を送信する。
【０００８】
他の周知の技術では、２つのデータセット間の差分を記述する演算子（operator）を送信する。第１のデータセットにおける演算子を適用することにより、当該第１のデータセットを第２のデータセットに変換する。
【０００９】
データセットに作用する演算子の良好なセットの選択とともに最適化が行なえる。現在、データセット差分を抽出するのに利用できる方法は質が悪い。
【００１０】
従って、ステップ数をより少なくする等、効率的な方法で演算子の抽出や選択を行なう技術や、プロセッサにかかる負荷を減らすため、コンピュータシステム内の帯域幅等のデータ配布を減らす技術の構築が必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
そこで、本発明は、リモート端末に向けて送信すべき更新データセットを生成するための解決策を提供することを目的とする。
【００１２】
本発明は、データセットから効率的にデータを抽出する解決策を提供することを他の目的とする。
【００１３】
本発明は、データセット間の差分に基づいて、演算子の抽出及び選択の少なくとも１つを効率的に行なう解決策を提供することを他の目的とする。
【００１４】
本発明は、リモート端末に向けて送信すべきデータ構成を生成する解決策を提供することを他の目的とする。
【００１５】
本発明は、プロセッサ時間をより少なくするのに使用する解決策を提供することを他の目的とする。
【課題を解決するための手段】
【００１６】
本発明の第１の側面によれば、上記及び他の目的をコンピュータシステムにより解決する。コンピュータシステムは、リモート端末に向けて送信すべき更新データセットを生成する。更新データセットは、ソート済みのデータ要素を含む第１のデータセットとソート済みのデータ要素を含む第２のデータセットとの差分を記述する演算子を含む。コンピュータシステムは、
第１のデータセット及び第２のデータセットを含むメモリと、
メモリに接続可能なコンパレータであって、第２のデータセット内のデータ要素と第１のデータセット内のデータ要素とを順次比較し、先の比較結果が、第１のデータセット内のどのデータ要素と第２のデータセット内のどのデータ要素が次の比較において比較されるかを制御し、各比較の後にメモリ内の変更パラメータを更新し、第２のデータセット内のデータ要素が第１のデータセット内のデータ要素に一致することを検出するとセレクタを起動するコンパレータと、
メモリ内に格納された変更パラメータに基づいて演算子を決定し、メモリ内に決定した演算子を格納するメモリ及びコンパレータに接続可能なセレクタと
を含み、
第２のデータセット及び第１のデータセットの差分を記述する演算子を含むリモート端末に送信すべき更新データセットを生成する。
【００１７】
コンピュータシステムは、商取引システム等のコンピュータシステムが、より少ないＣＰＵ時間を用いて更新データセットをより効率的に生成することを可能にするという利点を有する。例えば、コンピュータシステムは、各データセットを介した１度のみの実行により、好ましい第１のデータセット及び第２のデータセットの比較を可能にする。
【００１８】
更に、コンピュータシステムは、更新データセットを含む更新メッセージを生成及び送信するセレクタに関連するコミュニケータを含む。メッセージは、リモート端末に向けて送信すべきデータセットを含むリスト、配列、ビットボード、スタック、ヒープ、木又はコレクション、その他等のデータ構成を含む。好ましくは、メッセージはＦＩＸ基準を用いて送信されるが、Ｏｍｎｅｔ ＡＰＩ、ＸＴＰ、ＳＳＬ又は他の任意の基準等の当業者がメッセージ送信に使用する周知の任意の他のプロトコル、又は独自仕様のプロトコルであってもよい。
【００１９】
好ましくは、第１のデータセット及び第２のデータセットは、時間とともに変化する動的データ要素を含む。例えば、第１のデータセットは、時刻Ｔ１での商取引システムにおけるオーダー・ブック（order book）であり、第２のデータセットは、時刻Ｔ２でのオーダー・ブックであってもよい。販売金融商品に関する購入又は売り出しといった新たなオーダーが入力される可能性があるため、オーダー・ブック内のデータは、時刻Ｔ１とＴ２との間で変更される可能性がある。情報配布システムは、ある所定時間間隔か又はオーダー・ブック内のアクティブ時かのいずれかにおいて、リモート端末に向けて情報を配布してもよい。例えば、オーダー・ブックが新たなオーダを全く受信しなければ、リモート端末に向けて新たな更新を送信することは意味がない。しかし、新たなオーダーがオーダー・ブックに入力された場合、新たな情報は、リモート端末に伝播される必要がある。更に、アクティブが発生した時点において、更新メッセージを送信する必要がある。他の例では、オーダー・ブック内で生じる変更が状態遷移している間、例えば、オーダー・ブックが開く又閉じられたときである。
【００２０】
従って、第２のデータセットは、第１のデータセットよりも新しいバージョンである。このように中央システムは、生じた変更を比較でき、リモート端末の有するデータセットを把握できるので、格納及び送信するための演算子を更新データセット内から抽出できる。また更に、リモート端末側のユーザがデータセットの異なる部分に関する情報の取得を所望する場合があるので、第１のデータセット及び第２のデータセットの間の変更の確実な部分を特定のリモート端末に向けて送信することを可能にする。
【００２１】
好ましくは、演算子は、追加演算子（Add operator）、削除演算子（Delete operator）、置換演算子（Replace operator）を含むグループから決められる。変更パラメータに基づいてこれら演算子を決定することにより、更新データセットの生成が可能になる。演算子は、本明細書で後述する組み合わせがなされてもよい。
【００２２】
変更パラメータは、好ましくは、第１のデータセットに関連する第１のカウンタと、第２のデータセットに関連する第２のカウンタとを含む。このようにして選択処理は、より正確な方法でモニタ及び管理されうる。更に、セレクタは、第１のデータセットに関連する第１のカウンタと、第２のデータセットに関連する第２のカウンタとの関係に基づいて演算子を決定する。その関係は、＞、＜、＝、≧、≦又は≠を含む関係群の中から選択された関係であるため、これにより、選択処理が高速化する。カウンタ間の関係に基づいて、追加（Add）、削除（Delete）、置換（Replace）等の演算子の少なくとも１つに決められる。
【００２３】
更に、変更パラメータは、第１のデータセット及び第２のデータセット内におけるコンパレータの論理位置の追跡を維持するために、第１のデータセットに関連する第１の位置パラメータと、第２のデータセットに関連する第２の位置パラメータとを含む。このように第１のリスト及び第２のリストを順次比較した結果は、より正確な方法でモニタ及び管理されうる。
【００２４】
演算子は、差分変更を含む。従って、データ要素の一部のみが変更したのであれば、変更したデータ要素の当該部分を記述する演算子であってもよい。しかし、演算子は、例えば、削除、置換又は追加されるべきデータ要素全てを記述できてもよい。
【００２５】
各データ要素は、通常、少なくともキーを含む。しかし、データ要素は、データ部分を含んでもよい。一般に、データ部分は、空であってもよい。しかし、商取引システムにおいて、一般的なキーは、オーダー・ブック内における値段である。データ部分は、例えば、その値段の合計額であってもよい。しかし、キーが値段及び時間（time）を含むのであれば、全てのキーを送信することは必ずしも必要ではない。要素のソートは、値段及び時間に基づいて行なわれる場合もあるが、リモート端末に向けて送信される値段のみに基づいて行なわれてもよい。
【００２６】
本発明の第２の側面においては、電子商取引システムにより上記及び他の目的を解決する。電子商取引システムは、上述したコンピュータシステムを含む。
【００２７】
コンピュータシステムは、電子商取引システム内における内蔵モジュールであってもよい。また、情報抽出システムとして別々に販売されうるスタンドアローンモジュールであってよい。
【００２８】
本発明の第３の側面においては、方法により上記及び他の目的を解決する実現する。方法は、リモート端末に向けて送信すべき更新データセットを生成する。更新データセットは、ソート済みのデータ要素を含む第１のデータセットとソート済みのデータ要素を含む第２のデータセットとの差分を記述する演算子を含む。方法は、
第１のデータセット内のデータ要素と第２のデータセット内のデータ要素とを順次比較するステップであって、先の比較結果が、第１のデータセット内のどのデータ要素と第２のデータセット内のどのデータ要素が次の比較において比較されるかを制御するステップと、
各比較の後にメモリ内の変更パラメータを更新するステップと、
第２のデータセット内のデータ要素が第１のデータセット内のデータ要素に一致することを検出すると、メモリに格納された変更パラメータに基づいて演算子を決定する選択処理を開始するステップと、
決定された演算子をメモリに格納するステップと
を含み、
第１のデータセット及び第２のデータセットの差分を記述する演算子を含むリモート端末に送信すべき更新データセットを生成する。
【００２９】
方法は、商取引システム等のコンピュータシステムが、より少ないＣＰＵ時間を用いて更新データセットをより効率的に生成することを可能にするという利点を有する。本発明は、例えば、各データセットを介した１度のみの実行により、好ましい第１のデータセット及び第２のデータセットの比較を可能にする。
【００３０】
更に、方法は、決定された演算子と比較済みのデータ要素とを関連付けるステップを含む。このようにシステムは、演算子が使用されるべきデータ要素での追跡の維持を可能にする。
【００３１】
また、方法は、追加演算子、削除演算子、置換演算子を含むグループから少なくとも１つの演算子を決定するステップを含む。変更パラメータに基づいてこれら演算子を決定することにより、更新データセットの生成が可能になる。演算子は、本明細書で後述する組み合わせがなされてもよい。
【００３２】
上述した変更パラメータは、第１のデータセットに関連する第１のカウンタと、第２のデータセットに関連する第２のカウンタとを含んでもよい。従って、方法は、第１のデータセットに関連する第１のカウンタと、第２のデータセットに関連する第２のカウンタとの関係に基づいて演算子を決定するステップを更に含んでもよい。
【００３３】
好ましくは、各データ要素は、キー及びデータ部分を含む。方法は、第１のデータセットの要素のキー及びデータ部分の少なくとも１つと、第２のデータセットの要素のキー及びデータ部分の少なくとも１つとを比較するステップを更に含む。
【００３４】
上述した第１のデータセット及び第２のデータセットは、時間とともに変化する動的情報を含んでもよい。
【００３５】
本発明の第４の側面においては、コンピュータプログラム製品により上記及び他の目的を解決する。コンピュータプログラム製品は、上述した側面及び実施形態の少なくとも１つに係わり、記憶媒体に格納される。
【００３６】
本発明のこれら及び他の側面は、後述する実施形態を参照して明白及び明確に示されるであろう。
【図面の簡単な説明】
【００３７】
【図１】本発明で用いられるコンピュータネットワークの概要の一例を示す図である。
【図２】メモリ、第１のデータセット、第２のデータセット、変更パラメータ、コンパレータ、セレクタ、更新データセット、インターフェースを含む電子装置を示す図である。
【図３】データ要素を含むデータセットとキー及びデータを含むデータ要素とを示す図である。
【図４】テキストに記載されるデータセットを反復するアルゴリズムを示す図である。
【図５】データセットＡ及びデータセットＢを示す図である。
【図６】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図７】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図８】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図９】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１０】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１１】選択方法により選択された第１の演算子を示す図である。
【図１２】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１３】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１４】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１５】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１６】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１７】データセットＡの要素とデータセットＢの要素との比較の一例を示す図である。
【図１８】選択方法により選択された更なる演算子を示す図である。
【図１９】選択方法により選択された演算子を含む更新データセットの一例を示す図である。
【図２０】演算子が使用されるより以前のデータセットＡ及びデータセットＢを示す図である。
【図２１】更新データセットにおける列の一例を示す図である。
【図２２】第１の演算子を適用した後のデータセットＡの変更を示す図である。
【図２３】更新データセットにおける列の一例を示す図である。
【図２４】第２の演算子を適用した後のデータセットＡの変更を示す図である。
【図２５】更新データセットにおける列の一例を示す図である。
【図２６】第３の演算子を適用した後のデータセットＡの変更を示す図である。
【図２７】更新データセットにおける列の一例を示す図である。
【図２８】第４の演算子を適用した後のデータセットＡの変更を示す図である。
【図２９】演算子がデータセットＡに適用された後の結果を示す図である。
【図３０】選択方法Ｂを示す図である。
【発明を実施するための形態】
【００３８】
図１は、リモート端末１と、中央コンピュータ２と、ゲートウェイ又はルータ３とを含むコンピュータネットワークを示す。各装置間は、種々の太さを有するライン４により示される接続がなされている。ラインの太さは、帯域幅（データレート）を示す。太いラインは高いデータレートを有し、細いラインは低いデータレートを有している。図１に示す３つのフロントエンドコンピュータは、画面上に文字を有しており、この文字は、ユーザＡ、ユーザＢ、ユーザＣに属するリモート端末であることを示している。更新データセット６は、ライン４と、ルータや外部等のネットワーク装置とを含むネットワークを介して、中央コンピュータ２からリモート端末１に向けて送信される。更新データセット６は、本発明に係わるコンピュータシステム５において生成される。
【００３９】
図２は、本発明に係わるコンピュータシステム５を示す。コンピュータシステム５は、メモリ１０と、コンパレータ１４と、セレクタ１５と、更新データセット７を送信するためのインターフェース１６とを含む。メモリ１０は、第１のデータセット１１及び第２のデータセット１２を含む。更に、メモリは、変更パラメータ１３と、更新データセット７と、演算子１８とを格納するための領域を含む。
【００４０】
図３は、データセット１１と、データセットにおけるデータ要素１７の拡大とを示す。図中データ要素１７は、キーとデータ部分との両方を含んでいるが、本発明の他の実施形態においては、データ要素１７は、キー部分を少なくとも含んでいればよい。
【００４１】
以下、図を参照して本発明の詳細について説明する。演算子がどのようにして決定／選択されるかの詳細について説明する。
【００４２】
以下、２つのデータセット間の差分を効率的に記述する演算子を選択するための方法の一例を示す。
【００４３】
データセットは、１又は複数の要素から構成される。各要素は、キーと、可能であればデータ部分とを有する。キーは、データセット内の要素各々に論理位置を与えるソートアルゴリズムと対応付けられる。
【００４４】
この方法は、１）及び２）に基づく：
１）演算子の効率的なセットの策定
２）２つのデータセットの差分を評価し、演算子のセットを用いて当該差分を記述する効率的なアルゴリズムの策定。これを実現するため、アルゴリズムは、２つのデータセットのワン−パス・トラバース（one-pass traverse）を使用する。
【００４５】
この方法は、下記に示す２つのデータセット間における変更を記述する演算子のセットを使用する：
2010514035.tif 000003
【００４６】
[方法紹介]
２つのデータセット内で一致する要素（キー及びデータ部分の両方）は変わらない。アルゴリズムは、変わらない要素をバリア（barrier）とみなす。バリアは、演算子の最適化が実行されうる時点を識別するために上記方法により使用される。当該方法は、監視に基づいており、バリアが検出される前に使用された演算子に関して最適化が可能になる。
【００４７】
図５を参照してデータセットＡ及びデータセットＢを想定してみる。まず、データセットＡでは、複数の演算子がデータセットＢを獲得するのに適用されうる。以下に示すアルゴリズム及び方法は、データセットＡをデータセットＢに変換するこれら演算子を抽出する。
【００４８】
データセットのトラバースの間、好ましくは、以下に示すカウンタ、＃Ｄｅｌ及び＃Ａｄｄが使用される。これらには、最初に、０又は同じ目的を果たす任意の値が設定される。
【００４９】
その後、データセットＡ及びデータセットＢは、キーのソート順番に従って、好ましくは開始からトラバースされる。
【００５０】
データセットＡ内における実際の論理位置は、以降、Ａｐｏｓと名付けられる。Ａｐｏｓは、データセットＡに関する位置パラメータを含む。データセットＢ内における実際の論理位置は、以降、Ｂｐｏｓと名付けられる。Ｂｐｏｓは、データセットＢに関する位置パラメータを含む。Ａｐｏｓ及びＢｐｏｓは、最初に、データセットＡ及びデータセットＢ内における最初の論理位置に設定される。
【００５１】
初期化：
＃Ａｄｄ及び＃Ｄｅｌに対して０を設定する。
Ａｐｏｓ及びＢｐｏｓに対してデータセットＡ及びデータセットＢ内における最初の論理位置を設定する。
ＡｐｏｓＳｔａｒｔに対してＡｐｏｓを設定し、ＢｐｏｓＳｔａｒｔに対してＢｐｏｓを設定する。
【００５２】
アルゴリズム：データセットＡ及びデータセットＢを反復し、＃Ａｄｄ及び＃Ｄｅｌをカウントする：
１．論理位置Ａｐｏｓ及びＢｐｏｓにおいて、セットＡの要素とセットＢの要素とを比較する。
ａ．Ａ要素及びＢ要素がなければ、以下に示す方法Ｂを用いて演算子を選択し、ステップ２を継続する（完了）。
ｂ．キーは一致するがデータ部分が異なれば、＃Ａｄｄ、＃Ｄｅｌ、Ａｐｏｓ、Ｂｐｏｓを１増加する。ステップ１を継続し、次の要素を比較する。
ｃ．Ａ要素キーがＢ要素キーよりも（ソート順に照らして）悪い、又はＡ要素がなければ、＃Ａｄｄ及びＢｐｏｓを１増加する。ステップ１を継続し、次の要素を比較する。
ｄ．Ａ要素キーがＢ要素キーよりも（ソート順に照らして）良い、又はＢ要素がなければ、＃Ｄｅｌ及びＡｐｏｓを１増加する。ステップ１を継続し、次の要素を比較する。
ｅ．キー及びデータ部分の両方が一致すれば、バリアが発見される。（＃Ａｄｄ≠０又は＃Ｄｅｌ≠０）であれば、以下に示す方法Ｂを用いて演算子を選択する。
継続：
＃Ａｄｄ及び＃Ｄｅｌに対して０を設定する。
＃Ａｐｏｓ及びＢｐｏｓを１増加する。
ＡｐｏｓＳｔａｒｔにＡｐｏｓ、ＢｐｏｓＳｔａｒｔにＢｐｏｓを設定する。
ステップ１を継続し、次の要素を比較する。
【００５３】
２．完了
方法Ｂ：演算子の選択：＃Ｄｅｌと＃Ａｄｄとを比較。
ａ．＃Ｄｅｌが＃Ａｄｄを越えていれば、以下の演算子を選択する。
論理位置ＡｐｏｓＳｔａｒｔにおいて、（Ｎ＝＃Ｄｅｌ）演算子を削除する。
続いて以下を行なう：
論理位置ＡｐｏｓＳｔａｒｔから開始し、セットＢ要素から＃Ａｄｄ数の演算子を追加する。
ｂ．＃Ｄｅｌと＃Ａｄｄとが等しければ、以下の演算子を選択する。
論理位置ＡｐｏｓＳｔａｒｔから開始し、セットＢ要素から＃Ａｄｄ数の演算子を置換する。
ｃ．＃Ｄｅｌが＃Ａｄｄよりも小さければ、以下の演算子を選択する。
ＡｐｏｓＳｔａｒｔ＋＃Ｄｅｌから開始し、セットＢ要素から（＃Ａｄｄ−＃Ｄｅｌ）数の演算子を追加する。
【００５４】
[例]
以下、図を参照して種々の方法ステップの一例について説明する。
図５に示すテーブルに従って、データセットＡ及びデータセットＢを想定する。要素は、好ましくは、キーに基づいてソートされ、その結果、論理位置１において最も高い値が得られる。データセットＡは古いデータセットを示し、データセットＢは新しいデータセットを示す。このタスクは、データセットＡをデータセットＢに変換することである。
【００５５】
[方法の実行]
初期化：
＃Ａｄｄ及び＃Ｄｅｌに対して０を設定する。
Ａｐｏｓ及びＢｐｏｓに対してデータセットＡ及びデータセットＢ内における最初の論理位置を設定する。
Ａｐｏｓ及びＢｐｏｓに１を設定する。
ＡｐｏｓＳｔａｒｔにＡｐｏｓを設定し、ＢｐｏｓＳｔａｒｔにＢｐｏｓを設定する。
ＡｐｏｓＳｔａｒｔ及びＢｐｏｓＳｔａｒｔに１を設定する。
【００５６】
方法及びシステムは、カウンタの初期化を開始する。カウンタは、好ましくは、データセットの反復に使用されるであろう。
【００５７】
その後、反復フェーズが開始される。反復フェーズでは、変更パラメータ＃Ａｄｄ及び＃Ｄｅｌが反復及び増加される。
【００５８】
[ステップ１]
セットＡの要素とセットＢの要素とを比較する。Ａｐｏｓ及びＢｐｏｓには、両方１が設定されるので、これは、リストにおける１番目の要素が比較されることを意味する。しかし、データセットにおける要素が他の方法でソートされていれば、この方法では、まず、他の要素の比較を開始する場合もある。図６にこの比較を示す。この場合、９９は１０１よりも悪い（アルゴリズムステップｃ参照）（データセットＡの要素（Ａｐｏｓ＝１）は、データセットＢの要素（Ｂｐｏｓ＝１）よりも悪い）。そのため、＃Ａｄｄを１増加し、＃Ａｄｄに１を設定する。Ｂｐｏｓを１増加し、Ｂｐｏｓに２を設定する。アルゴリスムにおけるステップ１を継続し、次の要素を比較する。
【００５９】
[ステップ２]
セットＡの要素とセットＢの要素とを比較する。ここでは、Ｂｐｏｓカウンタが１増加しているため、データセットＡの（Ａｐｏｓ＝１）における要素と、データセットＢの（Ｂｐｏｓ＝２）における要素とが比較される。この比較を図７に示す。９９は１００よりも悪い（アルゴリズムステップｃ参照）。そのため、＃Ａｄｄを１増加し、＃Ａｄｄに２を設定する。Ｂｐｏｓを１増加し、Ｂｐｏｓに３を設定する。アルゴリスムにおけるステップ１を継続し、次の要素を比較する。
【００６０】
[ステップ３]
上記同様に、セットＡの要素とセットＢの要素とを比較する。この比較を図８に示す。９９は９７よりも良い（アルゴリズムステップｄ参照）。そのため、＃Ｄｅｌを１増加し、＃Ｄｅｌに１を設定する。Ａｐｏｓを１増加し、Ａｐｏｓに２を設定する。アルゴリスムにおけるステップ１を継続し、次の要素を比較する。
【００６１】
[ステップ４]
セットＡの要素とセットＢの要素とを比較する。この比較を図９に示す。９８は９７よりも良い（アルゴリズムステップｄ参照）。そのため、＃Ｄｅｌを１増加し、＃Ｄｅｌに２を設定する。Ａｐｏｓを１増加し、Ａｐｏｓに３を設定する。アルゴリスムにおけるステップ１を継続し、次の要素を比較する。
【００６２】
[ステップ５]
セットＡの要素とセットＢの要素とを比較する。この比較を図１０に示す。キー及びデータ部分の両方が一致するため（アルゴリズムステップｅ参照）、バリアに到達している。セレクタを起動し、方法Ｂを用いて演算子を選択する。
【００６３】
[ステップ６]
＃Ｄｅｌと＃Ａｄｄとを比較する。方法Ｂによれば、ステップｂが、この状況：（ｂ）に適用される。＃Ｄｅｌ（２）＝＃Ａｄｄ（２）であるので、下記に示す演算子を選択する：
置換（Ｒｅｐｌａｃｅ）２（＃Ａｄｄ）演算子、セットＢからデータを選択し、論理位置ＡｐｏｓＳｔａｒｔ＝１から開始する。選択された演算子を図１１に示す。
【００６４】
[ステップ７]
データセットＡ及びデータセットＢにおける要素の反復及び比較は継続する。
＃Ａｄｄ及び＃Ｄｅｌに対して０を設定する。
バリアを通り抜けるため、カウンタが増加される。Ａｐｏｓ及びＢｐｏｓが１増加され、Ａｐｏｓ及びＢｐｏｓに４が設定される。
ＡｐｏｓＳｔａｒｔにＡｐｏｓ、ＢｐｏｓＳｔａｒｔにＢｐｏｓを設定し、ＡｐｏｓＳｔａｒｔ及びＢｐｏｓＳｔａｒｔに４を設定する。
アルゴリズムにおけるステップ１を継続し、次の要素を比較する。
【００６５】
[ステップ８]
セットＡの要素とセットＢの要素とを比較する。この比較を図１２に示す。９６は９３よりも良い（アルゴリズムステップｄ参照）。そのため、＃Ｄｅｌに１増加し、＃Ｄｅｌに１を設定する。Ａｐｏｓを１増加し、Ａｐｏｓに５を設定する。アルゴリズムにおけるステップ１を継続し、次の要素を比較する。
【００６６】
[ステップ９]
セットＡの要素とセットＢの要素とを比較する。この比較を図１３に示す。９５は９３よりも良い（アルゴリズムステップｄ参照）。そのため、＃Ｄｅｌに１増加し、＃Ｄｅｌに２を設定する。Ａｐｏｓを１増加し、Ａｐｏｓに６を設定する。アルゴリズムにおけるステップ１を継続し、次の要素を比較する。
【００６７】
[ステップ１０]
セットＡの要素とセットＢの要素とを比較する。この比較を図１４に示す。９４は９３よりも良い（アルゴリズムステップｄ参照）。そのため、＃Ｄｅｌに１増加し、＃Ｄｅｌに３を設定する。Ａｐｏｓを１増加し、Ａｐｏｓに７を設定する。アルゴリズムにおけるステップ１を継続し、次の要素を比較する。
【００６８】
[ステップ１１]
セットＡの要素とセットＢの要素とを比較する。この比較を図１５に示す。キーは一致するが、データ部分が異なる（１０は、１５と等しくない）（アルゴリズムステップｂ参照）。
＃Ａｄｄを１増加し、＃Ａｄｄに１を設定する。
＃Ｄｅｌを１増加し、＃Ｄｅｌに４を設定する。
Ａｐｏｓを１増加し、Ａｐｏｓに８を設定する。
Ｂｐｏｓを１増加し、Ｂｐｏｓに５を設定する。
アルゴリズムにおけるステップ１を継続し、次の要素を比較する。
【００６９】
[ステップ１２]
セットＡの要素とセットＢの要素とを比較する。この比較を図１６に示す。Ｂ要素がない（空である）（アルゴリズムステップｄ参照）。
＃Ｄｅｌを１増加し、＃Ｄｅｌに５を設定する。Ａｐｏｓを１増加し、Ａｐｏｓに９を設定する。アルゴリズムにおけるステップ１を継続し、次の要素を比較する。
【００７０】
[ステップ１３]
セットＡの要素とセットＢの要素とを比較する。この比較を図１７に示す。Ａｐｏｓ（９）におけるデータセットＡの要素と、Ｂｐｏｓ（５）におけるデータセットＢの要素とが空となる。そのため、アルゴリズムのステップａが適用される。アルゴリズムにおけるステップａは、セレクタを起動する。ステップ１４に示されている方法Ｂである。
上述した選択の後、ステップ２を継続する（完了）。
【００７１】
[ステップ１４]
選択方法Ｂを使用することにより、カウンタ＃Ｄｅｌとカウンタ＃Ａｄｄとを比較する。
選択方法Ｂにおける選択ステップ（ａ）によれば、＃Ｄｅｌ（５）が＃Ａｄｄ（１）を越えているため、演算子は、好ましくは、下記に示す通りに選択される：
論理位置ＡｐｏｓＳｔａｒｔ（４）において、５（＃Ｄｅｌ）演算子を削除する。
続いて以下を行なう：
論理位置ＡｐｏｓＳｔａｒｔ（４）から開始し、セットＢ要素から１（＃Ａｄｄ）演算子を追加する。
この演算子の選択を図１８に示す。
【００７２】
[ステップ１５]
アルゴリズムにおける最後のステップ２（完了）が上述したステップ１４に到達する。
アルゴリズム及び方法Ｂの反復の完了後、データセットＡからデータセットＢへの変更を記述する複数の完全な演算子が、好ましくは、対応する論理位置、キー、データ部分とともにメモリに格納される。図１９に示すように、演算子、論理位置、キー、データ部分を含む更新データセットが生成される。
【００７３】
他の実施形態においては、論理位置は、キーにより記述されうる。この場合、端末が受信する更新データセットが、好ましくは、データ要素のソートが行なえるように、相互に関連する論理位置の状態を示す情報を含む。これにより、論理位置が、１、２、３・・・等である必要はない。また、ソートを容易にするため、位置が相互に関連を有する限り、Ａ、Ｂ、Ｃ・・・やその他により記述されうる。
【００７４】
データセットＡを承知した上で、更新データセットは、図１９に示すような演算子を含み、最初から最後まで演算子を一つずつ順番に用いることにより、データセットＢが生成されうる。
【００７５】
これがどのようにしてなされるかの段階的な記載が添付の図２０〜図２９に示される。
【００７６】
図２０は、更新データセットがデータセットＡに適用されるよりも以前のデータセットＡ及びデータセットＢの状況を示す。そのため、以下のステップは、図１９における更新データセットを使用することにより、データセットＡからデータセットＢを生成する。
【００７７】
図２１に示すように、図１９に示す更新データセットの１番目の列をデータセットＡに適用することにより、図２２に示すように、修正されたデータセットＡが得られる。
【００７８】
図２３に示すように、図１９に示す更新データセットの２番目の列を、データセットＡに適用することにより、図２４に示すように、修正されたデータセットＡが得られる。
【００７９】
図２５に示すように、図１９に示す更新データセットの３番目の列を、データセットＡに適用することにより、図２６に示すように、修正されたデータセットＡが得られる。
【００８０】
図２７に示すように、図１９に示す更新データセットの４番目の列を、データセットＡに適用することにより、図２８に示すように、修正されたデータセットＡが得られる。
【００８１】
ここで、演算子は、図２９に示すように、データセットＡをデータセットＢに変換する。
【００８２】
上記記載における用語”含む（ｃｏｍｐｒｉｓｉｎｇ）”は、他の要素又はステップを除外しない。”単数（ａ”又は”ａｎ”）は、複数を除外しない。
【００８３】
更に、用語”含む（ｉｎｃｌｕｄｅ）”及び”含む（ｃｏｎｔａｉｎ）”は、他の要素又はステップを除外しない。
【図１】
2010514035.tif 000004
【図２】
2010514035.tif 000005
【図３】
2010514035.tif 000006
【図４】
2010514035.tif 000007
【図５】
2010514035.tif 000008
【図６】
2010514035.tif 000009
【図７】
2010514035.tif 000010
【図８】
2010514035.tif 000011
【図９】
2010514035.tif 000012
【図１０】
2010514035.tif 000013
【図１１】
2010514035.tif 000014
【図１２】
2010514035.tif 000015
【図１３】
2010514035.tif 000016
【図１４】
2010514035.tif 000017
【図１５】
2010514035.tif 000018
【図１６】
2010514035.tif 000019
【図１７】
2010514035.tif 000020
【図１８】
2010514035.tif 000021
【図１９】
2010514035.tif 000022
【図２０】
2010514035.tif 000023
【図２１】
2010514035.tif 000024
【図２２】
2010514035.tif 000025
【図２３】
2010514035.tif 000026
【図２４】
2010514035.tif 000027
【図２５】
2010514035.tif 000028
【図２６】
2010514035.tif 000029
【図２７】
2010514035.tif 000030
【図２８】
2010514035.tif 000031
【図２９】
2010514035.tif 000032
【図３０】
2010514035.tif 000033
【国際調査報告】
2010514035.tif 000034
2010514035.tif 000035
2010514035.tif 000036