(57)【特許請求の範囲】
【請求項１】
クライアントと通信し且つ複数のプロセッサを有するマッチエンジンを備える電子取引システムにおいて暗示の注文を取引するためのコンピュータ実行方法であって、
前記マッチエンジンが、第１の組の１つ以上の実際の注文を前記クライアントから受信するステップであって、前記注文は互いに対して取引可能ではないステップと、
前記マッチエンジンが、１つ以上のノードを有する１つ以上の最短経路ツリーの計算に基づいて前記第１の組の実際の注文内の前記実際の注文から計算される１つ以上の暗示の注文を識別するステップであって、前記１つ以上の暗示の注文は関連する暗示の注文の１つ以上のグループを形成するステップと、
前記マッチエンジンが、約定グリッド上の要素が各スレッドにおけるツリーのルートに対応するように、別個のプロセッサで実行される並列の実行スレッドの各々に、前記関連する暗示の注文の１つ以上のグループを割り当てるステップと、
前記マッチエンジンが、少なくとも１つの追加の実際の注文を受信するステップと、
前記マッチエンジンが、１つ以上の暗示の注文のグループを利用して、前記追加の実際の注文が、前記第１の組の実際の注文内の１つ以上の実際の注文に対して取引可能であるかどうかを決定するステップと、
前記マッチエンジンが、前記少なくとも一つの追加の実際の注文と前記第１の組の実際の注文内の１つ以上の実際の注文との間で取引を実行するステップと、
前記マッチエンジンが、前記取引を反映するために前記第１の組の実際の注文を更新するステップと、
前記マッチエンジンが、更新された組の実際の注文内の前記実際の注文から計算される１つ以上の暗示の注文を識別するステップと
を備えることを特徴とするコンピュータ実行方法。
【請求項２】
暗示の注文を決定する方法が特定されているモデル化言語の構文マッピングに従って前記実際の注文を変換するステップをさらに備え、
前記変換することは、前記モデル化言語における表現を、コンピュータプログラミング言語で定義された変数に保持されるデータの変換と関係付けることにより、前記コンピュータのメモリに関係付けられることを特徴とする、請求項１に記載のコンピュータ実行方法。
【請求項３】
変換するステップは、
注文と関係付けられる一意の取引システム識別子を、前記約定グリッド上の要素と関連付けられる１組のノードにマッピングすること、及び
取引システム単位及び１０進精度を有する価格を、取引可能性が注文価格のゼロ又はネガティブサムによって表されるように、負数１を乗じた買い又は売り価格のいずれかを有する一般単位又は単位のない整数価格にマッピングすること
を含むことを特徴とする、請求項２に記載のコンピュータ実行方法。
【請求項４】
電子取引システムに使用されるモデル化言語の構文マッピングに従って、前記識別された暗示の注文を変換するステップをさらに備えることを特徴とする、請求項２に記載のコンピュータ実行方法。
【請求項５】
前記第１の組の実際の注文及び前記少なくとも一つの追加の実際の注文は、前記組内の各注文に対する最高ビッド及び最高アスクに関する注文価格を有し、
前記最高ビッド及び最高アスクが非負の価格を有する有向辺に関係付けられるように、再重み付け手続きが用いられることを特徴とする、請求項２に記載のコンピュータ実行方法。
【請求項６】
有向辺における効果に従って前記少なくとも一つの追加の実際の注文を分類するステップと、
どのツリー又はツリー内のノードが前記少なくとも一つの追加の注文によって影響を受けるかを決定するために前記最短経路ツリーを分析するステップと、
影響を受けるツリーごとに新しい値を計算するステップであって、前記影響を受けるツリーごとの計算は、独立の実行スレッドに割り当てられるステップと、
前記新しい値の計算を識別された暗示の注文と統合するステップと、
外部形式への変換に適したメッセージで前記識別された暗示の注文を報告するステップと
をさらに備えることを特徴とする、請求項１に記載のコンピュータ実行方法。
【請求項７】
前記追加の市場注文を分類するステップは、より良い最高価格、より悪い最高価格、最高レベルにおけるより大きな量、及び最高レベルにおけるより少ない量のカテゴリを備えることを特徴とする、請求項６に記載のコンピュータ実行方法。
【請求項８】
前記最短経路ツリーを分析するステップは、ルート集合の要素として潜在的に変化したツリーを識別することを特徴とする、請求項６に記載のコンピュータ実行方法。
【請求項９】
前記最短経路ツリーを分析するステップは、グローバル変化集合又はルート固有変化集合の要素として各ツリー内で潜在的に変化したノードを識別することを特徴とする、請求項６に記載のコンピュータ実行方法。
【請求項１０】
独立スレッドへの割り当ては、独立スレッドがルート固有変化集合を計算するために使用することが出来る１つ以上のパラメータの計算をさらに備えることを特徴とする、請求項６に記載のコンピュータ実行方法。
【請求項１１】
影響を受けたツリーに関係付けられる暗示の注文又は関連する市場データを制限するフィルタリング基準を設定するステップをさらに備えることを特徴とする、請求項６に記載のコンピュータ実行方法。
【請求項１２】
前記フィルタリング基準は、特定の取引可能な約定における暗示の注文が取引の実行をもたらす確率に関連することを特徴とする、請求項１１に記載のコンピュータ実行方法。
【請求項１３】
前記確率は、ビッド／アスクスプレッドの大きさと前記スプレッドで取引される量との間の関係に基づくことを特徴とする、請求項１２に記載のコンピュータ実行方法。
【請求項１４】
前記確率は、暗示の注文の識別と前記暗示の注文と取引する注文との間の時間差に基づくことを特徴とする、請求項１２に記載のコンピュータ実行方法。
【請求項１５】
前記フィルタリング基準は、取引状況の変化に応じて公示される市場データの量を拡大又は縮小するように自動的に調節されることを特徴とする、請求項１１に記載のコンピュータ実行方法。
【請求項１６】
取引状況の前記変化は、第１又は第２の組の市場注文が受信される速度を備えることを特徴とする、請求項１５に記載のコンピュータ実行方法。
【請求項１７】
前記最短経路ツリーを計算することは、間接経路が直接経路と同じ価格であるが非価格特性が悪い場合に、暗示される辺コレクションにおける代替経路を記録することを含むことを特徴とする、請求項６に記載のコンピュータ実行方法。
【請求項１８】
前記非価格特性は、時間、量、時間及び量、又は検出の順番を含むことを特徴とする、請求項１７に記載のコンピュータ実行方法。
【請求項１９】
コンピュータプログラムが記憶されたコンピュータ可読媒体であって、前記コンピュータプログラムは実行されると、複数のプロセッサを有するコンピュータに、
第１の組の１つ以上の実際の注文をクライアントから受信するステップであって、前記注文は、互いに取引可能でないステップと、
モデル化言語の構文マッピングに従って、暗示の注文の計算に適した形式に前記第１の組の実際の注文を変換するステップと、
１つ以上のノードを有する１つ以上の最短経路ツリーの計算に基づいて前記第１の組の実際の注文から計算される１つ以上の暗示の注文を識別するステップと、
前記暗示の注文に対応する公示可能な市場データを識別するステップと、
少なくとも１つの追加の実際の注文を受信するステップと、
暗示の注文を利用して、前記少なくとも一つの追加の注文と前記第１の組の実際の注文内の１つ以上の実際の注文との間で取引可能な注文の組を識別するステップと、
前記識別された取引を実行するステップと、
任意の実行された取引を明らかにするために前記第１の組の実際の注文を更新するステップと、
前記実行された取引及び前記更新された第１の組の実際の注文を伝達するステップと、
有向辺における効果に従って前記少なくとも一つの追加の実際の注文を分類するステップと、
どのツリー又はツリー内のノードが前記少なくとも一つの追加の実際の注文によって影響を受けるかを決定するために前記最短経路ツリーを分析するステップと、
影響を受けるツリーごとに新しい値を計算するステップであって、前記影響を受けるツリーごとの計算は、約定グリッド上の要素が各スレッドにおけるツリーのルートに対応するように、別個のプロセッサで実行される独立の実行スレッドの各々に割り当てられるステップと、
前記新しい値の計算を前記暗示の注文及び関連する市場データに統合するステップと、
外部形式への変換に適したメッセージで前記暗示の注文及び市場データを報告するステップと
を実行させることを特徴とするコンピュータ可読媒体。
【請求項２０】
電子取引環境において暗示の注文を決定するためのシステムであって、
ネットワークと、
前記ネットワークと通信する１つ以上のユーザ装置と、
前記ネットワークと通信する第１のプロセッサであって、
第１の組の１つ以上の実際の注文を受信し、前記注文は、互いに取引可能でなく、従って、休止の注文として前記第１のプロセッサのメモリ内で休止し、
前記第１の組の実際の注文を暗示の注文の計算に適した形式に変換し、
前記第１の組の実際の注文から計算される１つ以上の暗示の注文を識別し、
前記暗示の注文に対応する公示可能な市場データを識別し、
少なくとも一つの追加の実際の注文を受信し、
取引可能な注文の組を識別して、対応する取引を実行し、
前記第１のプロセッサに保持された休止の注文の組を更新し、且つ
前記実行された取引及び前記更新された休止の注文の組の結果を伝達する第１のプロセッサと、
前記第１の組の実際の注文内の前記１つ以上の暗示の注文と関係付けられる、１つ以上の最短経路ツリーを計算する第２のプロセッサであって、前記最短経路ツリーが１つ以上のノードを有し、
有向辺における効果に従って前記少なくとも一つの追加の実際の注文を分類し、
どのツリー又はツリー内のノードが前記少なくとも一つの追加の実際の注文によって影響を受けるかを決定するために前記最短経路ツリーを分析し、
影響を受けるツリーごとに新しい値を計算し、前記影響を受けるツリーごとの計算は、約定グリッド上の要素が各スレッドにおけるツリーのルートに対応するように、独立の実行スレッドの各々に割り当てられ、
前記新しい値の計算を前記暗示の注文及び関連する市場データに統合し、且つ
外部形式への変換に適したメッセージで前記暗示の注文及び市場データを報告する第２のプロセッサと
を備えることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、商品取引、金融派生商品取引又は買い方からの注文が売り方からの注文と一致する取引可能商品に関する類似のビジネスにおける電子取引のためのソフトウェア、システム及び方法に関する。
【背景技術】
【０００２】
電子取引システムは、特定の取引可能商品に対するビッド（ｂｉｄ）又はオファー（ｏｆｆｅｒ）の登録を可能にする。こうした単純なビッド及びオファーはアウトライト注文（ｏｕｔｒｉｇｈｔ  ｏｒｄｅｒ）と呼ばれ、以下でより詳細に検討されるスプレッド注文（ｓｐｒｅａｄ  ｏｒｄｅｒ）とは対照的である。
【０００３】
スプレッド注文は、例えば、異なる月の先物約定、異なる商品又は同じ商品の異なる等級等の、２つの取引可能商品の同時に行なわれる買い及び売りである。スプレッドの各ビッド及びオファー要素は、それぞれビッドレグ（ｂｉｄ  ｌｅｇ）及びオファーレグ（ｏｆｆｅｒ  ｌｅｇ）と呼ばれる。実際の注文（ｒｅａｌ  ｏｒｄｅｒ）は、取引者によってシステムに入力される注文である。取引者は、取引システムに適切な情報を入力して、見計らい注文（ｏｐｅｎ  ｏｒｄｅｒ）として注文をシステムに放出する。実際の注文は、限定されないが、先物、オプション、商品間スプレッド、商品内スプレッド、先物ストリップ等を含む任意の取引可能商品に関して、システムに入力されてもよい。
【０００４】
実際の注文とは異なり、暗示の注文（ｉｍｐｌｉｅｄ  ｏｒｄｅｒ）は、実際の注文を入力した取引者に代わってシステムによって生成される。例えば、暗示のスプレッドは、２つの実際のアウトライトから導出されてもよい。システムは、「導出（ｄｅｒｉｖｅｄ）」された又は「暗示（ｉｍｐｌｉｅｄ）」の注文を生成して、取引され得る市場として、暗示の注文の生成から生じる市場を表示する。取引者がこの暗示の市場に対して取引する場合、暗示の注文及び結果として生じる市場を生成するために結合した実際の注文は、一致した取引として実行される。
【０００５】
暗示の注文を導出する取引システムは、計算能力及び速度によって制限されることが多い。特に注文の組み合わせが２〜３以上の注文を含む場合、先行技術の取引システムは、全ての可能な又は最高の暗示の市場を決定する有効な方法を有していない。
【０００６】
最新の取引システムは、典型的には、分散機構により実装される。こうしたシステムは、各要素が他の要素の動作から大きく隔離されるように、高度の論理的分離を有する機能要素を含む。分散システムは、複雑な機能が多くの小さな要素として実装され得るように、システム要素間で通信するための改良された能力を利用する。こうした小さな要素は、設計及び維持するのが容易であり、様々なコンピュータハードウェア／オペレーティングシステム環境に適合するのに大きな柔軟性をもたらす。
【０００７】
取引システムにおける注文マッチング機能は、典型的には、多数の事例が存在し得るマッチエンジンと呼ばれる専用の要素によって実行される。各マッチエンジンは、注文を受信し、注文を内部に保存し、取引可能な組み合わせを計算し、且つ市場データの形式で実際及び暗示の注文の可用性を広告する専用の注文マッチング要素である。システムを使用する取引者が追加の注文を送信することにより市場データに応答する場合、こうした注文はマッチエンジンによって受信され、マッチエンジンは受信した注文を以前に受信した注文又はその組み合わせと一致させようとする。マッチエンジンは、可能な取引を実行して、結果を伝達する。
【０００８】
暗示の注文は、同じ約定において対応する実際の注文よりも良い価格を有することが多い。これは、取引を誘引することを望んで、２以上の取引者が注文価格を徐々に改善する場合に生じ得る。２つ以上の実際の注文からの小さな改善を結合することにより、暗示の注文において大きな改善が生じ得る。一般に、より良い価格で暗示の注文を広告することは、取引者がそれらと取引するために反対の注文を入力することを促進するであろう。マッチエンジンが計算することが出来る組み合わせが多いほど、この促進は大きくなり、取引所は増加した取引量からより大きな利益を得るであろう。しかし、広告される注文数が増加すると、市場データとしてそれらを計算して公示するのに必要な時間も増加する。取引者は取引システムから迅速な応答を期待しており、それが得られなければいつでも他の場所でビジネスをすることが出来るので、これは取引所にとって問題を生じる。
【０００９】
先行技術のシステムにおいて、時機を逸せずに暗示の注文を計算し且つ公示することが出来なければ、その用途は限定されることになる。こうしたシステムでは、少数の単純な組み合わせだけが計算され、すなわち大量に取引される約定のうちの少数に対してのみである。対照的に、本発明の実施は、大量の関連する約定に対する多くの組み合わせを効率的に計算することを可能にする。それは、マッチエンジン内の約定を並列的に計算され得るグループに分割することにより、及びより高い取引率を有する暗示の注文がより迅速且つ頻繁に報告されるように市場データをフィルタリングすることにより、これを達成する。
【００１０】
本発明の背景技術の検討は、本発明の事情を説明するために本明細書に含まれている。これは、参照されたいずれの題材が、いずれの請求項の優先日において、発行され、周知であり、又は周知慣用知識の一部であったことの承認として取られるべきものではない。
【００１１】
明細書の説明及び請求項の中で、「備える」という用語及びその変形は、他の付加物、構成要素、整数又はステップを排除することを意図していない。
【発明の概要】
【００１２】
本発明は、一般に、電子取引マッチングシステムにおいて暗示の注文を識別及び計算するためのシステム及び方法に関する。暗示の注文が１組の実際の注文から計算され得る方法が提供される。１つの実装では、計算はより速い速度を達成するために並列的に実行されてもよく、暗示の注文に対する検索は取引システムの操作者が収益を得る可能性が最も高いものに限定されてもよい。また、取引システムによって受信される新しい注文の各々又は注文の組に必要とされる計算量を低減させるための方法が提供される。
【００１３】
１つの実装では、電子取引システムにおいて暗示の注文を決定するためのコンピュータ実行方法が提供される。方法は、第１の組の１つ以上の実際の注文を受信することを備え、注文は互いに対して取引可能ではない。１つ以上の暗示の注文は、第１の組の実際の注文の中で識別される。また、暗示の注文に対応する市場データも識別され得る。少なくとも一つの追加の注文が受信され、追加の注文の取引可能性が第１の組の実際の注文の中で実際の又は暗示の注文に対して決定される。休止の注文の組は、追加の注文の取引可能性によって影響を受けない第１の組の注文の中で実際の及び暗示の注文から決定される。暗示の注文は、休止の注文の組の中から決定される。
【００１４】
１つの実装では、第１の組の実際の注文及び追加の注文は、モデル化言語の構文マッピングにより変換される。変換は、取引可能な注文に対する一意の取引システム識別子を約定グリッド上の要素に関連付けられる１組のノードにマッピングすること、及び取引システム単位及び１０進精度を有する価格を取引可能性が注文価格のゼロ又はネガティブサムによって表されるように負数１を乗じた買い又は売り価格のいずれかを有する一般単位又は単位のない整数価格にマッピングすることを含むことが出来る。
【００１５】
１つの実装では、第１の組の実際の注文によって暗示される１つ以上の注文の識別は、１つ以上のノードを有する１つ以上の最短経路ツリーの計算を含む。少なくとも一つの追加の実際の注文は、有向辺における効果によって分類され得る。最短経路ツリーは、どのツリー又はツリー内のノードが少なくとも一つの追加の注文によって影響を受けるかを決定するために分析され得る。影響を受けるツリーごとの新しい値が計算される。影響を受けるツリーごとの計算は、独立の実行スレッドに割り当てられる。新しい値の計算は、識別された暗示の注文及び関連する市場データと統合され得る。識別された暗示の注文及び市場データは、外部形式への変換に適したメッセージで報告され得る。
【００１６】
様々な実装は、１つ以上の以下の特徴を含み得る。追加の市場注文を分類することは、より良い最高価格、より悪い最高価格、最高レベルにおけるより大きな量、及び最高レベルにおけるより少ない量のカテゴリを備える。最短経路ツリーを分析することは、ルート集合の要素として潜在的に変化したツリーを識別する。最短経路ツリーを分析することは、グローバル変化集合又はルート固有変化集合の要素として各ツリー内で潜在的に変化したノードを識別する。独立スレッドへの割り当ては、独立スレッドがルート固有変化集合を計算するために使用することが出来る１つ以上のパラメータの計算をさらに備える。影響を受けたツリーに関係付けられる暗示の注文又は関連市場データを制限するフィルタリング基準が設定され得る。フィルタリング基準は、特定の取引可能約定における暗示の注文が実行される取引をもたらす確率に関連する。確率は、ビッド／アスク（ａｓｋ）スプレッドの大きさとそのスプレッドで取引される量との間の関係に基づく。確率は、暗示の注文の識別と暗示の注文と取引する注文との間の時間差に基づく。フィルタリング基準は、取引状況の変化に応じて公示される市場データの量を拡大又は縮小するように自動的に調節される。取引状況の変化は、第１又は第２の組の市場注文が受信される割合を備える。最短経路ツリーを計算することは、間接経路が直接経路と同じ価格であるが非価格特性が悪い場合に、暗示される辺コレクションにおける代替経路を記録することを含む。非価格特性は、時間、量、時間及び量、又は検出順序を備える。
【００１７】
１つ以上の実装の詳細は、添付の図面及び以下の記載おいて説明される。他の特徴、目的、及び利点は、記載及び図面、並びに請求項から明らかであろう。
【図面の簡単な説明】
【００１８】
【図１】本発明が実装される分散取引機構を示す。
【図２】階層化機構を有するマッチエンジンを示す。
【図３】単純な示唆グループのための約定グリッドを示す。
【図４】例示的な装飾された注文要素を示す。
【図５】幾つかの一般の注文記号を示す。これらは、マッチエンジンの状態を表すために約定グリッドに配置され、又は入力メッセージストリームをモデル化するための一連の表現に使用され得る。図５は、示唆グループにおける約定と約定グリッド上のノードペア数との間の対応を示す。
【図６】価格が単純な無次元数で与えられる８個の注文を有する単純な示唆グループのための約定グリッドを示す。
【図７】特定の約定の詳細がない注文の等価グラフ表現を示す。
【図８】約定グリッドにおけるノード０から全てのノードまでの最短経路ツリーを計算するための標識価格が付いた注文の付加を示す。
【図９】ツリー構造及びノードの重みと共に、ベルマン−フォードアルゴリズムによって計算され得る最短経路ツリー（ＳＰＴ）を示す。
【図１０】再重み付けと呼ばれる工程である、非負であることが保証される新しい辺の重みの計算を示す。
【図１１】多くの注文が追加された、図６の約定グリッドを示す。
【図１２】図１１における注文の等価グラフ表現を示す。
【図１３】ノード０をルートとするＳＰＴを示す。
【図１４】ノード１をルートとするＳＰＴを示す。
【図１５】ノード２をルートとするＳＰＴを示す。
【図１６】ノード３をルートとするＳＰＴを示す。
【図１７】ノード４をルートとするＳＰＴを示す。
【図１８】ノード５をルートとするＳＰＴを示す。
【図１９】図１３〜図１８におけるツリーと同じ簡略化された形式でノード６をルートとするＳＰＴを示す。
【図２０】プログラミング言語において現れるｓｐｔ［ｉ，ｊ］として示されるＳＰＴ行列の形式で、全７個の最短経路ツリーの数値表現を示す。
【図２１】どのように辺に影響を与え得るかに従ってマッチエンジンへの入力メッセージを分類するために使用され得るインプリケータのリストを示す。
【図２２】流動性市場及び非流動性市場の双方に対する取引された量対以前のビッド／アスクスプレッドのヒストグラムを示す。
【図２３ａ】単一スレッドモデルを使用する例示的なマッチエンジンの性能を示す。
【図２３ｂ】複数スレッドモデルを使用する例示的なマッチエンジンの性能を示す。
【図２４】暗示の注文を決定する例示的な方法の流れ図である。
【発明を実施するための形態】
【００１９】
本発明は、分散型コンピュータシステムに関して例示及び記載される。特定の例は、先物及びオプション取引に有益な要素の特定の組を識別する。しかし、多くの要素及び独創的な特徴は、他の電子取引環境に容易に適合される。本発明は予想可能な方法で他のプロトコル及びインターフェースに容易に拡張されることが理解されるべきであるが、本明細書に記載の特定の例示は、特定のプロトコル及び／又はインターフェースを教示してもよい。
【００２０】
規制された及び規制されていない取引及び他の電子取引サービスは、電子取引システムを利用する。このようなシステムの機能配置の例示が図１に示される。この例示では、電子取引システムは、システム境界１００内の構成要素から成る。クライアント１０９及び価格報告システム１１０はシステムの外部にあるが、インターネット等の通信ネットワークを使用してシステムと通信する。クライアントという用語は、一般に、電子取引システムと通信することが出来る任意のユーザによって操作される装置又は他のネットワーク装置を示すために使用される。
【００２１】
例示的な実装では、クライアント１０９は、インターネット等の通信ネットワーク１０１により注文提出点１０２に電子注文を送信する。注文提出点は、特定の証券会社、投資家、及び投資計画等の要求に適合する多様なアプリケーション固有の設計を採用することが考えられる。また、電子取引システムは、複数のバリデータ（Ｖａｌｉｄａｔｏｒ）、マッチエンジン、パーシスト要素（Ｐｅｒｓｉｓｔ  ｃｏｍｐｏｎｅｎｔ）、ティッカープラント（Ｔｉｃｋｅｒ  Ｐｌａｎｔ）、市場データサーバ及び市場データ分散サーバを含むことも考えられる。こうした要素間のメッセージのルーティングは、商業的に利用可能なハードウェア及びソフトウェアを用いて容易に処理される。記載は単独で開示を簡単にするためにのみ与えられることが理解されるべきである。
【００２２】
注文提出点１０２は、バリデータ１０３と通信する。バリデータは、確立された基準に対して新しい注文の特性を検査して、関連するマッチエンジン１０４に確認された注文を伝達する。図１では、新しい注文が以前に入力された注文に適合しなかったと仮定されて、マッチエンジンは受信した注文をパーシスト要素１０５に伝達する。パーシスト要素１０５は、注文をデータベースに記憶する。また、図１では、パーシストによる注文の記憶が取引システムによる「公式」な受信を構成すると仮定されて、パーシストは注文提出点１０２に約定報告を伝達する。それは注文提出点１０２から注文の発信者に伝達される。
【００２３】
マッチエンジンは、新しい注文及び作成した任意の暗示の注文の存在をティッカープラント１０６に伝達する。同様に、ティッカープラント１０６は、市場データサーバ１０７と通信する。ティッカープラントは、複数の発信元からのデータを統合して、価格報告システム１１０等の電子取引システムの外部の構成要素と通信するように機能するので、マッチエンジンと市場データサーバとの間の位置を占める。市場データサーバは、様々な方法で、市場データをクライアント１０９に伝達してもよい。例えば、データは、約定報告と同じリンクを介してクライアントと通信するために注文提出点１０２に送信されてもよく、又は任意の数のクライアントと通信可能な市場データ分散サーバ１０８に送信されてもよい。
【００２４】
当業者であれば、マッチエンジン１０４の操作が取引ネットワークの一部以上で又は関連システムで実行され得ることを理解するであろう。例えば、暗示の注文の計算は、取引ネットワーク又はマッチエンジンとの間の裁定機会を求めて取引ステーションで取引者によって行なわれてもよい。また、可能な取引戦略を評価するために、指示、規則のために、又は取引がモデルとして使用される他の問題を解決するために、取引ネットワークの外部でこうした計算を実行することも可能である。
【００２５】
幾つかの実装では、マッチエンジン１０４は、図２に示されるような階層化機構を有するであろう。マッチエンジンは、メッセージバス２０１を使用して他の構成要素と通信する。着信メッセージは、アダプテーション層２０２によって、単にコアと呼ばれることもあるマッチエンジンコア２０３により処理され得るイベントに変換される。コアからの出力メッセージは、アダプテーション層によって、メッセージバス２０１を使用する取引システムの他の部分に送信され得る元のメッセージに変換される。コア２０３は、暗示の注文を計算するために必要とされるプログラムコードを含む。このプログラムコードは、インプリケータと呼ばれる。本発明は、計算、公示及び取引全体の速度を増すために、暗示の市場データのグラフ理論、並列処理及び収益成形を用いる新しい種類のインプリケータである。この例は電子取引システムにおけるマッチエンジンの一部としてインプリケータを示すが、インプリケータは暗示の注文が計算される必要がある任意のシステムで使用され得る。このようなシステムの例は、市場データを受信して、複数の電子取引システムにおいて裁定機会を求めるために取引者によって使用されるクライアントソフトウェアである。
【００２６】
当業者であれば、マッチエンジンコア及びそのインプリケータが、複数スレッドの実行を可能にするＪａｖａ（登録商標）又はＣ＋＋等のプログラミング言語で実装され得ること、及び複数のスレッドを有するプログラムが複数の中央処理装置（ＣＰＵ）を有するコンピュータシステムで実行され得ることを理解するであろう。このような実装では、プログラムが正確に設計されていれば、スレッドは並列に実行され、全てのスレッドを実行するのにかかる時間は単一の最も長いスレッドによってかかる時間と同じ短さであり得る。ＣＰＵよりも多くのスレッドがある場合、実行時間は幾つのスレッドが各ＣＰＵで連続して実行されなければならないかに依存するであろう。図２では、コアはこのような言語で実装されること、及びインプリケータによる暗示の注文の計算は別個のスレッドで並列に多くの独立した計算を実行することにより加速されることが考えられる。
【００２７】
インプリケータは、示唆グループと呼ばれる約定のグループに作用する。先物取引では、示唆グループは、アウトライト約定及び互いと取引可能な組み合わせ約定から成る。アウトライト約定は、例えば、オクラホマ州クッシングで２００８年１月が限月のウェストテキサスインターミディエート原油（Ｗｅｓｔ  Ｔｅｘａｓ  Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｃｒｕｄｅ  Ｏｉｌ）等の生産物及び納期により定義される。組み合わせ約定は、レグ（ｌｅｇ）と呼ばれる２つ以上のアウトライト約定により定義される。これらのうち最も簡単なものは、ある納期で生産物を買い、別の納期でそれを売る約定であるカレンダースプレッドである。最も簡単な可能な示唆グループは、２つのアウトライト及びそれらの間のスプレッドから成る。
【００２８】
任意の数のレグを有する組み合わせ約定を定義することが出来る。これらのさらなる例示は、２つのレグを有する異種商品間スプレッド（ｉｎｔｅｒｃｏｍｍｏｄｉｔｙ  ｓｐｒｅａｄ）、３つのレグを有する３：２：１の比率のスプレッド、及び１２のレグを有する年次ストリップ（ｙｅａｒｌｙ  ｓｔｒｉｐ）を含む。任意の数のこのような約定は、示唆グループに属する任意の組み合わせ約定がグループの要素としてそのアウトライトレグ約定の全てを同様に有する限り、示唆グループに配置されてもよい。アウトライト約定の全ての可能な組み合わせが取引可能な組み合わせ約定に対応することは必要ではない。
【００２９】
示唆可能な約定を定義してこのような約定で取引可能な暗示の注文を計算する技術の例は、米国特許出願第１２／０３２，３７９号の中で見つけることが出来る。その中に記載されたモデル化言語及び示唆技術は、所定のコレクションからオブジェクト間のペアをなす関係をモデル化するために使用される数学的構造の研究であるグラフ理論を利用する。この文脈において「グラフ」とは、頂点又は「ノード」のコレクション及び頂点のペアを繋ぐ辺のコレクションのことを意味する。この技術で用いられるグラフの種類は、各辺が起点ノード及び目的ノードを用いて定義され、起点から目的地へと方向付けられるので、より詳細には、「有向グラフ」と呼ばれる。
【００３０】
ビジュアルマッチエンジンモデル化言語（ＭＥＭＬ）は、具象構文、言語で表現を構築するための抽象構文、表現を取引システムの要素と関係付けるための構文マッピング、及びモデル化言語表現を現実世界のビジネス要件に関連付けるための意味マッピングを含む。図３に示される約定グリッドは、表現の例示である。また、図４に示される装飾された注文要素も表現である。モデル化言語は、装飾された注文要素がマッチエンジンコアにおける休止の注文を表すために約定グリッド上に配置され得るように、こうした表現が結合されることを可能にする。
【００３１】
１つの実装では、アダプテーション層は、例えば、休止の注文の組等の注文の組の構文マッピングを実行する。アダプテーション層は、外部の取引システムにおける約定識別子をマッチエンジンモデル化言語で約定グリッドにより定義されるグラフにおけるノードのペアと関係付ける。それは、先物約定におけるバレル及びガロンのような現実世界の単位での外部の取引システムの価格を、マッチエンジンコアに対して内部であり且つ示唆グループ内の全ての約定に共通である縮小単位でのマシン価格と関係付ける。
【００３２】
また、アダプテーション層は、注文が買い又は売りであるかどうかに基づいて価格換算係数を適用する。実際の注文として市場参加者により提出される注文は、買い（ビッド）又は売り（アスク）のいずれかであってもよい。こうした注文の価格は、正又は負であってもよいが、一般には取引はビッドがアスク価格に等しいかより良い場合に可能である。注文が約定グリッド上に配置されると、買い及び売りはその開始及び終了点によって区別される。マシン価格として表示するために、買い注文の外部の価格に−１を乗じ、売り注文の外部の価格に＋１（すなわち、変化なし）を乗じる。結果として、互いに取引可能な２つ以上の注文のマシン価格の合計は、０以下になるであろう。
【００３３】
本発明を例示するために、単純な図３における接触グリッドが使用され得る。示唆グループは、２つの生産物から成る。１つは、「ＨＯ」と示される灯油（Ｈｅａｔｉｎｇ  Ｏｉｌ）３０１であり、もう１つは、「ＣＬ」と示されるウェストテキサスインターミディエート原油３０２である。一般月の１月（「Ｆ」）、２月（「Ｇ」）、及び３月（「Ｈ」）と示される３つの納期３０４がある。また、仮想の約定と現実の約定との間のスプレッド注文としてアウトライト注文のグラフ理論表示により要求される仮想ノード３０３もある。グラフのノードは０から６の番号が付けられ、取引可能な約定は図５に要約されるようにノードペアに対応する。実際の取引システムは、その示唆グループに対して遥かに大きなグリッドを必要とすることが理解されるであろう。
【００３４】
図６は、約定グリッド上の８つの実際の注文の配置を示す。実際の注文価格はマシン価格として示される。便宜上、特定されていない共通単位で単純な整数として縮小価格が示される。また、実際の注文量及び時間優先は、当面の間は特定されないままである。０−１の辺６０１は、２の価格で１月の灯油（「ＨＯＦ」）を売るためのアウトライト注文を表す。そして、２−３の辺６０２は、２月の灯油を買い、且つ１の価格で３月の灯油を売るためのスプレッド注文を表す。一般に、灯油価格はガロン当たりのドルという現実世界の単位で与えられ、且つ原油価格はバレル当たりのドルの単位で与えられること、及びアダプテーション層が入力値を適宜縮小することが理解されるであろう。
【００３５】
任意のアウトライト及び組み合わせ約定のための実際の注文は、グラフ上の有効辺で表現され得る。特定の約定における暗示の注文は、対応するノード間の最短経路として計算され得る。限定されないが、最短経路を計算するために、フロイド（Ｆｌｏｙｄ）のアルゴリズム、ベルマン−フォード（Ｂｅｌｌｍａｎ−Ｆｏｒｄ）アルゴリズム、ダイクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズム及びジョンソン（Ｊｏｈｎｓｏｎ）のアルゴリズムを含む様々な方法が用いられ得る。ノード間の最短経路を計算するために用いられる方法は、示唆グループの構造及び様々な約定の中の注文の分布に依存し、遭遇する可能性がある注文に最適なアルゴリズムで実装され得る。
【００３６】
本明細書に記載の実装は、要求される計算量を最小化する技術を含む。実装は、計算を並列化して優先順位を決めるために電子取引の様々な特性を使用する。
【００３７】
図２は、アダプテーション層２０２とマッチエンジンコア２０３との間の通信が入力イベント及び出力応答に関して示される例示的な実装を示す。入力イベント又は注文は、それらが記憶された辺に引き起こす変化に応じてインプリケータイベントに分類される。変化した辺によってどの最短経路が変更されるか及び各経路のどの程度が再計算を必要とするかを決定するために、現在の暗示の市場が分析される。暗示の計算の独立サブグループが多数の独立実行スレッドに割り当てられる。フィルタリング基準は、暗示の注文の報告を最もビジネス価値の高いものに限定して、それらが見つかるとすぐに計算を終了するように設定される。別個のプロセッサで独立スレッドの実行を処理するための基準が設定される。そして、結果は、取引システムの他の構成要素へ市場データとして公示するためにアダプテーション層によって変換に適した単一メッセージへと統合される。
【００３８】
並列化及び優先順位付け技術は、例えば、再重み付けされる辺にダイクストラのアルゴリズムを用いた暗示の注文の計算を利用して例示される。このステップの最後に、本発明の技術は、ダイクストラの計算から生じる最短経路ツリーを利用して例示されるであろう。当業者であれば、本発明のカテゴリ化、分析、割り当て、フィルタリング、スレッド管理及び統合技術は、最短経路ツリー又は暗示の市場データの類似のサブグループを独立スレッドに割り当てる手段が存在する限り、特定の形式の最短経路の計算に依存しないことを理解するであろう。インプリケータは、米国特許第６，３５６，９１１及び７，２８０，４８１号が教示する先行技術だけでなく、この分野におけるさらなる革新を利用することが出来る。
【００３９】
１つの実装では、辺は、約定の所与の側面において最高の価格レベルに対応する。辺の価格は、最高レベルの価格である。辺の量は、最高の価格レベルにおける全ての注文の総量である。辺の時間優先は、到着する最初の注文の時間優先であり、待ち行列の先頭注文とも呼ばれる。
【００４０】
最短経路の定義は、辺のこうした特性を含むように拡張される。経路の価格は、経路内の全ての辺価格の合計である。経路量は、任意の経路の成分辺の最小量である。経路時間は、任意の経路の成分辺の最大時間優先数である。これは、暗示される、すなわちマッチエンジンに到着する最後の成分注文を「完了」する注文の時間優先である。経路の優先度は、最初に価格により決定される。２つの経路が同じ価格を有する場合、最早時間優先を有する経路が「より短く」（すなわち優先し）、優先度がより高いと見なされる。２つの経路が同じ価格及び時間優先を有する場合、最も大きな量を有する経路が優先し、優先度がより高いと見なされる。３つの全ての特性が同じである場合、現在の実装では、アルゴリズムは、より高い優先度を有するものとして最初に発見された経路を選択する。しかし、別の実装では、最も高い優先経路を決定するために追加の辺特性がこのアルゴリズムに含まれ得る。
【００４１】
実際の注文が一方のノードから他方への辺として定義されることを考慮すると、暗示の注文は、単に、成分辺の価格、時間特性及び量から価格、時間特性及び量が計算される一方のノードから他方への経路である。この暗示の注文に対して取引する着信する実際の注文は、同じ経路を形成する複数の注文の連鎖に対して実際に取引することが理解される。各辺は、待ち行列の先頭の注文を有するであろう。そして、任意の取引の量は、最小の待ち行列の先頭の注文の量を超えることが出来ない。着信する実際の注文の量が最小の待ち行列の先頭の注文よりも大きいが経路の総量よりも小さい場合、入力される注文又は暗示の経路のいずれかが除去されるまで、連続する取引が実行される。
【００４２】
仮想ノードは、マッチエンジンモデル化言語の具体的な構文の一部として含まれ得る。これは、実際のアウトライト注文が、仮想ノードとアウトライトを定義する生産物及び限月に対応するノードとの間のスプレッドとして表現されることを可能にする。幾つかの実装では、実際のアウトライト売り注文がこのノードから発信する辺に対応する指向性の約定が含まれ得る。総合すれば、こうした特性は、仮想ノードから所与のアウトライトノードへの最短経路を所与のアウトライト約定に対する最も低い市場アスク価格に等しくする。以下の記載では、当業者に周知である任意の実際又は仮想のノードに関する再重み付けの一般概念が、スプレッドとして表される売りアウトライトの起点として特定の仮想ノードに適用されている。これは、後続の再重み付けされた辺価格に、計算を処理するために利用され得る特定のビジネス手段を与える。
【００４３】
暗示の注文を計算する最初のステップは、仮想ノードに関する注文グラフでノードの重みを計算することである。図７は、番号が付けられたノード及び重み付けされた辺を使って図６の注文グラフが如何にしてさらに単純に表現され得るかを示す。図６の注文６０１は図７では辺７０１として示され、図６の注文６０２は図７ではう７０２として示される。図８は、到達不能ノードに価格を割り当てるための標識価格がついた注文の付加を示す。標識価格は、油１バレル当たり１０，０００，０００．００ドルのような、実際に遭遇するであろう任意の価格よりも遥かに大きな実際の価格として定義される。この技術は、単純な価格の比較により欠けた辺を識別することを可能にし、これは実行上より高速であり、実装面でより単純である。
【００４４】
図９は、ベルマン−フォードアルゴリズムの適用から生ずる最短経路ツリー９０１を示す。ｓｐｔ［ｊ］１次元配列９０２は、ツリー内の各ノードの前身を含む（すなわち、ノードｓｐｔ［ｊ］はノードｊに先行する）。そして、ｗｔ［ｊ］一次元配列９０３は、ノードの重みを含む（すなわち、ｗｔ［ｊ］は最短経路に沿ったノード０及びノードｊの間の辺価格の合計である）。１０００という標識価格は単に例示であり、１つの実装では、標識価格は実際の価格よりも遥かに大きいがオーバフローを生じることなくコンピュータシステムによって処理され得る数字の範囲内であることが理解される。
【００４５】
暗示の市場を計算する第２のステップは、辺を再重み付けすることである。図１０は、元の価格を起点ノードの重みに加算して目的ノードの重みを減算することにより辺の新しい価格が得られる再重み付け規則の適用を示す。図１０における注文１００１は、図９のノード０及びノード１の重みを用いて新しい価格を計算した図６の注文６０１に対応する。図１０の注文１００２は、同様に処理された図６の注文６０２に対応する。この処理の結果は、全ての辺価格を非負にすることになる。当業者であれば、マシン価格からダイクストラのアルゴリズムで用いる非負の再重み付けされた辺価格への変換は容易な処理であることを理解するであろう。本明細書における実装は、他の価格、時間及び量の他の重み付け、スケーリング及び表現も可能であるという理解の下で再重み付けされた価格に関して記載される。
【００４６】
図１１は、既に再重み付けされた価格を有するより複雑な例示を示す。図１２は、簡略化されたノード及び辺のグラフ表現を示す。注文と辺との関係が個々の注文と共に示されているが、辺は同じ価格レベルで複数の注文を表すことが出来ることが理解される。１つの実装では、各ノードペアの間で各方向に単一の辺のみが許可される。この辺の価格は、ノードペアに対応する約定側における最高のビッド又はアスクの価格である。辺の量は、最高の価格レベルにおける注文の総量である。辺の時間優先は、最高の価格レベルでの最早注文の時間優先であり、待ち行列の先頭注文とも呼ばれる。
【００４７】
図１３から１９は、７個のルートノード全てについての最短経路ツリーを示す。図２０は、こうしたルートのそれぞれについてのＳＰＴベクトルを２次元配列ｓｐｔ［ｉ，ｊ］として示される行列にまとめたものである。マッチエンジンモデル化言語で特定されるマッチエンジンは、暗示の市場を計算するためのグラフ理論技術を用いて実装され得る。最短経路ツリーのコレクションとしての暗示の市場の表現は、この手法に基づく。行列は例示のために用いられる抽象概念であり、配列は特定の例示であり、ツリーは様々な異なる形式で記憶され得ることが理解されるべきである。
【００４８】
例えば、ｓｐｔ［ｉ，ｊ］配列の行０（図２１の２００１）は図１３に示される最短経路ツリーを表す。この行２００２の列０における０の値は、０がそのツリーのルートとしてそれ自身の前身であることを示す。列１における０の値（図２１における２００３）は、ノード０がツリー内のノード１の前身であることを示す。図１３のグラフに同等の関係が見受けられ、ここでルート１３１はノード１（１３３）に至る辺１３２を有する。図１３においてノード５（１３４）は到達不能であり、従って、ｓｐｔ行列の行０においてその前身として５を有する（図２１の２００５）。
【００４９】
所与のルートの関する最短経路ツリーを計算する際に、インプリケータは、同じ価格を有するが実際（直接）の経路とは異なる時間優先を有する暗示（間接）の経路が存在することを判断してもよい。それが実際の経路よりも遅い時間優先を有する暗示（間接）の経路に遭遇する場合、それは黙示の辺のコレクションにおいて「暗示の辺」として暗示の経路を記録してもよい。図１２では、このような経路が辺１２１、１２２、１２３及び１２４によって形成され、それにより経路６−５−４−１−０を形成している。図１９における最短経路ツリーは、それがｓｐｔ［ｉ，ｊ］配列に記憶される前身の配列外で表されなければならないことを示すために破線でこの黙示の辺を示す。１つの実装では、こうした辺のための容器は、黙示の辺コレクションと呼ばれ、それは同じルートを起点とする最短経路ツリーと関係付けられる。
【００５０】
既に述べたように、非負の再重み付けされた辺価格は、市場の買う側における最高の経路と売る側における最高の経路との間の差異を反映する。特に、仮想のノード０から最短経路ツリーで到達可能な全てのノードに対する再重み付けされた価格は、それら自体が０になるであろう。最短経路ツリー内の他のルートノードとノード０との間の経路についての価格は、対応する市場におけるビッド／アスクスプレッドを表すであろう。この特性は、スプレッド約定にまで及ぶが、スプレッド市場の何れの側も理論上はノード０をルートとする最短経路ツリーの一部であり得るので、より多くの計算を必要とする。最短経路ツリーのこの特性は、以下に記載される所定のフィルタリング動作に利用される。
【００５１】
既に述べられたように、マッチエンジンは、着信する注文イベントをそれらが記憶された辺に引き起こす変化に応じてインプリケータイベントとして分類する。図２２は、このようなイベントの例示的なリスト及びそれらがどのように発生し得るかを示す。１つの実装では、こうしたイベントは、インプリケータをマッチエンジンコアの他の部分と接続するインターフェースで定義される方法に対応する。
【００５２】
インプリケータは、もしあれば、どのツリーが変更された辺によって変更されるか、及びもしあれば、こうしたツリー内のどのノードが再計算される必要があるかを決定するために現在の暗示の注文を分析する。各インプリケータイベントは、分析が再計算用の全てのツリー及びその全てのノードを単純に示すデフォルトイベントを含む分析を有する。
【００５３】
全てのイベントに関して、ルート集合及びグローバル変化集合が存在する。ルート集合は、変更によって影響を受けるツリーのルートノードを含む。ルート集合内の各ルートは、そのルートを起点とするツリー内で影響を受けるノードを含むルート固有の変化集合を有する。また、全てのツリー内で影響を受けた全てのノードを含むグローバル変化集合も存在し、それは数学的にルート固有の変化集合の和集合として表現されてもよい。ルート集合は空であることが可能であり、この場合、変化集合は自動的に空である。ルート集合が非空である場合、任意の又は全ての変化集合が空であることが可能である。こうした集合は、アルゴリズムの説明するために用いられる数学的抽象概念であり、インプリケータがそれらを明示的に構築する必要はない。
【００５４】
１つの実装では、ｓｐｔ［ｉ，ｊ］配列は、所与の辺を含むツリーを識別するために使用され得る。例えば、１−０辺は、図１４（１４１）、図１５（１５１）、図１７（１７１）及び図１８（１８１）に見受けられるように、ルート１、２、４及び５に対するツリー内に存在することが知られている。ｓｐｔ［ｉ，ｊ］配列において、各ツリーは行によって表される。各ノードは列によって表される。列０（２００２）において、１は行１、２、４及び５における０の前身である。これらは１−０辺を含むツリーである。
【００５５】
１つの実装では、ｓｐｔ［ｉ，ｊ］配列は、所与の辺を含まないがその辺の特性が変化した後にその辺を含むかもしれないツリーを識別するために使用され得る。例えば、図２０では、ノード１がそれ自体以外の前身を有するツリーは、０、３及び６として列１において識別可能である。次に、こうしたルートの何れが現在のインプリケータイベントに関連するかを決定するためにさらなる基準が適用される。このような基準は、グラフを表すデータ構造から得ることが出来るノード及び辺の特性を用いて計算される。このような構造の例は隣接行列及び隣接リストであるが、本発明は、インプリケータによって用いられるノード及び辺の特性が適時に得ることが出来る限り、如何なる特定の表現にも依存しない。
【００５６】
現在のインプリケータイベントとの関連でどのルートのツリーが再計算されるべきかを決定するための追加の基準の適用は、例えば、１−０辺における改善がツリー０、３及び６における０の前身になる１を生ずる「より良い最高の（Ｂｅｔｔｅｒ  Ｂｅｓｔ）」イベントで例示され得る。しかしながら、この場合、ノード０は計算から除外される。すなわち、ノード０に至る辺における改善はノード０を起点とするツリーにおいて何も改善することが出来ないので、そのツリーは再計算されるべきではない。本質的に、ルートは前身を持たない。この場合に続いて、ノード３が除外される。これは図１６に例示されており、そこには、１−０辺が任意の経路を３から０に改善するために、経路が３から０を通って１へ行き、そして再び０に戻らなければならず、これはグラフが含まないと知られているサイクルを含むことが示されている。異なった方法で表現されると、１−０の改善を加えた３から１への経路は既存の３から０への経路よりも悪いであろう。最後に、この場合、ノード６についてのツリーはこうした基準に基づいて除外されない。ノード６をルートとするツリーは再計算され、その場合は、６−５−４−１−０経路が見つけられてより良い価格をもたらし（図１２を参照）、最短経路ツリーはこの経路を含むように更新され（図１９を参照）、そして経路はルートの暗示の辺コレクションから削除されるであろう。
【００５７】
既に述べられたように、インプリケータは、暗示の計算の独立サブグループを多数の独立実行スレッドに割り当てる。１つの実装では、インプリケータは、プログラミング言語によって提供されるスレッドオブジェクトを拡張するオブジェクトを生成する。各スレッドがルートに対応するように、約定グリッドにおいてスレッドがノードごとに生成される。各スレッドは、それ自体の最短経路ツリー、暗示の辺コレクション及びツリーのルートと関係付けられる他のデータを維持する。１つの実装では、最短経路ツリーは、既に述べられたように、前身、価格、時間及び量を含む１次元配列のコレクションによって表現されてもよい。オブジェクトは、内部変数を設定する方法及び実行を開始するための「ラン（ｒｕｎ）」方法を有する。方法は、ローカル変数を読み込み且つ書き込みしてもよいが、親スレッドと共有する変数を読み込むことのみが許可される。このようにして、並列的に実行が進行し得る。
【００５８】
１つの実装では、インプリケータは、ルート固有の変化集合を決定し又は計算の範囲を減らすために使用され得るスレッドにパラメータを渡す。例えば、「より悪い最高の（Ｗｏｒｓｅ  Ｂｅｓｔ）」イベントにおいて、暗示の注文が悪化し又は現状を維持し得ること、すなわち全く改善の可能性がないことが前もって知られる。直接の経路（すなわち、単一の実際の辺）が最高の経路であるノードは、この経路を新しく発見された間接の（すなわち、暗示の）経路で置き換えることが出来ない。このようなノードは、ルート固有の変化集合から除外され得る。
【００５９】
既に述べられたように、送信されるデータは生成する可能性がある収入に従って優先順位付けされ得るので、インプリケータは、市場データにおける暗示の注文の報告を最も大きなビジネス価値を有するものに限定するようにフィルタリング基準を設定する。これは本明細書において収益整形と呼ばれる技術である。マッチエンジンの他の部分又は取引システムの他の構成要素がついていくことが出来なければ、並列の計算による速度増加は十分に活用されないので、これは本発明の重要な部分である。本発明はマッチエンジン内で実行されるフィルタリングと共に記載されているが、フィルタリングが取引システムの他の箇所で実行されることも可能である。
【００６０】
例えば、個別に又は組み合わせて適用され得る２つの単純な基準がある。すなわち、即時のビッド／アスクスプレッドと最後の取引以降のイベント数である。多様なフィルタが可能であること及び具体的詳細が取引のビジネスニーズにより決定されることが理解される。１つの実装では、こうしたフィルタリング基準は、例えばＸＭＬ等の適切な言語で一連の表現として表され得るフィルタリングポリシーに基づくであろう。
【００６１】
この例を続けると、図２２は、取引所がフィルタリングポリシーを生成するのに使用し得るデータを示す。図示の２つの約定は非常に異なる特性を有するが、いずれもビッド／アスクスプレッドと取引されたロット数との間で同じ基本的な関係を示す。上のグラフに示される約定２２１は、ニューヨーク商品取引所で丸一日に電子的に取引する原油についての期近限月のアットザマネー（ａｔ−ｔｈｅ−ｍｏｎｅｙ）プットオプションである。３７０ロットのみが取引されている。第２の約定２２３は、ニューヨーク商品取引所で丸一日に電子的に取引される期近限月のｅｍｉＮＹ（登録商標）天然ガス先物約定である。１００００ロット以上が取引されている。いずれの場合も、取引の大部分は、取引前のビッド／アスクスプレッドが１のティックにあったときに行なわれる（２２２、２２４）。効果はより大量に取引される約定である先物約定２２３においてより強力であるが、取引数が比較的少ない場合であるオプション約定２２１においてもまだ存在している。多数の約定に当てはまる関係が、フィルタリングポリシーにおける一般規則を定義するために使用されてもよい。
【００６２】
図示の約定に関して、取引データは、ビッド／アスクスプレッドがより小さい暗示の注文が取引される可能性が高いことを示す。しかしながら、市場データにおける暗示の注文は、スプレッドを可視的に狭め又は追加の量を提供する取引を促進する可能性が高い。従って、閾値基準は、暗示の注文の計算及び市場データの公示に別個に適用されるように定義されてもよい。取引所の暗示の注文は取引閾値より低いビッド／アスクスプレッドにより全ての市場に対して計算されてもよいが、ビッド／アスクスプレッドが暗示により影響を受けるのに十分大きく又は取引所が注文の存在（すなわち、流動性）を示すことを希望する市場に対してのみ報告される。適切な閾値は約定ごとに異なり、フィルタリングポリシーにおける約定固有の規則で表されてもよい。
【００６３】
この例示をさらに続けると、図２２は、原油オプション約定２２１における取引の頻度を推定するためにも使用され得る。基本のＣＨＬ８約定の価格が変化していたときにこの約定において２４の取引が短期間の間に行なわれた場合であっても、こうした期間は持続時間が数分であり、従って、この約定に関係付けられるメッセージの割合は比較的に低くなっている。約定の取引が稀にしか起こらない場合、２つの取引間の長い遅延の後に、次の取引の前の別の長い遅延が続く可能性がある。この文脈において、長いとは数秒以上のことである。取引の多くが６又は７ティックのビッド／アスクスプレッドで行なわれるとしても、７から６へのスプレッドの改善は１０００の事象ごとに１取引を生ずるのみであってもよい。このような場合、時間又は比率の基準がフィルタリングポリシーにおける規則の一部を形成してもよい。
【００６４】
１つの実装では、マッチエンジンは、その初期化の一部として、又は取引システムの操作者によってそうするように命令されたときにフィルタリングポリシーを含むファイルを読み取る。フィルタリングポリシーは、インプリケータに渡され得る時間、割合、及び閾値基準に変換され、インプリケータから適切な形式で適切なサブセットが各実行スレッドに渡され得る。各スレッドに渡される基準は、以前の注文及び取引に依存してもよく、従って、インプリケータ又はマッチエンジンの他の部分によって時宜更新されてもよい。
【００６５】
１つの実装では、インプリケータは、スレッドにビッド／アスクスプレッド閾値を提供する。先に示唆したとおり、ビッド／アスクスプレッド閾値は全ての約定に共通であってもよく、又は個々に特殊化されてもよい。最も単純な形式では、再重み付けされた辺に対してダイクストラのアルゴリズムを使用して計算されるノード価格が、最高ビッドと最高アスクとの間の差がこの閾値よりも大きいことを示す場合、市場データは、公示するためにインプリケータに戻されない。着信する注文がその価格に一致する場合、暗示の注文自体はマッチエンジンの中に留まって、取引されることが理解される。その結果、取引者は、自身の注文に対して考えられる最高のフィル（ｆｉｌｌ）を受け取る。また、公示された市場データが、もはや存在しない暗示の注文の削除を示さなければならないことが理解される。
【００６６】
１つの実装では、インプリケータは、スレッドにメッセージ数閾値も提供する。メッセージ数閾値は全ての約定に共通であってもよく、又は個々に特殊化されてもよい。最高ビッドと最高アスクとの間の差がビッド／アスクスプレッド閾値よりも大きい場合、市場データは、暗示されたものを完了したメッセージ以降のメッセージがメッセージ数閾値を越えるまで公示されない。
【００６７】
当業者であれば、ダイクストラのアルゴリズムが重みの順に最短経路ツリーにノードを加えることを理解するであろう。結果として、ビッド／アスクスプレッド基準は、報告する市場データの量を減らすだけでなく、アルゴリズムを早期に終了させることにより、計算時間をさらに短縮する。最も低く重み付けされたノードは、最も高い取引の可能性を有するので、最も高い収入の可能性を有する。
【００６８】
１つの実装では、アダプテーション層は、メッセージが到着している速度を計測して、これを入力速度閾値及び出力市場データ量目標のテーブルと比較してもよい。後者は、取引システムに固有であり、そのハードウェア及びソフトウェア要素の能力によって決定される。アダプテーション層は、閾値を超過しており、メッセージ速度が隣接する閾値によって確立された範囲内に留まる可能性がある場合、対応する市場データ量目標をマッチエンジンコアに伝達する。計測された取引特性に基づくエントリを有する第２のテーブルは、各約定に対して目標市場データ速度とビッド／アスクスプレッド基準とを関係付ける。この第２のテーブルは、マッチエンジンコアに対して利用可能であり、外部の取引システムの状態に応じてビッド／アスクスプレッド基準を変化させるためにインプリケータによって使用されてもよい。この技術は、適応インプリケーションと呼ばれる。
【００６９】
先に述べたとおり、インプリケータは、別個のＣＰＵで独立スレッドの実行を管理するための基準を設定する。１つの実装では、こうした基準は、順に実際に実行スレッドを管理するコンピュータのオペレーティングシステムの一部に基準を渡すプログラミング言語及びその関連ツールの一部として提供されるランタイムライブラリコードに渡される。例えば、一般に入手可能なバージョンのＪａｖａ（登録商標）及びＣ＋＋は、この種類のライブラリコードを提供する。
【００７０】
最後に、インプリケータは、フィルタリングされた市場データを、取引システムの他の構成要素へ市場データとして公示するためにアダプテーション層によって変換に適した単一メッセージに統合する。１つの実装では、各スレッドは、スレッドの最短経路ツリー内のノードと関係付けられる約定に対する暗示の市場データの追加、容量更新及び削除のリストを作成する。スレッドがインプリケータに計算終了の信号を送ると、インプリケータは、現在のイベントに関する変更コレクションリストにリストを追加する。最後のスレッドが報告したか又は何らかの他の基準が満たされた場合、インプリケータは、外部の取引システムによって期待されるメッセージの形式に変換するために、コレクションを市場データスレッドに渡す。この市場データスレッドは、図２に示されるアダプテーション層２０２と関係付けられ得る。
【００７１】
図２３は、Ｊａｖａ（登録商標）で実装されて、１６個のプロセッサを有するホストで実行されるマッチエンジンの性能を例示する。一番上の画像は、全ての最短経路ツリーが単一のスレッドで計算されるシングルスレッドモードで実行されるウインドウズタスクマネージャを示す。下の画像は、マルチスレッドモードでの実行を示す。マルチスレッドバージョン（４７９対４２３）には５６以上のアクティブなスレッドがある。これは、並列に計算され得る４９のツリー及びインプリケータが直接の制御を持たないＪａｖａＶｉｒｔｕａｌＭａｃｈｉｎｅ又は他のシステム要素によって加えられる７の追加のスレッドに対応する。４９のツリーは、最初の１２限月に仮想ノードを加えた完全なインプリケーションにより４の生産物から生ずる。
【００７２】
図２３の下の画像では、右端の最もアクティブなプロセッサは市場データの公示を処理している。市場データは、「ムービーモード」と呼ばれる非常に単純な周波数フィルタでフィルタリングされており、市場データの更新は、全ての約定に対する固定速度で公示され、速度は、人間の視覚システムの応答時間によって決定される。１つの実装では、フィルタリングは、利用可能なハードウェアから最大量の収入を生成する市場データを取得するためにさらに洗練され得る。
【００７３】
例示の実装では、暗示の注文を決定するコンピュータ実行方法が提供される。図２４を参照すると、例示の方法２４００は、第１の組の１つ以上の実際の注文を受信するステップ２４１０と、第１の組の実際の注文の中で１つ以上の暗示の注文を識別するステップ２４２０と、暗示の注文に対応する市場データを識別するステップ２４２５と、少なくとも一つの追加の実際の注文を受信するステップ２５３０と、少なくとも一つの追加の実際の注文の取引可能性を決定するステップ２４４０と、第１の組の実際の注文の中で休止の注文の組を識別するステップ２４４５と、休止の注文の組の中で１つ以上の暗示の注文を識別するステップ２４５０とを備える。
【００７４】
１つ以上の実際の注文を受信するステップ２４１０は、ネットワークを介して実際の市場注文を受信することを含み得る。１つ以上の注文は、リアルタイムで又は既定のスケジュールに従ってバッチ処理で受信され得る。１つの実装では、１つ以上の実際の注文は、注文提出点を介してクライアントから送信され、既定の基準に対して確認され、且つマッチエンジンで受信され得る。実際の注文は、最高のビッドデータ及び最高のアスクデータを含み得る。
【００７５】
第１の組の実際の注文の中で１つ以上の暗示の注文を識別するステップは、インプリケータを使用して暗示の注文を識別することを含み得る。上述のとおり、暗示の注文は、マッチエンジンモデル化言語及びグラフ理論を用いて決定され得る。１つ以上の暗示の注文を識別することは、１つ以上のノードを含む１つ以上の最短経路ツリーの計算を含み得る。
【００７６】
また、ステップ２４２５のように、暗示の注文及び／又は実際の注文と関係付けられる市場データも識別され得る。市場データは、証券又は約定の識別子、買い又は売りの側、価格、約定数等のその価格で取引するために利用可能な量、実際又は暗示の量の起源、及び新しい価格の追加、価格レベルの削除、価格レベルで利用可能な量の変更若しくは市場の状態の変化等、市場データの識別又は公示を引き起こした取引システムによる動作を含み得る。市場状態によっては、市場データは、クライアントが基礎価格及び量を解釈するのを支援するための概要又は指示データを含んでもよい。また、メッセージの形式で送信される市場データは、その計算又は識別の時間及び場所、それを受信する資格のある名前等、その出所を識別して受け渡しを容易にするためのデータを含んでもよい。
【００７７】
追加の実際の注文が受信され得る、２４３０。追加の実際の注文は、注文提出点を介してクライアントから送信され、既定の基準に対して確認され、且つマッチエンジンで受信され得る。１つの実装では、マッチエンジンを使用して、追加の実際の注文は、取引可能な一致が存在するかを決定するために実際の又は暗示の注文に対して比較され得る。追加の実際の注文が実際の又は暗示の注文に対して取引可能であると決定されると、マッチエンジンは、上述の取引を実行することが出来る。追加の実際の注文が実際の又は暗示の注文に対して取引可能でない場合、追加の実際の注文は、実際の注文の第１の組に追加され得る。追加の実際の注文は、後の処理のために記憶され得る。追加の注文は、１組の休止の注文に追加され得る。
【００７８】
追加の実際の注文を受信すると、こうした追加の実際の注文は、有向辺に対する影響又は最短経路ツリーに対する影響に従って分類され得る。追加の実際の注文は、より良い最高価格、より悪い最高価格、最高レベルにおけるより大きな量、及び最高レベルにおけるより少ない量を含む１つ以上のカテゴリによって分類され得る。他のカテゴリが使用されてもよい。ツリーが追加の実際の注文により影響を受けると決定されると、ツリー又はツリーのノードに対する新しい値が計算され得る。
【００７９】
１組の休止の注文は、追加の実際の注文が実際の又は暗示の注文に対して取引可能であると分かった後、第１の組の実際の注文から残る実際の及び／又は暗示の注文を識別することにより決定され得る。休止の注文の組を識別した後２４４５、上述したのと類似の方法で、追加の暗示の注文が計算され得る２４５０。
【００８０】
追加の実際の注文と他の実際の注文又は暗示の注文との間の暗示の注文及び取引可能な一致は、上述したように、電子取引システムを介してメッセージの形式で送信され得る。
【００８１】
他の実装が可能である。例えば、１つの実装では、暗示の注文を計算及び取引するコンピュータ実行方法が提供される。第１の組の１つ以上の実際の注文が、マッチエンジンで受信され得る。１つ以上の実際の注文は第１の組の実際の注文の中にあり得るが、ここで、価格が実際の注文間で一致せず、量が不十分であり若しくは一致せず、又は取引を遂行するために要求される１つ以上の実際の注文が第１の組の実際の注文の中に存在しないという理由で、個々の実際の注文は互いに取引可能でない。第１の組の実際の注文は、マッチエンジン内にある又は電子取引システムの他の場所に記憶された休止した実際の注文の組にさらに属し得る。休止の注文の組は、第１の組の実際の注文の全部又は一部を含み得るが、ここで実際の注文は取引が不一致であり及び／又は実行された取引において取引されていない。
【００８２】
１つ以上の暗示の注文は、第１の組の実際の注文内の実際の注文から計算され得る。実際の又は暗示の注文の関連グループが互いにリンクされ又は関係付けられる。ここで、関連する注文の価格が暗示の注文の価格を計算するために追加され又は結合される。適切なスケーリング及び再重み付けが関連する注文のグループを形成するために使用され得る。暗示の注文の量は、リンクされた一連の注文における価格レベル又は互いのレベルにおいて利用可能な量から決定され得る。このように、暗示の注文の価格及び量が決定されて、関連する暗示の注文のグループが形成され得る。関連する暗示の注文のグループは、並列の実行スレッドに割り当てられて、全体としてマッチエンジン及び電子取引システムの性能及び効率を最適化するように管理され得る。
【００８３】
暗示の注文が計算されて関連するグループに関連付けられると、実際の及び暗示の注文に対応する市場データが識別され得る。市場データは、暗示の注文及び／又は対応する市場データのいずれかを公示するための基準を有し得る。
【００８４】
追加の実際の注文が、マッチエンジンによって受信され得る。追加の実際の注文は、第１の組の実際の注文、休止の注文の組、又は１つ以上の関連する暗示の注文のグループに対する実際の注文の取引可能性を決定するために分析され得る。その価格及び量によって実際の注文が市場の反対側で未だ受信されていない実際の注文と取引されることを可能にする１組の実際の注文を暗示の注文が表すという原理に基づいて、休止した組又は第１の組の実際の注文内の１つ以上の実際の注文に対して、追加の実際の注文が取引可能である。
【００８５】
追加の実際の注文が休止した組又は第１の組の実際の注文内の１つ以上の実際の注文に対して取引可能である場合、取引が実行され得る。
【００８６】
休止した組及び／又は第１の組の実際の注文は、実行される取引を反映するために更新され得る。さらに、取引が実行されない場合、休止した組又は第１の組の実際の注文は、マッチエンジンで受信されるさらに別の実際の注文又は任意の他の新しく受信される注文を反映するために更新され得る。１つ以上の暗示の注文は、更新された休止の組の中で識別され得る。
【００８７】
本明細書に記載の主題及び機能動作の実施形態は、デジタル電子回路で、又は本明細書で開示された構造、その構造的均等物を含む、コンピュータソフトウェア、ファームウェア若しくはハードウェアで、又はそれらの１つ以上の組み合わせで実装され得る。本明細書に記載の主題の実施形態は、１つ以上のコンピュータプログラム製品、すなわち、データ処理装置の動作を制御することにより又は制御するために実行されるコンピュータ可読媒体に符号化されるコンピュータプログラム命令の１つ以上のモジュールとして実装され得る。コンピュータ可読媒体は、機械可読記憶装置、機械可読記憶基板、メモリ装置、又はこれらの１つ以上の組み合わせであり得る。「データ処理装置」という用語は、例として、プログラム可能プロセッサ、コンピュータ、又はマルチプロセッサ若しくはコンピュータを含むデータを処理するための全ての機器、装置、及び機械を包含する。装置は、ハードウェアに加えて、当該コンピュータプログラムのための実行環境を生成するコード、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、又はこれらの１つ以上の組み合わせを構成するコードを含み得る。
【００８８】
コンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、又はコードとしても知られる）は、コンパイラ型又はインタープリタ型言語を含む任意の形態のプログラミング言語で書かれてもよく、スタンドアロンプログラム又はモジュール、コンポーネント、サブルーチン、若しくはコンピュータ環境で使用される他の適切なユニットを含む任意の形態で展開される。コンピュータプログラムは、ファイルシステムにおけるファイルに必ずしも対応しない。プログラムは、他のプログラム又はデータ（例えば、マークアップ言語文書に記憶される１つ以上のスクリプト）を保持するファイルの一部に、当該プログラムに専用の単一ファイルに、又は複数の統合ファイル（例えば、１つ以上のモジュール、サブプログラム、又はコードの一部を記憶するファイル）に記憶され得る。コンピュータプログラムは、１箇所に設置され、又は複数箇所に分散され、且つ通信ネットワークによって相互接続される１つ又は複数のコンピュータで実行されるように展開され得る。
【００８９】
本明細書に記載のプロセッサ及び論理フローは、入力データを操作して出力を生成することにより機能を遂行するように１つ以上のコンピュータプログラムを実行する１つ以上のプログラム可能プロセッサにより実行され得る。また、専用論理回路、例えば、ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）又はＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）によって、プロセッサ及び論理フローが実行可能であり、またそれらとして装置が実装されることも可能である。
【００９０】
コンピュータプログラムを実行するのに適したプロセッサは、例として、汎用及び専用マイクロプロセッサ、並びにデジタルコンピュータの任意の種類の１つ以上の任意のプロセッサを含む。一般に、プロセッサは、読み取り専用メモリ又はランダムアクセスメモリ又はその両者から命令及びデータを受信するであろう。コンピュータの必須要素は、命令を実行するプロセッサ並びに命令及びデータを記憶する１つ以上のメモリ装置である。また、一般に、コンピュータは、データを記憶するために１つ以上の大容量記憶装置、例えば、磁気、光磁気ディスク、又は光ディスクを含み、これらからデータを受信し、又はデータを転送し、又はその両方のために動作可能に結合されるであろう。しかし、コンピュータは、このような装置を有する必要はない。さらに、コンピュータは、別の装置に、例を挙げると、携帯電話、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、形態音楽プレーヤ、ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）受信機に組み込まれ得る。コンピュータプログラム命令及びデータを記憶するのに適したコンピュータ可読媒体は、全ての形式の、不揮発性メモリ、媒体及びメモリ装置を含んでおり、例として、半導体メモリ装置、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及びフラッシュメモリ装置、磁気ディスク、例えば、内蔵型ハードディスク又は取り外し可能ディスク、光磁気ディスク、並びにＣＤ−ＲＯＭ及びＤＶＤ−ＲＯＭディスクを含む。プロセッサ及びメモリは、専用論理回路が補足され、又は組み込まれ得る。
【００９１】
ユーザとの相互作用を提供するために、本明細書に記載の主題の実施形態は、ユーザに情報を表示するための、ディスプレイ、例えば、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）若しくはＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）モニタ、ユーザがコンピュータに入力を提供するキーボード及びポインティング装置、例えば、マウス又はトラックボールを有する装置で実装され得る。他の種類の装置もユーザとの相互作用を提供するためにも使用され得る。例えば、ユーザに提供されるフィードバックは、任意の形式の感覚フィードバック、例えば、視覚フィードバック、聴覚フィードバック、又は触覚フィードバックであり、ユーザからの入力は、聴覚、音声、又は触覚入力を含む任意の形式で受信され得る。
【００９２】
本明細書に記載の主題の実施形態は、例えば、データサーバとして、バックエンド要素を含み、又は、ミドルウェアコンポーネント、例えば、アプリケーションサーバを含み、又はフロントエンドコンポーネント、例えば、本明細書に記載の主題の実装とユーザが相互作用出来るグラフィカルユーザインターフェース又はウェブブラウザを有するクライアントコンピュータ、又はこのようなバックエンド、ミドルウェア、又はフロントエンドコンポーネントの１つ以上の任意の組み合わせを有するコンピュータシステムで実装され得る。システムの構成要素は、任意の形式又は媒体のデジタルデータ通信、例えば、通信ネットワークにより相互接続され得る。通信ネットワークの例は、ＬＡＮ（ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）及びＷＡＮ（ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）、例えば、インターネットを含む。
【００９３】
コンピュータシステムは、クライアント及びサーバを含むことが出来る。クライアント及びサーバは、一般に、互いから離れており、典型的には、通信ネットワークを介して相互作用する。クライアント及びサーバの関係は、各コンピュータで実行されて、互いにクライアント−サーバの関係を有するコンピュータプログラムによって生ずる。
【００９４】
本明細書は多くの詳細を含むが、これらは本発明の又はクレームされるものの範囲を限定するものと解釈されるべきではなく、むしろ本発明の特定の実施形態に固有の特徴の説明として解釈されるべきである。また、別個の実施形態との関連で本明細書に記載される所定の特徴は、単一の実施形態で組み合わせて実装され得る。逆に、単一の実施形態との関連で記載される多様な特徴も、複数の実施形態で別個に、又は任意の適切なサブコンビネーションで実装され得る。さらに、特徴は所定の組み合わせで動作するように先に記載され且つこのように当初クレームされ得るが、クレームの組み合わせから１つ以上の特徴が場合によっては組み合わせから切り取られて、クレームされた組み合わせはサブコンビネーション又はサブコンビネーションの変化に向けられてもよい。
【００９５】
同様に、動作は特定の順番で図面に描かれているが、これは、このような動作が図面に示された特定の順番で又は連続する順に実行されること、又は所望の結果を達成するために全ての例示の動作が実行されることを必要とするものと理解されるべきではない。特定の状況では、マルチタスク及び並列処理が好都合であり得る。さらに、上記の実施形態における様々なシステム要素の分離は、全ての実施形態でこのような分離を必要とすると理解されるべきではない。また、記載されたプログラム要素及びシステムは、一般に、単一のソフトウェア製品に統合され、又は複数のソフトウェア製品にパッケージ化され得ることが理解されるべきである。
【００９６】
このように、本発明の特定の実施形態が説明された。以下のクレームの範囲には他の実施形態が含まれる。例えば、クレームに記載の動作は、異なる順番で実行されることが可能であり、それでも所望の結果を達成することが出来る。
【図１】
0005623427.tif 000002
【図２】
0005623427.tif 000003
【図３】
0005623427.tif 000004
【図４】
0005623427.tif 000005
【図５】
0005623427.tif 000006
【図６】
0005623427.tif 000007
【図７】
0005623427.tif 000008
【図８】
0005623427.tif 000009
【図９】
0005623427.tif 000010
【図１０】
0005623427.tif 000011
【図１１】
0005623427.tif 000012
【図１２】
0005623427.tif 000013
【図１３】
0005623427.tif 000014
【図１４】
0005623427.tif 000015
【図１５】
0005623427.tif 000016
【図１６】
0005623427.tif 000017
【図１７】
0005623427.tif 000018
【図１８】
0005623427.tif 000019
【図１９】
0005623427.tif 000020
【図２０】
0005623427.tif 000021
【図２１】
0005623427.tif 000022
【図２２】
0005623427.tif 000023
【図２３Ａ】
0005623427.tif 000024
【図２３Ｂ】
0005623427.tif 000025
【図２４】
0005623427.tif 000026