(57)【要約】      （修正有）【課題】特定のアイテムが１つのデータセットに含まれるか否かを決定する方法を提供する。【解決手段】データセットは複数のサブセットに分割され、特定のアイテムがいずれかのサブセットに含まれる可能性があるか否かが判定される。可能性があると判定されたサブセットは第１のメモリーから該第１のメモリーよりアクセス待ち時間が短い第２のメモリーに転送され、特定のアイテムが転送されたサブセット内に含まれるか否かが評価される。存在しない場合、当該特定のアイテムが当該データセットに存在しないことが決定される。【選択図】図３
2020017296.tif 000002
【特許請求の範囲】
【請求項１】
複数のアイテムを含むデータセットに特定のアイテムが含まれるか否かを決定する、コンピュータで実行される方法であって、前記複数のアイテムが第１のメモリーであって該第１のメモリーよりもアクセス待ち時間が短い第２のメモリーに接続されており、前記第１のメモリーと前記第２のメモリーは、前記第１のメモリーと前記第２のメモリーとの間の単一の転送操作によって前記第１のメモリーから前記第２のメモリーへ転送されるアイテムの最少の数によって特徴づけられており、前記方法は、
前記第１及び第２のメモリーに接続されたプロセッサにより、前記データセットの前記複数のアイテムを複数の重複しないサブセットに分割するステップであって、各重複しないサブセットに含まれる前記複数のアイテムのアイテム数が前記最小の数を越えないようにされており、各重複しないサブセットの中に含まれるアイテムが共通するサブセット属性を有し且つ該サブセット属性が他のサブセットのサブセット属性とは異なるように分割するステップと、
前記プロセッサにより、前記複数のサブセットの内の何れか１つのサブセットのサブセット属性が前記特定のアイテムの属性と共通するか否かを判定するステップと、
前記プロセッサにより、前記特定のアイテムの属性と共通するサブセット属性を有すると判定されたサブセットの前記第１のメモリーから前記第２のメモリーへの転送を引き起こすステップと、
前記プロセッサにより、前記判定されたサブセットに前記特定のアイテムが含まれているか否かを決定するために前記第２のメモリーにおける前記判定されたサブセットを評価するステップであって、前記特定のアイテムが前記第２のメモリーにおける前記判定されたサブセットに含まれていないと決定された場合には、前記特定のアイテムは前記複数のアイテムの中に存在しないと決定する、ステップと、
を含む複数のアイテムを含むデータセットに特定のアイテムが含まれるか否かを決定する方法。
【請求項２】
前記特定のアイテムと前記複数のアイテムの属性が当該アイテムを表す値であり、前記サブセットを判定するステップは、前記特定のアイテムの値が各サブセットに含まれる複数のアイテムの値の範囲内にあるか否かを判定する、請求項１に記載の方法。
【請求項３】
前記第１のメモリーがコンピュータのメインメモリーであり、前記第２のメモリーがキャッシュメモリーであり、前記第１のメモリーから前記第２のメモリーへ移動されることが可能なデータの最小サイズがキャッシュラインサイズである、請求項１に記載の方法。
【請求項４】
転送されるアイテムの前記最少の数は、前記第１のメモリーから前記第２のメモリーへと転送されることが可能なデータの最少量によって決定される、請求項１に記載の方法。
【請求項５】
前記データセットの前記複数のアイテムが、金融市場で金融商品の売り買いをする注文を示すデータを含む、請求項１に記載の方法。
【請求項６】
前記特定のアイテムが複数ある場合、前記判定するステップ、転送を引き起こすステップ及び評価するステップが、該複数の特定のアイテムの各々に対して繰り返され、前記方法は更に、前記複数のアイテムを含む前記データセットに存在すると決定された全てのアイテムのデータセットを生成するステップを含む、請求項１に記載の方法。
【請求項７】
前記分割するステップが、単一の転送操作によって転送することのできる前記アイテムの最少の数に基づいて、前記データセットの中の前記複数のアイテムを保存するのに要求とされるサブセットの最小数量を決定するステップと、全サブセットの数量を、決定されたサブセットの最小数量に制限するステップと、を含む、請求項１に記載の方法。
【請求項８】
前記判定されたサブセットを評価するステップが、フォワード・イテレーション（ｆｏｒｗａｒｄ  ｉｔｅｒａｔｉｏｎ）法、再帰法、リバース・オーダー（ｒｅｖｅｒｓｅ  ｏｒｄｒ）法又は番兵法（ｓｅｎｔｉｎｅｌ  ｍｅｔｈｏｄ）、又はそれらの組み合わせを含む、請求項１に記載の方法。
【請求項９】
複数のアイテムを含むデータセットに特定のアイテムが含まれるか否かを決定するシステムであって、前記複数のアイテムは第１のサイズと第１のアクセス待ち時間を有する第１のメモリーに保存され、前記第１のメモリーは、前記第１のサイズよりも小型の第２のサイズと前記第１のアクセス待ち時間よりも短い第２のアクセス待ち時間を有する第２のメモリーと接続されており、前記第２のメモリーは更に前記第1のメモリーから前記第２のメモリーへと移動されることが可能な最少データ量によって特徴づけられており、前記システムは、
第３のメモリーに保存され、プロセッサによって実行可能とされるコンピュータ実行可能プログラムコードであって、前記プロセッサに、
前記データセットの前記複数のアイテムを複数の重複しないサブセットに分割するステップであって、各重複しないサブセットのデータ量が、前記第１のメモリーから前記第２のメモリーへと移動されることが可能な前記最少データ量を超えることはないようにされ、前記重複しない複数のサブセットの各々に含まれるアイテムが共通するサブセット属性を有し且つ該サブセット属性が他のサブセットのサブセット属性とは異なるように分割する、ステップと、
前記特定のアイテムの属性が前記複数のサブセットのうちの前記特定のアイテムが前記複数のアイテムのうちの１つであるとしたときに前記特定のアイテムを含むことになるサブセット、を判定するステップと、
前記特定のアイテムの属性と共通するサブセット属性を有すると判定されたサブセットの前記第１のメモリーから前記第２のメモリーへの転送を要求するステップと、
前記判定されたサブセットに前記特定のアイテムが含まれているか否かを決定するために前記第２のメモリーにおける前記判定されたサブセットを評価するステップであって、前記特定のアイテムが前記第２のメモリーにおける前記判定されたサブセットに含まれていないと決定された場合には、前記特定のアイテムは前記複数のアイテムの中に存在しないと決定される、ステップと、
を実行させるコンピュータ実行可能プログラムコードと、
を備える複数のアイテムを含むデータセットに特定のアイテムが含まれるか否かを決定するシステム。
【請求項１０】
前記特定のアイテムと前記複数のアイテムの属性が前記アイテムを表す値であり、前記サブセットを判定するステップは、前記特定のアイテムの値が各サブセットに含まれる複数のアイテムの値の範囲内にあるか否かを判定する、請求項９に記載のシステム。
【請求項１１】
前記第１のメモリーがコンピュータのメインメモリーであり、前記第２のメモリーがキャッシュメモリーであり、前記第１のメモリーから前記第２のメモリーへ移動されることが可能なデータの最小サイズが、キャッシュラインサイズである、請求項９に記載のシステム。
【請求項１２】
前記キャッシュラインサイズは、３２バイト、６４バイト、１２８バイト及び２５６バイトからなる群から選ばれる、請求項１１に記載のシステム。
【請求項１３】
前記データセットの前記複数のアイテムが、金融市場で金融商品の売り買いをする注文を示すデータを含む、請求項９に記載のシステム。
【請求項１４】
前記プロセッサは更に、対象のデータセットにおける複数のアイテムの各々に対して、前記判定するステップ、引き起こすステップ及び評価するステップを繰り返すように構成され、前記コンピュータ実行可能プログラムコードは、前記データセットに存在すると決定された前記対象のデータセットからの全てのアイテムの共通部分のデータセットをプロセッサに生成させるように、前記プロセッサによって実行可能である、請求項９に記載のシステム。
【請求項１５】
前記プロセッサは更に、前記第１のメモリーから前記第２のメモリーへ転送されるデータの最少量に基づいて、前記データセットの前記複数のアイテムを保存するのに要求されるサブセットの最少数量を決定するように構成され、前記サブセットの全数量を、前記決定されたサブセットの最少数量に制限する、請求項９に記載のシステム。
【請求項１６】
前記プロセッサは更に、フォワード・イテレーション法、再帰法、リバース・オーダー方法又は、番兵法を用いて、前記判定されたサブセットを評価するように構成されている、請求項９に記載のシステム。
【請求項１７】
複数のアイテムを有するデータセットに特定のアイテムが含まれるか否かを決定するシステムであって、前記複数のアイテムは第２のメモリーと接続された第１のメモリーに保存され、前記第１のメモリーと前記第２のメモリーは、前記第１のメモリーと前記第２のメモリーとの間の単一の転送操作によって前記第１のメモリーから前記第２のメモリーへ転送されるアイテムの最少の数によって特徴づけられており、前記第２のメモリーは前記第１のメモリーよりアクセス待ち時間が短いものとされており、前記システムは、
前記第１のメモリーと前記第２のメモリーに接続されて、前記データセットの前記複数のアイテムを複数の重複しないサブセットに分割するように構成されているデータ・アレンジャー（ｄａｔａ  ａｒｒａｎｇｅｒ）であって、前各重複しないサブセットに含まれる前記複数のアイテムのアイテム数が、前記アイテムの最少の数を超えないようにされており、前記複数の重複しないサブセットはそれぞれ、当該重複しないサブセットの各々に含まれるアイテムが共通するサブセット属性を有し且つ該サブセット属性が他のサブセットのサブセット属性とは異なるようにする、データ・アレンジャーと、
前記第１のメモリーと前記第２のメモリーに接続され、前記複数のサブセットの内の何れか１つのサブセットのサブセット属性が前記特定のアイテムの属性と共通するか否かを判定し、共通する属性を有すると判定した場合、判定したサブセットを前記特定アイテムが前記複数のアイテムのうちの１つである可能性のあるものとして特定する、データ・ロケーター（ｄａｔａ  ｌｏｃａｔｏｒ）と、
前記第１のメモリーと前記第２のメモリーに接続され、前記第１のメモリーから前記第２のメモリーへの前記特定されたサブセットの転送を引き起こさせて、前記特定のアイテムが前記特定されたサブセットの中に含まれているかどうかを決定するために前記第２のメモリーにおける前記特定されたサブセットを評価するように構成されているデータ・コンパレーター（ｄａｔａ  ｃｏｍｐａｒａｔｏｒ）であって、前記特定のアイテムが前記第２のメモリーにおける前記特定されたサブセットに含まれていないと決定された場合には、前記特定のアイテムは前記複数のアイテムの中に存在しないと決定される、データ・コンパレーターと
を含む複数のアイテムを含むデータセットに特定のアイテムが含まれるか否かを決定するシステム。
【請求項１８】
前記第１のメモリーがコンピュータのメインメモリーであり、前記第２のメモリーがキャッシュメモリーであり、前記第１のメモリーから前記第２のメモリーへ移動することが可能なデータの最小サイズがキャッシュラインサイズであり、移動可能な前記アイテムの最少の数が前記キャッシュラインサイズに保存することが可能なアイテムの最大の数である、請求項１７に記載のシステム。
【請求項１９】
複数のアイテムを含むデータセットに特定のアイテムが含まれるか否かを決定するシステムであって、前記複数のアイテムが第２のメモリーに接続されている第１のメモリーに保存され、前記第１のメモリーと前記第２のメモリーは、前記第１のメモリーと前記第２のメモリーとの間の単一の転送操作によって、前記第１のメモリーから前記第２のメモリーへ転送されるアイテムの最少の数によって特徴づけられており、前記第２のメモリーは前記第１のメモリーよりアクセス待ち時間が短いものとされており、前記システムは、
前記データセットの前記複数のアイテムを複数の重複しないサブセットに分割する手段であって、各重複しないサブセットに含まれる前記複数のアイテムのアイテム数が、前記最少のアイテム数を超えないようにされており、前記重複しない複数のサブセットの各々に含まれるアイテムが共通するサブセット属性を有し且つ該サブセット属性が他のサブセットのサブセット属性とは異なるように分割する手段と、
前記複数のサブセットの内の何れか１つのサブセットのサブセット属性が前記特定のアイテムの属性と共通するか否かを判定する手段と、
前記第１のメモリーから前記第２のメモリーへの前記判定されたサブセットの転送を引き起こす手段と、
前記判定されたサブセットに前記特定のアイテムが含まれているか否かを決定するために前記第２のメモリーにおける前記判定されたサブセットを評価する手段であって、前記特定のアイテムが前記第２のメモリーにおける前記判定されたサブセットに含まれていないと決定された場合には、前記特定のアイテムは、前記複数のアイテムの中に存在しないと決定される、評価する手段と、
を含む複数のアイテムを含むデータセットに特定のアイテムが含まれるか否かを決定するシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
シカゴ・マーカンタイル取引所（ＣＭＥ）のような、本明細書では「取引所」とも言う先物取引所等の金融商品取引システムは、例えば、先物及び先物オプションといった金融商品が取引される１つの契約市場を提供している。先物とは、先渡し又は商品先物取引に関する現金決済のための金融商品又は現物商品の売り買いのための全ての約定を指定するために用いられる用語である。先物取引は、将来の所定の時点における特定価額での商品の売り買いの法的拘束力のある合意である。オプションとは、特定の時点内での特定価額での基礎商品（この場合は、先物契約）を売り買いする権利であり義務ではない。契約の履行において引き渡される商品又はその代わりに、市場価額が先物契約の最終決済価額を決定する商品は、当該契約の基礎商品又は「原資産」として知られている。各先物契約の条件は、契約の基礎商品の仕様、当該商品の品質、数量、決済日及び契約決済手段に関して標準化されている。現金決済は、先物契約の決済方法であり、当該契約が、先物契約で決定された価額において、基礎商品の現物の売買に影響を及ぼすよりはむしろ、現金における契約に関連する損失を支払うか、利益を受け取ることにより、契約が満了する際に現金決済によって、当事者が最終決済を行う。
【０００２】
一般的に、取引所は、集中した「清算機関」を提供し、この清算機関を通じてなされる全ての取引が、相殺又は引き渡されるまで、毎日、確認、突き合せ及び決済されなければならない。清算機関は、取引所の１つの付属機関で、取引所の１つの運営機関であり、取引口座を決済し、取引を清算し、履行保証金を集めて維持し、引渡を規制し、取引データを報告する責任がある。清算機関の本質的役割は、信用リスクを緩和することである。清算とは、清算機関が、先物契約の各売主に対して買主となり、各買主に対して売主となる手続きで、ノベーション（当事者交代；ｎｏｖａｔｉｏｎ）ともいわれ、各契約の履行を保証することで、売主と買主を契約違反のための金銭上の損失から守る責任を有する。清算人は、清算機関を通じて取引の清算を行う資格を有する会社である。
【０００３】
現在の金融商品取引システムは、取引者は、売り約定又は買い約定の注文を取引所が維持・管理する、「レスティング（Ｒｅｓｔｉｎｇ）」注文ともいわれる、以前に受け取られたが、満たされていないことを示すデータが含まれている注文台帳データベースに提出することを可能にしている。突き合わせエンジンは、特定の入来注文（ｉｎｃｏｍｉｎｇ  ｏｒｄｅｒ）に関し、注文台帳データベースを、適切な反対注文を特定するために、例えば、受注と同じ金融商品であって、同等かより良い価額を検索して、受注を突き合せる為に取引所によって利用される。言い換えれば、データセットは、従前に受領されて満たされていない注文すなわちレスティング注文を含んでいてもよい。入来注文が受領されると、レスティング注文のデータセットが、入来注文をレスティング注文に突き合せるであろうデータすなわち交差データとして知られるものを見つけようと、検索される。例えば、買い待ち注文と入来売り注文が、１つの原資産の同じ数量又は金額であってもよく、それ故に整合するデータすなわち交差データを有する。１つのデータセットの１つ以上のアイテムが第２データセットに存在するかどうかを決定するプロセスは、２つの集合の共通部分を決定することであると言うことができる。数学的には、ＡとＢの２つの集合の共通部分は、ＡとＢに共通な要素の集合である。
【０００４】
集合の共通部分は、コンピュータ科学における基本的な問題であり、多様なアプリケーションを有する。例えば、データベースの質問評価（ｑｕｅｒｙ  ｅｖａｌｕａｔｉｏｎ）における索引論理積（Ｉｎｄｅｘ−ＡＮＤｉｎｇ）は、特性索引表の集合の共通部分を計算する。集合の共通部分を計算する幾つかの確立された方法があり、例えば、ソートに基づく方法、ハッシュに基づく方法、またはサーチ・ツリー法を利用することができる。
【０００５】
データセットの共通部分の決定において、データセットにおけるアイテムが比較され得る。このアイテムの比較には、メモリーを異なるメモリーロケーション及びレベルのメモリーに転送することを必要とする。これらの転送と大型のデータセットの保存に含まれるであろう大量のデータのために、非常に多数の転送が、すべてのデータセットの共通部分を決定するために必要とされるであろう。例えば、多数のデータ転送が、１つのデータセットの１つのアイテムの個別の値をもう一つのデータセットで検索するために必要とされるであろう。それ故、データセットが、何千、何百万のアイテムを有する場合、データセットの共通部分の決定は、コンピュータ処理的に、非常に高負荷（ｉｎｔｅｎｓｉｖｅ）である。
【０００６】
一般的に、コンピュータは、ＳＲＡＭとＤＲＡＭのバンク等の、基板に取り付けられたＲＡＭメモリーを含む。一般的に、基板に取り付けられたメモリーは、メモリー階層を形成し、例えば、ＳＲＡＭは、容量がより小さいがアクセスはより速く、ＤＲＡＭは、容量はより大きいがアクセス時間はより長い。この種類のメモリー階層は、複数のレベルの記憶装置、ＲＡＭ及びメインコンピュータメモリーを通じて存在する。また、各レベルのメモリーは、１回のメモリー転送におけるメモリーレベル間で転送するのに必要な最少量のメモリーを有するであろう。キャッシュメモリーでは、この最少量のメモリーがキャッシュライン又はブロックとして知られている。キャッシュライン又はブロックは、一般的に、１６バイトから２５６バイトの範囲の大きさに固定されているが、特定のハードウェア構成やアプリケーションに適した大きさであろう。
【図面の簡単な説明】
【０００７】
【図１】開示された実施形態を実行するために使用される実例システムである。
【０００８】
【図２】データセットの共通部分の発見のためのフローチャートである。
【０００９】
【図３】データセットの共通部分の決定の実施例である。
【００１０】
【図４】データセットの共通部分の発見のための一般的なコンピュータシステムの実施形態である。
【発明を実施するための形態】
【００１１】
開示された実施形態は、データセット間の共通部分の決定に関するものである。特に、第１のデータセットにおけるアイテムは、１回のメモリー処理によって第２のデータセットに存在するかしないかが決定され得る。
【００１２】
複数のデータセットにおけるアイテムの間の比較を行うために、比較されているアイテムを含むメモリーは、複数のメモリーレベルの間を転送される必要がある。比較されているアイテムが設定されたキャッシュラインサイズよりも小さいメモリーを用いて保存されていても、全キャッシュラインが、転送されるように要求される。各メモリー転送または処理はそれぞれ、システム時間と計算資源を費やす。この様にして、複数のデータセットにおける複数のアイテムが比較され何の共通部分も決定されないたびに、より多くのアイテム及びデータが、当該複数のデータセット全体を比較するために、転送されることが必要となる。それ故に、共通部分は、計算資源を節約するために最少量のメモリー処理を用いて決定され、より少ない時間で共通部分を見つけることが重要である。また、アイテムが有効な態様で保存されるようにメモリーは有効に使われることが重要である。
【００１３】
ある実施形態では、第１データセットにおける複数のアイテムは、メモリーに蓄えられるが、多くのアイテムが複数のサブセットにグループ化されるように配列され、各サブセットは、キャッシュミス／フェッチ／ブロック転送操作等の単一の処理における複数のレベルのメモリー間で転送される最少の数のアイテムに基づく、最大の大きさを有する。当該複数のアイテムは更にグループ化され、各サブセットがグループ独自の属性を有するように編成される。第２データセットからのアイテムは、編成された第１データセットの唯一のサブセットとともにグループの属性を共有する。それから、当該サブセットは、複数のレベルのメモリー間を移動し、第２データセットからのアイテムと比較され、当該アイテムがサブセットに存在するかどうかを決定する。第２データセットからの当該アイテムが当該サブセットに存在しない場合、当該アイテムは、第１データセットに存在しないこととなる。
【００１４】
データセットは、一つの構成からもう一つの構成へと変換することができる。ある実施形態では、データセットの中の複数のアイテムは、任意の種類の構成から、メモリーの中のアイテムのグループ化を含む、キャッシュメモリーへの転送のためのキャッシュライン等の、複数のメモリーレベルの間で転送するのに必要とされる最小限の量のデータによって制約される構成へと再編される。ある実施形態では、特定の構成のためのキャッシュラインは１２８バイトであり、データセットの複数のアイテムは、３２ビットの整数値であってもよい。それ故、最大３２個のアイテムがサブセット又はグループに存在可能である。
【００１５】
サブセットの属性は、任意の技術を用いて、グループに与えられまたは決定されてもよい。例えば、ハッシング、マスキング又はソート技術を、当該属性が当該サブセットの内容を示し、異なるデータセットからのアイテムが当該サブセットにあってもよいように、利用することができある。ハッシュ技術では、アイテムの内容は、当該アイテムを分類するアルゴリズムに従う。当該分類は、特定の配列されたグループの属性であり得る。マスキング技術では、1バイトの中の複数のビットを、アイテム又はひと組のアイテムを表すか、又は関連させるために用いる２進値を作るために、ビットごとの演算において、オン、オフ又はオンからオフへの反転（又はその逆）のいずれかに設定することができる。当該２進値は、特別に配列されたグループの属性である。ソート技術では、ある特定の範囲の全てのアイテムは、サブセット内に存在する。ソート技術は、従来の辞書における欄外見出語に類似している。アイテムがデータセット内にある場合、特定の境界特性により形成される範囲に存在する。これらの境界特性は、サブセットの属性であり得る。複数の技術の如何なる組み合わせもまた利用できる。
【００１６】
図１は、データセット共通部分の決定に利用される実例システム１０５を示している。システム１０５は、命令１１０、１２０、１３０を含むプロセッサ１４０を含み、当該命令を実行することを許容するように構成することが可能なコンピュータのハードウェアに接続している。プロセッサ１４０は、図４のコンピュータシステム４００に関して記載されるプロセッサ４０２等のプロセッサである。プロセッシング・ハードウェア１４０は、第１のメモリー１０１と第２のメモリー１０２に接続している。ある実施形態では、第１のメモリーと第２のメモリーは、プロセッシング・ハードウェア１４０の一部として考えられている。別の実施形態では、第１のメモリー１０１と第２のメモリー１０２は、プロセッシング・ハードウェア１４０とは別にあると考えられる。図１に示されるプロセッシング・ハードウェア１４０の動作は、持続性のあるコンピュータ可読性媒体４２２に保存されるコンピュータ実行可能命令によって抑制されている。
【００１７】
システム１０５は、複数のアイテムを含むデータセットに特定のアイテムが含まれることを決定するように構成され、当該特定のアイテムと当該複数のアイテムの各々がアイテム属性により特徴づけられ、当該複数のアイテムが第１の配列により特徴づけられ第２のメモリー１０２に接続された第１のメモリー１０１に保存され、第１のメモリー１０１と第２のメモリー１０２は、単一の転送操作により第１のメモリーから第の２メモリーへと転送されるアイテムの最少の数によって特徴付けられる。
【００１８】
第１のメモリー１０１と第２のメモリー１０２は、如何なる種類のメモリーであってもよい。第１のメモリー１０１と第２のメモリー１０２は、異なるレベルのメモリーの階層構造に存在している。コンピュータの保存におけるメモリーの階層構造は、回答時間によって階層構造における各レベルを区別する。高い実行性を企図する際の多くのトレードオフには、例えば、各要素の大きさと技術等のメモリー階層構造が含まれる。そこで、多様な構成要素は、メモリーの階層構造（ｍ１、ｍ２、…、ｍｎ）を形成し、各要素ｍｉは、ある意味、当該階層構造の次に高い要素ｍｉ‐１が続く。より高いレベルによる待機を限定するために、より低いレベルがバッファーを埋めることで反応し、それから信号を発して転送をアクティブにする。複数のレベルの階層構造が互いに部分集合となる。一般的に、あるレベルの全てのデータは、下位のレベルでも見つけられ、下位のレベルの全てのデータはそれより下位のレベルで見つかる等、階層構造の最下位に到達するまで続く。例えば、第１のメモリー１０１はディスクメモリーであり、第２のメモリー１０２はプロセッサ・キャッシュ・メモリー又はメインメモリーとプロセッサの間に位置する中間キャッシュメモリーである。
【００１９】
第１のメモリー１０１と第２のメモリー１０２の間のデータの転送は、単一のメモリー転送又は処理と考えられる第１のメモリー１０１と第２のメモリー１０２の間で転送されるデータの最少量によって特徴づけられる。例えば、第１のメモリー１０１はディスクメモリーであり、第２のメモリー１０２はプロセッサー・キャッシュメモリーであり、それらの間で転送されるデータの最少量は、３２バイト、６４バイト、１２８バイト又は２５６バイトである。介在する構成要素及び装置は、第１のメモリーと第２のメモリー１０２の間の接続箇所に存在し、当該構成要素及び装置の各々は、異なる量のメモリー又はデータを転送し通過させ全体のメモリー処理を完成させる。又は、多くの副次的処理が、第１のメモリー１０１から第２のメモリー１０２へとデータを転送する過程で起こるが、第１のメモリー１０１と第２のメモリー１０２の間の単一の処理は、第１のメモリー１０１と第２のメモリー１０２の間の単一の転送の開始のデータ量によって決められる。
【００２０】
システム１０５は、第１のメモリー１０１と第２のメモリー１０２に接続されているデータ・アレンジャー（ｄａｔａ  ａｒｒａｎｇｅｒ）１１０を含む。データ・アレンジャー１１０は、第１の配列とは異なる第２の配列に当該データセットの複数のアイテムを再配列するように構成され、第２の配列は、複数のアイテムの重複しないサブセットを含み、その結果各々の重複しないサブセットに含まれる当該複数のアイテムのアイテム数は、アイテムの最少の数を超えず、複数の重複しないサブセットの各々は、当該サブセットに含まれる複数のアイテムのうちの当該アイテムの属性に基づいたサブセットの属性によって特徴づけられる。ある実施形態では、データ・アレンジャー１１０は、論理コード又はコンピュータ実行可能コードであり、データセットを受け取り、配列アルゴリズムを通じてデータセットの当該複数のアイテムを処理し、配列されたデータセットを創る。
【００２１】
システム１０５は、第１のメモリー１０１と第２のメモリー１０２に接続されたデータ・ロケーター（ｄａｔａ  ｌｏｃａｔｏｒ）１２０を含む。データ・ロケーター１２０は、特定のアイテムの当該アイテム属性と複数のサブセットの各々の当該サブセット属性に基づき、複数のサブセットのうちの、特定のアイテムが複数のアイテムのうち１つであったとしたときに当該特定アイテムを含むことになるサブセットを探し出す。ある実施形態では、データ・ロケーター１２０は、論理コード又はコンピュータ実行可能コードであり、アイテム属性と探し出されたサブセットと関連する対応する属性に基づいて、サブセットを探し出す。
【００２２】
システム１０５は、第１のメモリー１０１と第２のメモリー１０２に接続された、データ・コンパレーター（ｄａｔａ  ｃｏｍｐａｒａｔｏｒ）１３０を含む。データ・コンパレーター１３０は、特定されたサブセットの第１のメモリー１０１から第２のメモリー１０２への転送を引き起こし、第２のメモリー１０２における特定されたサブセットを評価し、当該特定のアイテムが当該サブセットに含まれるかどうかを決定するように構成されており、当該特定のアイテムが第２メモリーにおける特定されたサブセットに含まれていないと決定された場合、当該特定アイテムは当該複数のアイテムには含まれないと決定される。ある実施形態では、データ・コンパレーター１３０は、論理コード又はコンピュータ実施可能コードであり、特定されたサブセットを評価し、特定のアイテムが当該サブセットに含まれるかどうかを決定し、当該特定のアイテムは、特定されたサブセットに含まれていないと決定されると、当該特定のアイテムが当該複数のアイテムに存在しないと決定される。
【００２３】
ここで、「接続されている」という語句は、直接的に接続されているか、１つ以上の中間構成要素を通じて間接的に接続されていることを意味する。当該中間構成要素には、ハードウェアに基づく構成要素とソフトウェアに基づく構成要素の双方が含まれる。更に、係属中の請求項での使用を明らかにし、本明細書によって公に知らせるために、当該語句「＜Ａ＞、＜Ｂ＞、…及び＜Ｎ＞の少なくとも１つ」若しくは、「＜Ａ＞、＜Ｂ＞、…及び＜Ｎ＞の少なくとも１つ若しくはそれらの組み合わせ」は、最広義の意味で出願人が定義づけをし、出願人が反対の明示的な意思表示をしない限り、この前後で他の黙示的定義に優先し、Ａ、Ｂ、…及びＮからなるグループから選択された１つ以上の要素、つまり、他の要素を含むか、他の要素の１つ以上の組み合わせの、Ａ、Ｂ、…及びＮの要素の１つ以上の組み合わせを意味しており、組み合わせにおいては、挙げられていない追加の要素もまた含まれる。
【００２４】
図２は、データセットの共通部分の発見のためのフローチャートを示している。フローチャートには、データセット内にある複数のアイテムを特定の大きさで複数のサブセット属性を有するサブセットに再配列し（ブロック２１０）、サブセットの属性を有するサブセットを特定し（ブロック２２０）、特定されたサブセットの転送を引き起こし（ブロック２３０）、特定のアイテムを含むことに関し特定されたサブセットを評価すること（ブロック２４０）が含まれる。
【００２５】
ある実施形態では、図２のフローチャートは、複数のアイテムを含むデータセット内に特定のアイテムが含まれることを決定するコンピュータ実行方法であり、特定のアイテムと複数のアイテムの各々が、アイテム属性によって特徴づけられ、当該複数のアイテムは、第１の配列により特徴づけられ、第２のメモリーに接続されている第１のメモリーに保存され、第１のメモリーと第２のメモリーは、その間の単一の転送操作により第１のメモリーから第２のメモリーに転送されるアイテムの最少の数によって特徴づけられる。
【００２６】
ある実施形態では、第１のメモリーはコンピュータメインメモリーであり、第２のメモリーはプロセッサ・キャッシュ・メモリーであり、アイテムの最小の数は、第１のメモリーから第２のメモリーへと移動することのできるデータの最小の大きさとして決定される。ある実施形態では、データの最小の大きさは、第２のメモリーのためのキャッシュ・ライン・サイズである。ある実施形態では、転送されるアイテムの最小の数は、第１のメモリーから第２のメモリーへと移動されるデータの最少量によって決定され、当該データの最少量は、３２バイト、６４バイト、１２８バイト又は２５６バイトである。
【００２７】
当該方法には、データセットの複数のアイテムを第１の配列とは異なる第２の配列に再配列すること（ブロック２１０）が含まれ、第２の配列は、当該複数のアイテムと重複しない複数のサブセットを含み、その結果、重複しないサブセットの各々に含まれる複数のアイテムのアイテム数は、アイテムの最小の数を超えず、重複しない複数のサブセットの各々は、当該サブセットに含まれる複数のアイテムのうちの当該アイテムのアイテム属性と関係づけられたサブセット属性によって特徴付けられている。ある実施形態では、第２の配列には、ハッシュ表と関連するハッシュ関数が含まれる。別の実施形態では、サブセット属性は、アイテム階級区分であり、例えば、１００から１５０の整数の範囲がサブセットに含まれ、当該サブセット属性は、そのようなものとして示される。当該階級区分にはまた、サブセットにおける値の内容に対応する二進値の階級が含まれる。特定のアイテム属性はまた、値であってもよく、特定のアイテムの内容の二進値であってもよい。第２の配列は、第１のメモリーに保存される。
【００２８】
ある実施形態では、第２の配列に再配列することには、単一の転送操作で転送できるアイテムの最少の数に基づいてデータセット内にある複数のアイテムを保存するのに要するサブセットの最小の数を決定し、決定された最少の数のサブセットにより第２のデータセット内のサブセットの総数に制限することが含まれる。例えば、当該データセットは、各３２ビットの整数値である３７５４個のアイテムを有する。また、単一の転送で転送される最少の数のアイテムは、２５６バイトの第２のメモリー・キャッシュラインにより制限される。それ故、転送可能な最少の数のアイテム、つまり、サブセット内のアイテムの最大の数は、６４である。このことから、制限されるサブセットの総数とサブセットの最小可能数は、第２の配列においては、５９であると決定することが可能である。
【００２９】
当該方法はまた、特定のアイテムのアイテム属性と複数のサブセットの各々のサブセット属性に基づき、当該特定のアイテムが当該複数のアイテムのうちの１つであれば当該特定のアイテムを含むような複数のサブセットのうちの１つのサブセットを特定すること（ブロック２２０）を含む。ある実施形態では、特定には、ハッシュ関数の利用が含まれ、特定のアイテム属性をサブセット属性と関係づける。
【００３０】
当該方法にはまた、第１のメモリーから第２のメモリーへの特定されたサブセットの転送を引き起こすこと（ブロック２３０）も含まれる。ある実施形態では、メモリー・コントローラー又はキャッシュ・コントローラーは、実際に、特定されたサブセットの転送を引き起こし、プロセッサは、当該転送を要求する。しかしながら、他の実施形態では、プロセッサは、必要に応じて又は直接、転送を引き起こすと考えられる。
【００３１】
当該方法には更に、第２のメモリーにおける特定されたサブセットを評価し（ブロック２４０）、当該特定のアイテムが当該サブセットに含まれるかどうかを決定することが含まれるが、特定のアイテムが第２のメモリーにある特定されたサブセットに含まれていないと決定された場合、当該特定のアイテムが当該複数のアイテムには存在しないと決定される。ある実施形態では、特定されたサブセットを評価することには、フォワード・イテレーション（ｆｏｒｗａｒｄ  ｉｔｅｒａｔｉｏｎ）法、再帰法、リバース・オーダー（ｒｅｖｅｒｓｅ  ｏｒｄｒ）法又は、番兵法（ｓｅｎｔｉｎｅｌ  ｍｅｔｈｏｄ）が含まれる。
【００３２】
ある実施形態では、特定すること、引き起こすこと、及び評価することは、第２のデータセットの複数のアイテムの各々に対して繰り返され、当該方法には更に、データセットに存在すると決定される第２のデータセットからの全てのアイテムの共通部分のデータセットを生成することが含まれる。ある実施形態では、特定のアイテムとデータセットは、電子金融市場の注文台帳に保存される買い注文又は売り注文を示す記録であり、共通部分のデータセットは、突き合せ注文を含むデータセットである。
【００３３】
ある実施形態では、再配列すること（ブロック２１０）又は配列することは、上記の方法の他の部分（ブロック２２０、ブロック２３０、ブロック２４０）の十分前に起こることが可能で１度だけなされる必要があるが、上記の方法の残りは多数のアイテムがデータセットに存在するかどうかを決定するために繰り返し実行されうる。
【００３４】
ある実施形態では、入来注文が受領され、レスティング注文のデータセットが入来注文をレスティング注文に突き合せ又は交わるデータを検索する。例えば、注文台帳の待機中の売り注文又は買い注文等のアイテムは、第１の配列とは異なる第２の配列へと配列され又は再配列され（ブロック２１０）、第２配列は、複数の重複しない待機中の注文アイテムのサブセットを含み、その結果、各々の重複しないサブセットに含まれる複数のアイテムのアイテム数は、アイテムの最少の数を超えず、重複しない複数のサブセットの各々は、含まれる複数のアイテムのアイテム属性と関連するサブセット属性に特徴づけられる。注文が受領され、サブセットが、受領された注文の特定のアイテムのアイテム属性と配列された注文台帳の複数のサブセットの各々のサブセット属性に基づいて特定されるが（ブロック２２０）、当該サブセットは、受領された注文の特定アイテムが注文台帳の複数のアイテムの１つであるとしたときに受領された注文の特定アイテムを含むことになる、複数のサブセットのうちのサブセットである。注文台帳の特定されたサブセットは第１のメモリーから第２のメモリーへと転送される（ブロック２３０）。注文台帳の転送されたサブセットは入来注文の特定のアイテムが存在するかどうかを決定するために評価される（ブロック２４０）。
【００３５】
ある実施形態では、アーカイブ市場データと金融上のメッセージデータは、ネットワーク構成のアーカイブデータセットとして保存される。アーカイブデータセットには、他のマーケットパラメータつまり取引所で取引された１つ以上の製品の履歴価額又は履歴価値、一人以上のマーケット参加者の過去の注文その他の活動等の過去の取引行為を示すデータ又はそれらの組み合わせが含まれる。アーカイブデータセットは、どの期間にも及ぶ。アーカイブデータセットには、多数のサーバーに保存される１０億を超える個別の記録又はデータアイテムが含まれる。検索データセットを含む別の集合のデータには、アーカイブマーケットデータに含まれるアイテムが含まれる。例えば、ユーザーは、特定の期間に所定の製品に関する履歴価額データの見直しを望み、又は、ユーザーは、特定の期間に特定の市場参加者の取引行為、又は、取引所で取引される製品の特定のサブセットに関して見直すことを望む。検索データセットは、多くの重複しないサブセットを含む配列に配列し又は再配列する（ブロック２１０）。配列のサブセットは、検索データセットのアイテムの最小数を超えることはない。当該配列の特定のサブセットは、アーカイブデータセットのアイテムの属性に関係するサブセット属性を用いて特定される（ブロック２２０）。特定のサブセットが、サーバーのメモリー階層構造又はサーバーとの伝達におけるワークステーションコンピュータで構築されたメモリーの間で転送されることとなり（ブロック２３０）、特定のサブセットは、アーカイブデータセットに当該アイテムが含まれることに関して評価される（ブロック２４０）。この様に、検索データセットとアーカイブデータセットの間の共通部分を決定するのに必要なデータ又はメモリー処理の数は、大幅に減少する。例えば、共通部分の総数は、アーカイブデータセットのアイテムの数に等しいデータ処理数と共に決定される。更に、データ処理数は、アーカイブデータセットのアイテム数に等しくなるように保証される。
【００３６】
図３は、データセットの共通部分の決定の実施例を示している。図３において、データセット３１０は、複数のサブセット３３０、３３１、複数のアイテム３２５及び複数のサブセット属性３５０、３５５を有する第２のデータセット３２０へと配列される。また別のデータセット３６０からの特定のアイテム３２１、３２２は、第２データセット３２０に存在するか存在しないかが決定される。
【００３７】
ある実施形態では、データセット３１０は、各サブセットのデータ量が、第１のメモリーから第２のメモリーへと移動することのできるデータの最小量を超えないように、複数のサブセット３３０、３３１を有する配列３２０へと配列される。複数のサブセットの各々は、サブセット３３０に含まれる複数のアイテム３２５の各々のアイテム属性に基づくサブセット属性によって特徴づけられる。複数のサブセット３３０の複数のアイテム３２５は、値又は特徴に基づき分類され、分類された属性に基づいて、複数のサブセットに細かく分けられる。
【００３８】
ある実施形態では、データセット３２０の配列における各アイテム３２５は、３２ビットの整数値である。また、配列されたデータセット３２０のサブセット３３０、３３１の大きさは、６４バイトのキャッシュラインサイズによって制限される。それ故、サブセット３３０、３３１は、最大１６個のアイテム３２５を有することになる。３２個のアイテムを含むデータセットを考え合わせると、データセット３２０の配列は、２つのサブセット３３０、３３１を有する。当該実施形態では、２つのサブセットは、サブセット３３０、３３１の最大許容数である。
【００３９】
各サブセット３３０、３３１はまた、関連する属性３５０、３５５を有する。ある実施形態では、関連するサブセットの属性３５０、３５５は、サブセット３３０、３３１に含まれる、ある範囲のアイテム３２５を特定する。
【００４０】
ある実施形態では、プロセッサが用いられ、特定のアイテム３２１、３２２のアイテム属性及び配列された複数のサブセット３３０、３３１のサブセット属性に基づき、特定のアイテム３２１、３２２が当該データセット３１０に含まれるとしたときに当該特定のアイテム３２１、３２２を含むことになるサブセット３３０、３３１を特定する。また、プロセッサを用いて、特定したサブセット３３０、３３１を第１のメモリーから第２のメモリーへと転送することを要求する。特定されたサブセット３３０、３３１が第２のメモリー上にあるときに、プロセッサは、第２のメモリーにおける特定されたサブセット３３０、３３１を評価し、特定のアイテム３２２、３２１が特定されたサブセット３３０、３３１に含まれるかどうかを決定する。特定のアイテム３２２、３２１が特定されたサブセット３３０、３３１に存在しない場合、当該特定のアイテム３２２、３２１は、当該データセット３１０に含まれないことが決定される。
【００４１】
図３を参照すると、ある実施形態では、別のデータセット３６０にある特定の値３２２は、アイテム３２２の数値（この場合は１４５）のアイテム属性を示す。当該値は、サブセット属性３５０（この場合は、８５から１６０の範囲）に関係づけられている。そして、関係づけられたサブセット属性３５０を用いて、特定のアイテム３２２がデータセット３１０に存在すれば特定のアイテム３２２が存在すると思われる特定のサブセット３３０を特定する。特定されたサブセット３３０は、特定のアイテム３２２の存在についての特定されたサブセット３３０の評価を容易にする異なるレベルのメモリーに転送される。評価は、任意の方法によって、異なるレベルのメモリーを用いて、プロセッサによって実行される。例えば、フォワード・イテレーション法、再帰法、リバース・オーダー法又は、番兵法を利用することができる。最終的には、本実施形態では、特定のアイテム３２２が特定されたサブセット３３０に存在したことが評価を通じて決定されたことをもって、特定のアイテム３２２がデータセット３１０に存在していたと決定されることになる。図３から見てわかるように、他方のデータセット３６０からの特定のアイテム３２２は、データセット３１０におけるアイテム３２５として存在する。
【００４２】
しかしながら、異なるサブセット３３１に関係付けられる別の特定のアイテム３２１は、同じ方法を用いて異なるサブセット３３１に存在しないと決定される。他方の特定のアイテム３２１が他方のサブセット３３１に存在しないことが決定されるとき、これは、特定の値３２１がデータセット３１０に存在しないことを示す。他の如何なるデータ転送も本決定をするためになされる必要がなく、仮に特定の値３２１がデータセット３１０に存在した場合には、データセット３２０の特定の配列の設計上の理由で、サブセット３３１に存在していたことになる。
【００４３】
図４を参照すると、データセットの共通部分の発見又は決定のための一般的なコンピュータシステムの実施例が示されている。コンピュータシステム４００は、メモリー４０４と接続されたプロセッサ４０２を含み、バス４０８を用いて、ディスプレイ４１４、ユーザー入力装置４１６及び通信インターフェース４１８と通信している。
【００４４】
ある実施形態では、メモリー４０４は、多数の組のメモリーを含むことができる。例えば、メモリー４０４は、レベル１のキャッシュ４０９、レベル２のキャッシュ４０７、レベル３のキャッシュ４０６及び／またはメインメモリー４０５を含んでもよい。メモリー４０４におけるメモリーの組の組み合わせは、第１のサイズと第１のアクセス待ち時間を有する第１のメモリーを含み、第１のメモリーは、データセット及び第２のデータセットを保存するように構成されている。メモリー４０４はまた、第１のメモリーに接続され、第１のサイズより小型の第２のサイズと、第１のアクセス待ち時間よりも短い第２のアクセス待ち時間を有する第２のメモリーを含み、第２のメモリーは更に、第１のメモリーから第２のメモリーへと移動することができる最少のデータ量によって特徴づけられる。第１のメモリーと第２のメモリーは、メモリーのレベルが異なる。ある実施形態では、第１のメモリーは、メインメモリー４０５であり、第２のメモリーは、キャッシュメモリー４０６、４０７、４０９である。別の実施形態では、第１のメモリーは、レベル２のキャッシュ４０７であり、第２のメモリーはレベル１のキャッシュ４０９である。
【００４５】
ある実施形態では、コンピュータシステム４００は、複数のアイテムを含むデータセットに特定のアイテムが含まれることを決定する際に利用され、特定のアイテムと複数のアイテムの各々は、アイテム属性によって特徴付けられ、複数のアイテムは、第１の配列によって特徴づけられる。プロセッサ４０２は、データセットの複数のアイテムを第１の配列とは異なる第２の配列に再配列するよう構成されており、第２の配列は、複数のアイテムの複数の重複しないサブセットを含み、各々の重複しないサブセットのデータ量は、第１のメモリーから第２のメモリーへと移動することのできる最少のデータ量を超えず、複数の重複しないサブセットの各々は、当該サブセットに含まれる複数のアイテムの当該アイテムの当該アイテム属性の特徴に基づくサブセット属性によって特徴づけられる。プロセッサ４０２はまた、特定のアイテムのアイテム属性と複数のサブセットの各々のサブセット属性に基づいて、複数のサブセットのうちの、特定のアイテムが当該複数のアイテムのうちの１つであるとしたときに当該特定のアイテムを含むことになるサブセット、を特定するように構成される。プロセッサ４０２はまた、特定されたサブセットの第１のメモリー４０５から第２のメモリー４０６への転送を要求するように構成されている。プロセッサ４０２はまた、第２のメモリーにおける特定されたサブセットを評価し、当該特定のアイテムが当該サブセットに含まれるかどうかを決定するように構成され、当該特定のアイテムが第２のメモリー４０６の特定されたサブセットに含まれないと決定された場合には、当該特定のアイテムは当該複数のアイテムに存在しないことが決定される。
【００４６】
コンピュータシステム４００は、コンピュータシステム４００に本明細書で開示された１つ以上の方法又はコンピュータに基づく機能を実行させるように遂行させることのできる一組の命令４１２を含むことができる。コンピュータシステム４００は、独立型装置として作動し、又は、例えば、ネットワーク４２０を用いて、他のコンピュータ又は周辺機器に接続される。データ・アレンジャー１１０、データ・ロケーター１２０又はデータ・コンパレーター１３０等の上記の如何なる構成要素も、コンピュータシステム４００又はコンピュータシステム４００における構成要素である。コンピュータシステム４００は、突き合せエンジン、マージン・プロセッシング、又は、シカゴ・マーカンタイル取引所等の取引所の代わりの支払又は清算機能を実行し、開示された実施形態は、当該コンピュータシステム４００の構成要素である。
【００４７】
ネットワーク化の展開において、コンピュータシステム４００は、サーバーの許容量において、又は、クライアント‐サーバー・ユーザーネットワーク環境におけるクライアント・ユーザー・コンピュータとして、又はＰ２Ｐ（又は配信された）ネット‐ワーク環境におけるピア・コンピュータとして作動する。コンピュータシステム４００はまた、パソコン（ＰＣ）、タブレットパソコン、セットトップボックス（ＳＴＢ）、携帯情報端末（ＰＤＡ）、モバイル装置、パームトップ・コンピュータ、ラップトップ・コンピュータ、デスクトップ・コンピュータ、コミュニケーション装置、無線電話、固定電話、コントロールシステム、カメラ、スキャナー、ファックス、プリンター、ポケットベル、パーソナル・トラスト装置、ウェッブ装置、ネットワーク・ルーター、スイッチ又はブリッジ又は当該機械がとる行為を特定する一組の命令４１２（順次のものその他）を行うことのできるその他の装置等、多様な装置として実行され、または多様な装置に組み込むことができる。特定の実施形態では、コンピュータシステム４００は、声、ビデオ又はデータ・コミュニケーションを提供する電子装置を用いて実行することができる。更に、単一のコンピュータシステム４００が示されているが、「システム」という用語はまた、１つ以上の計算機能を実行するために、個別又は連結して１組又は複数組の命令を遂行するシステム又はサブシステムの集合体を含むようにも取られる。
【００４８】
図４に示しているように、コンピュータシステム４００は、例えば、中央演算処理装置（ＣＰＵ）、グラフィックス・プロセッシング・ユニット（ＧＰＵ）又は双方といったプロセッサ４０２を含む。プロセッサ４０２は、多様なシステムにおける構成要素である。例えば、プロセッサ４０２は、標準のパソコン又はワークステーションの一部である。プロセッサ４０２は、１つ以上の一般的なプロセッサ、デジタル信号プロセッサ、特定用途向け集積回路、フィールド・プログラマブル・ゲート・アレイ、サーバー、ネットワーク、デジタル回路、アナログ回路、それらの組み合わせ、又はその他のデータの分析・加工のための現在公知又は後に開発される装置である。プロセッサ４０２は、手作業により生成された（すなわち、プログラムされた）コード等のソフトウェアプログラムを実行することができる。
【００４９】
コンピュータシステム４００は、バス４０８経由で伝達できるメモリーを含む。メモリー４０４は、メインメモリー、スタティック・メモリー又はダイナミックメモリーである。メモリー４０４は、多様な種類の揮発性及び不揮発性記憶媒体等のコンピュータ可読性記憶媒体を含むがそれに限定されず、また、ＲＡＭ、ＲＯＭ、プログラム可能なＲＯＭ、電子的にプログラム可能なＲＯＭ、電子的に消去できるＲＯＭ、フラッシュメモリー、磁気テープ又はディスク、光媒体等を含むが、それらに限定されない。ある実施形態では、メモリー４０４は、プロセッサ４０２のためのキャッシュメモリー又はＲＡＭを含む。別の実施形態では、メモリー４０４は、プロセッサのキャッシュメモリー等のプロセッサ４０２、システムメモリーその他のメモリーとは別になっている。メモリー４０４は、外部保存装置又はデータ保存用のデータベースであってもよい。具体的には、ハードドライブ、コンパクトディスク（ＣＤ）、デジタルビデオディスク（ＤＶＤ）、メモリーカード、メモリースティック、フロッピー（登録商標）ディスク、ユニバーサル・シリアル・バス（ＵＳＢ）メモリー装置、その他データを保存するために作動する装置を含む。メモリー４０４は、プロセッサ４０２により実行可能な命令４１２を保存するように操作可能である。図に示され又は本明細書で記載されている機能、動作又はタスクは、メモリー４０４に保存される命令を遂行するプログラム化されたプロセッサ４０２によって実行される。当該機能、動作又はタスクは、特定の種類の命令の組、保存媒体、プロセッサ又は情報処理戦略とは独立しており、ソフトウェア、ハードウェア、集積回路、ファームウェア、マイクロコード等によって実行され、単独又は組み合わせて作動する。同様に、情報処理戦略には、多重処理、多重タスク処理、並行処理等を含む。
【００５０】
示されているように、コンピュータシステム４００は更に、液晶ディスプレイ（ＬＣＤ）、有機発光ダイオード（ＯＬＥＤ）、フラットパネル・ディスプレイ、ソリッドステートディスプレイ、ブラウン管（ＣＲＴ）、プロジェクター、プリンターその他決定された情報をアウトプットするための公知又は後に開発された装置等の表示ユニット４１４を含む。ディスプレイ４１４は、ユーザーがプロセッサ４０２の機能を見るためのインターフェースとして、又は特に、メモリー４０４に保存されるソフトウェアとのインターフェースとして作用する。
【００５１】
更に、コンピュータシステム４００は、ユーザーがシステム４００の如何なる構成要素とも対話ができるように構成されている入力装置４１６を含む。入力装置４１６は、テンキー、キーボード若しくはマウス又はジョイスティック、タッチパネル、リモコンその他システム４００と対話するように作動する装置等のカーソル・コントロール装置である。
【００５２】
ある特定の実施形態では、図４で示されているように、コンピュータシステム４００はまた、ディスク又は光学式ドライブユニット４２５を含む。ディスクドライブユニット４２５は、例えば、ソフトウェア等の一組以上の命令４１２が組み込まれることが可能なコンピュータ可読媒体４２２を含む。更に、命令４１２は、明細書に記載されているような、１つ以上の方法又は論理を具体化する。ある特定の実施形態では、命令４１２は、コンピュータシステム４００による実行の間は、メモリー４０４及び／又はプロセッサ４０２の中に、完全に又は少なくとも一部は、存在している。メモリー４０４とプロセッサ４０２はまた、上記のようなコンピュータ可読性媒体を含む。
【００５３】
本開示は、命令４１２を含み、又は、伝播された信号に応える命令を受け取り又は実行する、コンピュータ可読性媒体４２２を考慮に入れており、通信インターフェース４１８によるネットワーク４２０に接続される装置は、声、ビデオ、オーディオ、画像その他ネットワーク４２０上のデータを伝達することができる。更に、命令は、通信インターフェース４１８経由でネットワーク上を送信され又は受領される。通信インターフェース４１８は、プロセッサ４０２の一部か又は、別の構成要素であってもよい。通信インターフェース４１８は、ソフトウェアにおいて作成されるか、又は、ハードウェアにおける物理的接続である。通信インターフェース４１８は、ネットワーク４２０、外部媒体、ディスプレイ４１４その他システム４００の構成要素又はそれらの組み合わせと接続するように構成される。ネットワーク４２０との接続は、有線のイーサーネット接続等の物理的接続であってもよく、又、以下に述べるように無線で設定されてもよい。同様に、システム４００の他の構成要素との付加的接続は、物理的接続であってもよく、又、無線で設定されてもよい。
【００５４】
ネットワーク４２０は、有線のネットワーク、無線のネットワーク又はそれらの組み合わせを含む。無線のネットワークは、携帯電話ネットワーク、８０２．１１、８０２．１６、８０２．２０又はＷｉＭａｘネットワークであってもよい。更に、ネットワーク４２０は、インターネット等の公共のネットワーク、イントラネット等の私的なネットワーク又はそれらの組み合わせであってもよく、ネットワーキング・プロトコルに基づくＴＣＰ／ＩＰを含む（それに限定されない）、現在入手可能又は後に開発される多様なネットワーキング・プロトコルを利用する。
【００５５】
主題の実施形態及び本明細書に記載される機能的作動は、本明細書で開示される構造体及びその構造上の均等物又はそれらの１つ以上のものを組み合わせたものを含む、デジタル電子回路又はコンピュータ・ソフトウェア、ファームウェア又はハードウェアにおいて、実行することができる。本明細書に記載されている主題の実施形態は、例えば、データ加工装置による実行又はその操作を抑制する為に、コンピュータ可読性媒体４２２上にコード化される１つ以上のコンピュータプログラム命令のモジュール４１２等の１つ以上のコンピュータプログラム製品として実装することができる。コンピュータ可読性媒体４２２は、単一の媒体であることが示されるが、「コンピュータ可読性媒体」という用語は、集中型又は分散型データベース又は１つ以上の組の命令を保存する関連するキャッシュ及びサーバー等の単一媒体又は多数媒体を含む。「コンピュータ可読性媒体」という用語はまた、プロセッサによって実行されるか、又は、コンピュータシステムに本明細書で開示する方法又は動作の１つ以上を実行させる一組の命令を保存し、コード化し又は運搬することができる媒体が含まれる。コンピュータ可読性媒体は、機械可読性保存装置、機械可読性保存基板、メモリー装置又はそれらの１つ以上の組み合わせであることができる。「データ処理装置」という用語は、具体例として、プログラム可能なプロセッサ、コンピュータ又は多重プロセッサ又はコンピュータを含むデータ処理のための全ての器具、装置又は機械を含む。当該装置は、ハードウェアに加えて、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム又はそれらの1つ以上の組み合わせを構成するコード等、問題となっているコンピュータプログラムの実行環境を作り出すコードを含む。
【００５６】
特定の実施形態では（それに制約されない）、コンピュータ可読性媒体は、メモリーカードその他の１つ以上の不揮発性ＲＯＭを収容するパッケージ等の固体メモリーを含むことが可能である。更に、コンピュータ可読性媒体４２２には、ＲＡＭその他揮発性の書き換え型メモリーであることも可能である。更に、コンピュータ可読性媒体４２２は、ディスク、テープその他伝送媒体上で伝達される信号などの搬送波信号を捕らえる保存装置等の光磁気又は光学媒体４２２が含まれる。Ｅメールその他の自己完結型情報アーカイブ又はアーカイブの組へのデジタル添付ファイルは、有形の保存媒体である配布媒体であると考えられる。従って、本開示は、１つ以上のコンピュータ可読性媒体４２２又は配布媒体その他データ又は命令が保存され得る均等物及び代わりの媒体を含むと考えられる。
【００５７】
別の実施形態では、特定用途向け集積回路、プログラム可能な論理アレイその他のハードウェア装置等の専用のハードウェア・インプリメンテーションは、本明細書に記載されている１つ以上の方法を実行するように構成されている。多様な実施形態の装置及びシステムを含むアプリケーションは、広範囲に、多様な電子及びコンピュータシステムを含むことができる。本明細書に記載される１つ以上の実施形態は、モジュール間及びそれを通じて伝達することができる関連するコントロールとデータ信号のついた２つ以上の特定の相互接続されたハードウェア・モジュールを用いて又は、特定用途向け集積回路の一部として、諸機能を実行する。従って、本システムは、ソフトウェア、ファームウェア及びハードウェア・インプリメンテーションを含む。
【００５８】
本開示の多様な実施形態に従い、本明細書に記載される方法は、コンピュータシステムによって実行可能なソフトウェアプログラムによって実行される。更に、ある実施例では（それに限定されない）、実行は、分散処理、構成要素／対象分散処理及び並行処理を含めることができる。又は、仮想上のコンピュータシステム処理は、本明細書に記載されているように１つ以上の方法又は機能性を実行するように構成され得る。
【００５９】
本明細書は、特定の基準及びプロトコルに関して特定の実施形態において実行される構成要素及び機能を記載しているが、本発明は、当該基準とプロトコルには限定されない。例えば、インターネット及びその他のパケット交換網伝送（例えば、ＴＣＰ／ＩＰ、ＵＤＰ／ＩＰ、ＨＴＭＬ、ＨＴＴＰ、ＨＴＴＰＳ）が最新技術の具体例を示している。当該基準は、定期的に、本質的に同じ機能を有するより速く、又はより有効な均等物に取って代わられる。従って、本明細書に記載されたものと同じか類似の機能を有する代用基準及びプロトコルは、それとの均等物と考えられる。
【００６０】
コンピュータプログラム（また、プログラム、ソフトウェア、ソフトウェア・アプリケーション、スクリプト又はコードとして知られている）は、コンパイラ型又はインタープリタ型言語等のプログラム言語の形態で書くことができ、独立型プログラム又は、モジュール、構成要素、サブルーチン又はその他のコンピュータ環境における使用に適しているユニットを含む、如何なる形態において展開され得る。コンピュータプログラムは、必ずしもファイルシステムにおけるファイルに対応するものではない。プログラムは、問題のプログラム専用の単一のファイル又は複数の調整されたファイル（例えば、１つ以上のモジュール、サブプログラム又はコードの部分を保存するファイル）における他のプログラム又はデータ（例えば、マークアップ言語文書に保存された１つ以上のスクリプト）を保有するファイルの一部に保存されることができる。コンピュータプログラムを展開して、１つのコンピュータ上、又は１つのサイトに配置され又は複数のサイトに渡って分散されコミュニケーションネットワークに接続されている複数のコンピュータ上で実行することができる。
【００６１】
本明細書に記載されているプロセス及び論理フローは、１つ以上のコンピュータプログラムを実行する１つ以上のプログラム可能なプロセッサによって実行されることが可能で、入力データ上を作動し、出力を生みだすことで諸機能を実行する。当該プロセスと論理フローはまた、例えば、ＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ）又はＡＳＩＣ（特定用途向け集積回路）等の特定用途向け論理回路によって実行され及び装置がそういうものとして実行されることも可能である。
【００６２】
コンピュータプログラムの実行にふさわしいプロセッサは、具体例として、一般用途向け及び特定用途向けマイクロプロセッサ、更には、如何なる種類のデジタル・コンピュータのプロセッサを含む。一般的に、プロセッサは、命令及びＲＯＭ又はＲＡＭ若しくはその双方から命令及びデータを受領する。コンピュータの本質的要素は、命令を実行するためのプロセッサ及び命令とデータを保存するための１つ以上のメモリー装置である。一般的に、コンピュータはまた、例えば、磁気、光磁気ディスク又は光ディスク等のデータを保存するための１つ以上の大量保存装置を含み、これらからデータを受領し又はこれらへデータを転送するか又はその双方のために、操作可能に接続されている。しかしながら、コンピュータはそのような装置は必要としていない。更に、コンピュータは、例えば、ほんのわずかを挙げることになるが、携帯電話、携帯情報端末（ＰＤＡ）、携帯音響プレーヤー、グローバル・ポジショニング・システム（ＧＰＳ）レシーバー等の別の装置に組み込まれることができる。コンピュータプログラム命令とデータを保存する為にふさわしいコンピュータ可読性媒体は、全ての形態の不揮発性メモリー、媒体及びメモリー装置を含み、具体例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ及びフラッシュメモリー装置等の半導体メモリー、内蔵型ハードディスク又は取り外し可能ディスク等の磁気ディスク、光磁気ディスク及びＣＤ  ＲＯＭ及びＤＶＤ−ＲＯＭディスクを含む。プロセッサ及びメモリーは、特定用途向け論理回路によって補完され、又はこれらに組み込まれることが可能である。
【００６３】
ユーザーとの対話を提供するために、本明細書に記載される主題の実施形態は、ユーザーに情報を表示するために、例えば、ＣＲＴ（ブラウン管）又はＬＣＤ（液晶表示装置）モニター等の表示及び、ユーザーがコンピュータに入力できるようにする、キーボード及び例えばマウス又はトラックボール等のポインティングデバイスを有する装置上で実行されることが可能である。他の種類の装置はまた、ユーザーとの対話を提供するために使用されることが可能である。例えば、ユーザーに提供されるフィードバックは、例えば、視覚フィードバック、聴覚フィードバック又は触覚フィードバック等の如何なる形態の感覚フィードバックであることが可能で、ユーザーからの入力は、音響、対話又は触覚の入力等の如何なる形態において受領されることが可能である。
【００６４】
本明細書に記載される主題の実施形態は、例えばデータサーバーとしてバックエンド要素を含むか、例えばアプリケーションサーバー等のミドルウェア要素を含むか、例えばグラフィック・ユーザー・インターフェース又はユーザーが本明細書に記載される主題のインプリメンテーションと対話できるウェッブ・ブラウザーを有するクライアント・コンピュータ等のフロントエンド構成要素又は１つ以上の当該バックエンド、ミドルウェア又はフロントエンド構成要素の組み合わせを含む。本システムの構成要素は、例えば、コミュニケーションネットワーク等のデジタル・データ・コミュニケーションの如何なる形態又は媒体によって接続されることが可能である。コミュニケーションネットワークの具体例には、ローカル・エリア・ネットワーク（ＬＡＮ）とインターネット等の広域ネットワーク（ＷＡＮ）が含まれる。
【００６５】
コンピュータシステムは、クライアントとサーバーを含む。一般的に、クライアントとサーバーは一般的に互いに離れており、一般的には、コミュニケーションネットワークを通じて相互作用する。クライアントとサーバーの関係は、それぞれのコンピュータ上を走行し、互いにクライアント・サーバーの関係のあるコンピュータプログラムによって生じる。
【００６６】
本明細書に記載される実施形態の例示は、多様な実施形態の構造の１つの一般的理解を提供することを意図されている。例示は、本明細書に記載される構造又は方法を利用する装置及びシステムの要素と特徴の全てを完全に記載するものとして努めることを意図されていない。他の多くの実施形態は、本開示の見直しの際には、当業者には明白である。他の実施形態は、本開示から利用され派生され、構造上及び論理上の代用及び変更は、本開示の範囲を逸脱することなくなされる。更に、実例は、単に再現描写であり、一定の縮尺で描かれているわけではない。実例の特定の部分は、誇張されており、他の部分は最少化されている。それ故、本開示と図面は、限定というよりはむしろ例示として見なされる。
【００６７】
本明細書は、多くの特徴を含んでおり、これらは、発明又は請求項の範囲で限定するものではなく、むしろ発明の特定の実施形態に特有の特徴の記載として解釈されるべきである。個別の実施形態の文脈で本明細書に記載される特徴はまた、単一の実施形態における組み合わせで実施されることが可能である。反対に、単一の実施形態の文脈で記載される多様な特徴は、別々に多くの実施形態で、又は、適切な下位の組み合わせで実施される。更に、特徴が、特定の組み合わせにおいて作用するものとして、また、そのように当初主張されるように上記に記載されているが、主張される組み合わせからの１つ以上の特徴は、場合によっては、当該組み合わせから削除され、１つの下位の組み合わせ又は下位の組み合わせの変形に向けられている。
【００６８】
同様に、操作が図面において描かれ、特定の順序で本明細書に記載されており、これは、当該作用が示された特定の順序で、又は、順次行われること又は、望ましい結果を達成する為、全ての例示の作動が実行されることを要求して理解してはならない。特定の状況では、多重タスク処理及び並行処理は長所である。更に、上記の実施形態において、多様なシステムの構成要素の分離は、すべての実施形態において当該分離を要求するものとして理解すべきではなく、記載されたプログラム構成要素とシステムは、一般的に、単一のソフトウェア製品に統合され、複数のソフトウェア製品にまとめることができる。
【００６９】
本開示の１つ以上の実施形態は、個別に及び／又はまとめて、単に便宜上「発明」という用語で、又、本出願の範囲を特定の発明又は発明概念に自発的に制限する意図はなく、本明細書で示されている。更に、特定の実施形態が例示され本明細書に記載されているが、同じ又は類似の目的を達成するために企図されたいかなる後続のものも示されている特定の実施形態の代用であることを理解すべきである。本開示は、すべて後続の適用又は多様な実施形態の変形に及ぶことを意図されている。上記の実施形態の組み合わせ及び本明細書には特に記載されていない他の実施形態は、本記載の見直しの際に当業者には明瞭である。
【００７０】
本開示の要約書は、米国特許法１．７２（ｂ）条（３７  Ｃ．Ｆ．Ｒ．１．７２（ｂ））に従って提供されており、請求項の範囲と意味を制限的に解釈するために利用されないことを理解して提出されている。更に、上記の詳細な説明では、多様な特徴が、本開示をストリーミングするために、グループにまとめ、単一の実施形態で記載されている。本開示は、請求項で主張された実施形態が各請求項で明示的に列挙された以上の特徴を要求する意図を反映するものとして解釈されることを予定していない。むしろ、以下の請求項が表すように、発明の主題は、開示された実施形態の如何なるものの全ての特徴には満たないものに向けられている。そこで、以下の請求項は、別々に主張された主題を定義するものとして各請求項が独立して、詳細な説明に組み込まれている。
【００７１】
それ故、上記の主催な説明は、制限というよりはむしろ例示と見なされ、全ての均等物も含めて、以下の請求項は、本発明の精神と範囲を定義するものとして理解されることが意図されている。
【図１】
2020017296.tif 000003
【図２】
2020017296.tif 000004
【図３】
2020017296.tif 000005
【図４】
2020017296.tif 000006