(57)【特許請求の範囲】
【請求項１】
指定された数量の結果についてメモリ内の複数のストレージ領域をスキャンするためのコンピュータ実装の方法であって、各ストレージ領域は、そのストレージ領域内の値についての値範囲を示す第１及び第２の区間値を含む区間に関連付けられており、前記コンピュータ実装の方法は、
第１の区間値を順序に従ってソートし、ここで前記第１の区間値の前記順序は、前記複数のストレージ領域のスキャン順序を決定するものである、ソートすることと、
指定された数量の結果の上限、下限、又は外部にある、結果値を決定することと、
ソートされた第１の区間値を検査し、前記決定された結果値とそのストレージ領域の第１の区間値との比較に応答して、必要に応じて、対応する個々のストレージ領域をスキャンすることと、
を含む、方法。
【請求項２】
前記対応する個々のストレージ領域をスキャンすることが、
前記比較を満たさない最初の第１の区間値を決定し、前記ソートされた第１の区間値内の前記最初の第１の区間値及び後続の第１の区間値に対応する、前記対応する個々のストレージ領域を、前記スキャンから除外すること、
を含む、請求項１に記載のコンピュータ実装の方法。
【請求項３】
前記指定された数量の結果が、昇順ソートに関連付けられ、各ストレージ領域についての前記第１の区間値が、そのストレージ領域にとっての最小値を含み、前記対応する個々のストレージ領域をスキャンすることが、
前記決定された結果値がそのストレージ領域の前記第１の区間値よりも大きいことに応答して、個々のストレージ領域をスキャンすること、
を含む、請求項１に記載のコンピュータ実装の方法。
【請求項４】
前記数量の結果が、降順ソートに関連付けられ、各ストレージ領域についての前記第２の区間値が、そのストレージ領域にとっての最大値を含み、前記対応する個々のストレージ領域をスキャンすることが、
前記決定された結果値がそのストレージ領域の前記第２の区間値よりも小さいことに応答して、個々のストレージ領域をスキャンすること、
を含む、請求項１に記載のコンピュータ実装の方法。
【請求項５】
昇順ソートにおけるソートされた第１の区間値のリスト内のストレージ領域の前記第１の区間値が前記決定された値よりも大きいことが確立されると、スキャンを終了することをさらに含む、請求項１に記載のコンピュータ実装の方法。
【請求項６】
ストレージ領域にレコードを追加すること又はストレージ領域からレコードを削除することと、
追加又は削除されたレコードが、前記ストレージ領域にとっての最小値である第１の区間値又は最大値である第２の区間値を含むか否かを判定することと、
新たな最小値又は新たな最大値を反映させて前記第１の区間値又は前記第２の区間値を更新することと、
をさらに含む、請求項１に記載のコンピュータ実装の方法。
【請求項７】
１つ又は複数のソートキーに基づいて識別されるグループによるグループ分け動作を行うことをさらに含み、前記指定された数量の結果が、指定された数量の相異なるグループである、請求項１に記載のコンピュータ実装の方法。
【請求項８】
複数のコンピュータにより決定された複数の結果値の最小値を表す、大域結果値を決定することと、
昇順ソートにおけるソートされた第１の区間値のリスト内のストレージ領域の前記第１の区間値が前記決定された大域結果値よりも大きいことが確立されると、スキャンを終了することと、
をさらに含む、請求項１に記載のコンピュータ実装の方法。
【請求項９】
各ストレージ領域がそのストレージ領域内の値についての値範囲を示す第１及び第２の区間値を含む区間に関連付けられている、複数のストレージ領域を含むメモリと、
ネットワークインタフェースと、
プロセッサと、
を含むシステムであって、前記プロセッサが、
第１の区間値を順序に従ってソートし、ここで前記第１の区間値の前記順序は、前記複数のストレージ領域のスキャン順序を決定するものであり、
指定された数量の結果の上限、下限、又は外部にある、結果値を決定し、
ソートされた第１の区間値を検査し、前記決定された結果値とそのストレージ領域の第１の区間値との比較に応答して、必要に応じて、メモリ内の対応する個々のストレージ領域を前記指定された数量の結果についてスキャンする
ように構成された、システム。
【請求項１０】
前記プロセッサが、前記比較を満たさない最初の第１の区間値を決定し、前記ソートされた第１の区間値内の前記最初の第１の区間値及び後続の第１の区間値に対応する、前記対応する個々のストレージ領域を、前記スキャンから除外するように構成された、請求項９に記載のシステム。
【請求項１１】
前記指定された数量の結果が、昇順ソートに関連付けられ、各ストレージ領域についての前記第１の区間値が、そのストレージ領域にとっての最小値を含み、前記プロセッサが、前記決定された結果値がそのストレージ領域の前記第１の区間値よりも大きいことに応答して、個々のストレージ領域をスキャンするように構成された、請求項９に記載のシステム。
【請求項１２】
前記数量の結果が、降順ソートに関連付けられ、各ストレージ領域についての前記第２の区間値が、そのストレージ領域にとっての最大値を含み、前記プロセッサが、前記決定された結果値がそのストレージ領域の前記第２の区間値よりも小さいことに応答して、個々のストレージ領域をスキャンするように構成された、請求項９に記載のシステム。
【請求項１３】
前記プロセッサが、昇順ソートにおけるソートされた第１の区間値のリスト内のストレージ領域の前記第１の区間値が前記決定された値よりも大きいことが確立されると、スキャンを終了するように構成された、請求項９に記載のシステム。
【請求項１４】
前記プロセッサが、
ストレージ領域にレコードを追加し又はストレージ領域からレコードを削除し、
追加又は削除されたレコードが、前記ストレージ領域にとっての最小値である第１の区間値又は最大値である第２の区間値を含むか否かを判定し、
新たな最小値又は新たな最大値を反映させて前記第１の区間値又は前記第２の区間値を更新する
ように構成された、請求項９に記載のシステム。
【請求項１５】
前記プロセッサが、１つ又は複数のソートキーに基づいて識別されるグループによるグループ分け動作を行うように構成され、前記指定された数量の結果が、指定された数量の相異なるグループである、請求項９に記載のシステム。
【請求項１６】
前記プロセッサが、
複数のコンピュータにより決定された複数の結果値の最小値を表す、大域結果値を決定し、
昇順ソートにおけるソートされた第１の区間値のリスト内のストレージ領域の前記第１の区間値が前記決定された大域結果値よりも大きいことが確立されると、スキャンを終了する
ように構成された、請求項９に記載のシステム。
【請求項１７】
請求項１〜８の何れか１項に記載の方法を、コンピュータに実行させる、コンピュータ・プログラム。
【請求項１８】
請求項１７記載の前記コンピュータ・プログラムをコンピュータ可読ストレージ媒体に記録した、コンピュータ可読ストレージ媒体。  
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、クエリ評価のための計算作業負荷を低減することに関し、より詳細には、表スキャンの条件付き終了を管理するためにゾーンマップ内の情報を利用することにより計算作業負荷を低減することに関する。
【背景技術】
【０００２】
クエリを用いて情報を検索することは、結果的に大きいデータベース表を検索することになる場合がある。大きいデータベース表内に格納された情報は、ソート及び再編成に関連した計算コストが高いので、ソートされた形では維持されていないのが普通である。索引付けは、データ値の集合をこれらのデータ値に関連したレコードの集合にマッピングするものであり、これを用いて、データをソート順に格納する効果を与えることができる。しかしながら、大きいデータベース表を格納する分散型データウェアハウスは、レコードの集合を複数のストレージディスクにわたって分割する場合があり、所与のデータ値をそのデータ値に関連するレコードにマッピングする索引の部分を同じ場所に配置することは、付加的なネットワーク・オーバヘッドを必要とする場合があるので、待ち時間の悪化及び計算作業負荷の増大をもたらすことになる。
【０００３】
クエリ評価が、大きい表のスキャンを必要とする場合、データウェアハウス管理システムによっては、表ストレージの各領域に関するメタデータを維持するものもある。
【０００４】
特許文献１は、スケーラブルなデータストレージサービスを実装するシステムが、サービスクライアントの代わりに、非関係型データストア内で表を維持することができることを開示する。要約、図１〜図２５、第１欄、第５〜２６行、第４５欄、第１〜６７行及び請求項１〜３５を参照されたい。
【０００５】
特許文献２は、データセットから、該データセットのサイズに線形比例する時間で、最大（又は最小）キー値を有するｋ個のデータ要素のみ（すなわち上位ｋ結果）を取り出すアルゴリズムに関する。要約、図１〜図２、第２欄、第５〜６７行、第３欄、第１〜６７行及び請求項１〜１４を参照されたい。
【０００６】
特許文献３は、強く接続された構成要素を、同時に入口、出口、及び対応するエッジと共に効率的に識別するグラフ横断（graph transversal）を記載する。入口及び出口ノードは、強く接続された構成要素を識別した後ですべてのノードをスキャンすることにより認識することができるが、これらのノードの再訪は、望ましくないオーバヘッドを生じさせることになる。要約、図１〜図４、第１欄、第５〜６７行、第２欄、第１〜５行、及び請求項１１を参照されたい。
【０００７】
特許文献４は、データベース・サーバのデータベース・エンジン上のクエリ表現を最適化する方法を開示する。要約書、図１〜図２０、第１欄、第５〜４３行、第１２欄、第１〜６７行及び請求項１〜１５を参照されたい。
【０００８】
特許文献５は、表スキャンプロセスを管理するための方法、情報処理システム、及びコンピュータ可読媒体を開示する。要約、図１〜図１０、第２欄、第６５〜６７行、第８欄、第１〜６７行及び請求項１〜２０を参照されたい。
【０００９】
特許文献６は、ソートされたリストをディスプレイ装置上に表示するためのシステム、及び方法、並びに該システム又は方法を組み入れたコンピュータを開示する。要約、図１〜図３、第１欄、第５〜６７行、第２欄、第１〜４７行及び請求項１〜２０を参照されたい。
【００１０】
特許文献７は、大きい情報空間を多数の小さい情報エクステントに分割することを開示する。これらのエクステントは、それらが収容する情報に関する統計量で注釈付けされる。ある情報を求める検索が、値に基づく制限を含む場合、所望の値範囲を各エクステントの値範囲と比較することができる。所望の値範囲がエクステントの範囲外にある場合、そのエクステントは所望の値を保持している可能性はないので、検索に含める必要はない。
【００１１】
特許文献８は、ゲームに関する文書を自動的に処理及びソートするためのシステムを開示する。要約、図１〜図５、第［００１８］〜［００５２］行、第［００５５］〜［００６２］行及び請求項１〜３８を参照されたい。
【００１２】
特許文献９は、シンボルの文字列を規則セットにマッチングする方法及びシステムを開示する。要約、図１〜図４、第［０００５］〜［０００７］行、第［００４４］〜［００５０］行及び請求項１〜１０を参照されたい。
【００１３】
特許文献１０において、スケーラブルなデータストレージサービスを実装するシステムは、クライアントの代わりに、非関係型データストア内で表を維持することができる。要約、図１〜図２５、第［０００１］〜［０００３］行、第［０１７０］〜［０１７８］行及び請求項１〜３５を参照されたい。
【００１４】
特許文献１１は、多重範囲スキャンにおいてＮソートクエリを最適に処理するための方法及び装置を開示し、これは、クエリに含まれる第１の数の抽出レコードに基づいてバッファを割り当てることと、クエリ内に含まれる第１のリスト内に第１の属性に関連する第１のデータを抽出し、抽出された第１のデータをバッファ内でソートすることと、クエリ内に含まれる第１のリスト内に抽出されていない第１の属性に関連する第２のデータを抽出することと、バッファ内に格納されたデータと第２のデータとを比較することにより、クエリを満足するようにバッファを更新することと、を含み、ここでクエリは、第１の属性及び第２の属性に基づいてソートされる少なくとも１つのレコードに対する多重範囲スキャンにおけるＮソートクエリである。要約、図１〜図７、第［０００３］〜［００１８］行、第［００２９］〜［００９２］行及び請求項１〜２０を参照されたい。
【００１５】
特許文献１２は、マルチテナント・データベースシステムのためのクエリ最適化のための方法及びシステムを開示する。要約、図１〜図９、第［０００２］〜［００１０］行、第［０１０６］〜［０１２５］行及び請求項１〜４５を参照されたい。
【００１６】
その他の注目文献を以下に列挙する。
非特許文献１。
非特許文献２。
非特許文献３。
非特許文献４。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】米国特許第８５７２０９１号明細書
【特許文献２】米国特許第８２９６３０６号明細書
【特許文献３】米国特許第８２３９４０４号明細書
【特許文献４】米国特許第８２０４８７３号明細書
【特許文献５】米国特許第８０１０７６６号明細書
【特許文献６】米国特許第６１５４７４０号明細書
【特許文献７】米国特許第６９７３４５２号明細書
【特許文献８】米国特許出願公開第２０１３０２５１２３５号明細書
【特許文献９】米国特許出願公開第２０１３００４６７８４号明細書
【特許文献１０】米国特許出願公開第２０１２０３３０９５４号明細書
【特許文献１１】米国特許出願公開第２０１２０３１７１２８号明細書
【特許文献１２】米国特許出願公開第２０１１００８２８５４号明細書
【非特許文献】
【００１８】
【非特許文献１】ＨＥＲＯＤＯＴＯＵ他、「Ａ  ＳＱＬ−Ｔｕｎｉｎｇ−Ａｗａｒｅ  Ｑｕｅｒｙ  Ｏｐｔｉｍｉｚｅｒ」、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＶＬＤＢ  Ｅｎｄｏｗｍｅｎｔ、第３巻、第１号、２０１０年９月１３−１７日、ｐ．１−１２
【非特許文献２】ＩＰ．ＣＯＭ他、「Ｍｅｔｈｏｄ  Ａｎｄ  Ｓｙｓｔｅｍ  ｏｆ  Ｒｅｓｔｒｕｃｔｕｒｉｎｇ  Ｉｍｐｅｒｆｅｃｔ  Ｌｏｏｐ  Ｎｅｓｔ  Ｗｉｔｈ  Ｅａｒｌｙ  Ｅｘｉｔｓ  ｔｏ  Ｆａｃｉｌｉｔａｔｅ  Ｌｏｃａｌｉｔｙ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ」、ＩＰＣＯＭ０００２３２３０９Ｄ、２０１３年１０月、ｐ．１−７
【非特許文献３】ＩＰ．ＣＯＭ  他、「Ｓｙｓｔｅｍ  Ａｎｄ  Ｍｅｔｈｏｄ  Ｆｏｒ  ＧＲＯＵＰ  ＢＹ  Ｗｉｔｈ  ＩＮ−ＬＩＳＴ  Ｓｕｂｑｕｅｒｙ  Ｏｐｔｉｍｉｚａｔｉｏｎ」、ＩＰＣＯＭ０００２２９５７３Ｄ、２０１３年８月６日、ｐ．１−６
【非特許文献４】ＧＲＡＥＦＥ、「Ｆａｓｔ  Ｌｏａｄｓ  ａｎｄ  Ｆａｓｔ  Ｑｕｅｒｉｅｓ」、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、Ｂｅｒｌｉｎ、Ｈｅｉｄｅｌｂｅｒｇ、ＤａＷａＫ２００９、ＬＮＣＳ５６９１、ｐｐ．１１１−１２４．
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の目的は、クエリ評価のための計算作業負荷を低減するために、指定された数量の結果についてメモリ内の複数のストレージ領域をスキャンするための方法、システム及びコンピュータ可読媒体を提供することである。
【課題を解決するための手段】
【００２０】
第１の態様によれば、指定された数量の結果（specified quantityof results）についてメモリ内の複数のストレージ領域をスキャンするためのコンピュータ実装の方法が提供され、各ストレージ領域は、そのストレージ領域内の値についての値範囲を示す第１及び第２の区間値を含む区間に関連付けられており、上記コンピュータ実装の方法は、第１の区間値を順序に従ってソートし、第１の区間値の該順序は、複数のストレージ領域のスキャン順序を決定するものである、ソートすることと、指定された数量の結果の上限境界（upper bound: 以下、上限と記載）、下限境界(lower bound: 以下、下限と記載)、又は外部にある、結果値を決定することと、ソートされた第１の区間値を検査し、決定された結果値とそのストレージ領域の第１の区間値との比較に応答して、必要に応じて、対応する個々のストレージ領域をスキャンすることと、を含む。
【００２１】
第２の態様によれば、各ストレージ領域がそのストレージ領域内の値についての値範囲を示す第１及び第２の区間値を含む区間に関連付けられている、複数のストレージ領域を含むメモリと、ネットワークインタフェースと、プロセッサと、を含むシステムが提供され、該プロセッサは、第１の区間値を順序に従ってソートし、第１の区間値の順序は、複数のストレージ領域のスキャン順序を決定するものであり、指定された数量の結果の上限、下限、又は外部にある、結果値を決定し、ソートされた第１の区間値を検査し、決定された結果値とそのストレージ領域の第１の区間値との比較に応答して、必要に応じて、メモリ内の対応する個々のストレージ領域を指定された数量の結果についてスキャンするように構成される。
【００２２】
第３の態様によれば、具体化されたコンピュータ可読プログラムコードを有するコンピュータ可読ストレージ媒体を含む、ユーザに情報を提供するためのコンピュータ・プログラム製品が提供され、該コンピュータ可読プログラムコードは、プロセッサによって実行されると、該プロセッサに、各ストレージ領域がそのストレージ領域内の値についての値範囲を示す第１及び第２の区間値を含む区間に関連付けられている、メモリ内の複数のストレージ領域に対して、第１の区間値を順序に従ってソートさせ、ここで第１の区間値の順序は、ストレージ領域のスキャン順序を決定するものであり、指定された数量の結果の上限、下限、又は外部にある、結果値を決定させ、ソートされた第１の区間値を検査させ、決定された結果値とそのストレージ領域の第１の区間値との比較に応答して、必要に応じて、メモリ内の対応する個々のストレージ領域を指定された数量の結果についてスキャンさせる。
【００２３】
他の実施形態において、本明細書に開示された技術は、第２の区間値をソートすることを含むことができる。
【００２４】
実施形態によれば、近似的に順序付けされた（nearly ordered）マップを用いて、大まかに順序付けされた（looselyordered）及び／又はグループ分けされた関係の表スキャンを早期に終了するためのソリューションが提供される。
【００２５】
一般に、種々の図面内の類似の符号は、類似の構成要素を示すために使用される。
【００２６】
本発明の実施形態を、以下、例示のみを目的として、以下の図面を参照して説明する。
【図面の簡単な説明】
【００２７】
【図１】本発明の実施形態と共に使用するための例示的なコンピューティング環境を示す。
【図２】本発明の実施形態による表ストレージの領域（エクステント）の例を示す。
【図３】本発明の実施形態による表ストレージの領域に対応するメタデータの例を示す。
【図４】本発明の実施形態による、あるストレージ領域をスキャンするか否かを決定するための、該ストレージ領域に関連づけられたメタデータの使用を一般的に説明する手順のフローチャートである。
【図５】本発明による、図４のフローチャートに基づくより具体的な手順のフローチャートであり、メタデータを用いて表スキャンの条件付き終了を管理する方法を示す。
【図６】本発明による、図４のフローチャートに基づくより具体的な手順のフローチャートであり、メタデータを用いて表スキャンの条件付き終了を管理する方法を示す。
【図７】本発明による、ストレージ領域内のレコードが追加又は削除されたときにストレージ領域に関連付けられたメタデータを更新することができる方法を示す、別の手順フローチャートである。
【図８】本発明の実施形態によるシステム／装置の例である。
【発明を実施するための形態】
【００２８】
データウェアハウスのクエリは、結果値の集合をソートし及び限定して結果値の部分集合にする場合が多い。典型的な方法は、クエリに応答して大きいデータ表をスキャンして結果を見いだすことと、結果をソートする及び／又は集約することと、例えば上位Ｎ個の結果（ここでＮは任意の整数、例えば５０である）以外を棄却することと、を含む。
【００２９】
大きい表をディスク上に格納する場合、表がかなり大きいか又は断片化されていて、大きい表を検索するために多くの異なるディスク領域にディスクヘッドを移動させるのに時間がかかる場合がある。ストレージ領域に対応するメタデータを用いて、該ストレージ領域内に含まれる表データを特徴付けることができる。例えば、第１の区間値は、行の各範囲に対して、各列の最小データ値を表すものとすることができ、第２の区間値は、行の各範囲に対して、各列の最大データ値を表すものとすることができる。第１及び第２の区間値は両方とも、種々のストレージ領域に対して決定することができるメタデータ型式を表し、（付加的な情報型式との組合せで）「ゾーンマップ」とも呼ばれることがある。ストレージ領域内の特定のデータ範囲を識別するためにゾーンマップを使用することで、本発明の実施形態によれば、ディスクスキャン時間及び計算負荷が低減される。ゾーンマップの最小値及び最大値は、保存的とすることができることに留意されたい。換言すれば、ゾーンマップエントリの最小値は、対応するデータのストレージ領域についての実際の最小よりも小さい場合があり（例えばレコード削除等により）、同様に、ゾーンマップエントリの最大値は、対応するデータのストレージ領域についての実際の最大よりも大きい場合がある。
【００３０】
本発明の実施形態は、ゾーンマップを利用して、指定された条件を満たすとクエリ評価を早期に終了する技術を提供する。ゾーンマップの最小データ値（第１の区間値とも呼ばれる）のリスト、又は代替的に最大データ値（第２の区間値とも呼ばれる）のリストをソートすることにより、上位Ｎソートの一部になり得る可能性がある全ての結果が既に識別されたと判定した後、表スキャンを終了すること、例えば表の読出しを停止することができる。したがって、本明細書で開示される技術は、読出し／書込み動作などのＩ／Ｏ動作に起因する計算処理要求を減らすことができる。好ましい実施形態において、本明細書で提示される技術は、上位Ｎソート、すなわち「ＯＲＤＥＲ  ＢＹ」文節とそれに続く「ＬＩＭＩＴ」文節を含むクエリに適用される。
【００３１】
図１を参照すると、本発明の実施形態と共に使用するための例示的なコンピューティング環境が示されている。詳細には、この環境は、１つ又は複数のクライアント又はエンドユーザシステム１００と、１つ又は複数のサーバシステム１１０及び１２０とを含む。ホストサーバシステム１１０及び情報サーバ１２０は、互いに遠隔であってネットワーク１３０上で通信するものとすることができる。クライアントシステム１００から発信されたクエリ要求は、データベース・ストレージユニット１４０上に格納されたデータを検索するために情報サーバ１２０に転送されることができる。ネットワーク１３０は、任意の数の任意の適切な通信媒体（例えば、広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、インターネット、イントラネット、等）で実装することができる。あるいは、サーバシステム１１０及び１２０は、互いにローカルであっていずれかの適切なローカル通信媒体（例えば、ローカルエリアネットワーク（ＬＡＮ）、配線、無線リンク、イントラネット、等）を介して通信するものとすることができる。ネットワークインタフェースユニットは、１１２及び１２２で示されている。
【００３２】
クライアントシステム（１００）は、ユーザが、文書（例えば、文書収集のための文書、解析用文書、等）をデータベース・ストレージユニット内に保管するために情報サーバシステム１２０に提出することを可能にする。本明細書で論じるように、文書（又は他の情報）は、既存のデータベースストレージにストレージ領域（エクステントとも呼ばれる）として追加することができる。
【００３３】
データベース・ストレージユニット１４０は、解析（例えば、上位Ｎサーチ、等）のための情報を格納することができ、任意の従来型の又はその他のデータベース又はストレージユニットによって実装することができる。データベース・ストレージユニット１４０は、情報サーバ１２０に対してローカル又は遠隔とすることができ、任意の適切な通信媒体（例えば、ローカルエリアネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、インターネット、配線、無線リンク、イントラネット、等）を介して通信することができる。クライアントシステム１００は、所望の文書及び解析に関係するユーザからの情報を求めるために、グラフィカルユーザインタフェース（例えば、ＧＵＩ等）又はその他のインタフェース（例えば、コマンドラインプロンプト、メニュスクリーン、等）を提示することができ、かつ、結果の解析（例えば、テキスト解析、検索結果、プロファイルスコア、等）を含むレポートを提供することができる。
【００３４】
複数のデータベース・ストレージユニット１４０がデータウェアハウス内に存在する場合がある。情報サーバ１２０は、ホストサーバ１１０の方向で、データベース・ストレージユニット１４０からの情報を格納し及び取り出すことができる。ホストサーバ１１０は、クライアントシステム１００からの要求を受け、これに応答する。１つの実施形態において、データベース・ストレージユニット１４０内のメモリ空間は、ユーザ情報を格納するための一次パーティション、一次情報のバックアップコピーを格納するためのミラーパーティション、情報サーバ１２０の方向で中間結果を保持するための一時的パーティション、データベース・ストレージユニット１４０内の情報の物理的レイアウトに関する情報を保持するコアパーティションを含む、いくつかのパーティションに分割することができる。
【００３５】
図２を参照すると、本発明の実施形態は、大きい情報空間１６０を複数の小さい情報領域１７０及び１８０（「エクステント」又は「ストレージ領域」とも呼ばれる）に分割することにより動作する。各エクステントは、いくつかの連続する固定サイズ又は可変サイズのサブエクステント・ブロックにさらに分割することができる。固定サイズを用いることの利点は、特定の計算がより速くなり、かつより複雑でなくなることである。本発明の代替的な実施形態において、固定サイズは、データベース全体のサイズ又はその他の特徴に基づいて、動的に変更することができる。可変ブロックサイズは、例えば属性の型式に基づいて、動的に修正することができる。例えば、最小データ値（第１の区間値とも呼ばれる）及び最大データ値（第２の区間値とも呼ばれる）がタイムスタンプデータを参照する場合、エクステントのサイズは、特定の期間に対する全てのデータが１つのデータブロック内に格納されるように変更することができる。ブロックは、全情報空間を保持するデータベース・ストレージユニット１４０と情報を検査及び操作することができる情報サーバ１２０との間の転送の最小単位である。１つの実施形態において、ブロックは、１２８Ｋバイトとすることができるが、他のサイズも同様に機能することができる。
【００３６】
エクステント１７０、１８０は、ストレージ割当ての便利な単位であるので、情報空間が増大するとき、その増大は、エクステントの単位に量子化される。エクステント内のアドレス空間は連続的（すなわち、ホールは存在しない）であるが、情報空間１６０は、不連続のエクステントから構成される場合があり、なぜなら、後のエクステントの割当てが、以前のいずれかの割当てのアドレス範囲に対してなんらかの固定的な関係を持つアドレス範囲を生成しなければならないという要件はないからである。
【００３７】
図３を参照すると、本発明の実施形態は、エクステントに、該エクステントが含む情報に関する統計量（例えばメタデータ）で注釈を付け、この情報を近似的順序付け（nearly ordered）マップ表又はリスト２００内にエントリとして格納することができる。図３に示すように、近似的順序付けマップ表２００は、表識別子２１０、列索引２２０、最小データ値２３０、最大データ値２４０、及びエクステント識別子２５０を含む構造を示す。メタデータの多数のエントリが２６０（１）−２６０（Ｎ）として示されている。表識別子２１０は、例えば関係型データベース表に対応するものとすることができる情報空間を一意に指定する。１つの実施形態において、これは、関係型データベース表を一意に識別する４バイトの数値である。列索引２２０は、表識別子２１０により識別される情報空間内の特定のクラスの情報を一意に識別する。１つの実施形態において、列索引２２０は、表識別子２１０により識別される関係型表内の列を表す２バイトの数値である。別の実施形態において、列索引２２０は、列が関係型表内で定義される順序に対応するものとすることができる。
【００３８】
本発明の１つの実施形態において、最小データ値２３０及び最大データ値２４０は、日付、時間、データ−時間、整数値、等を含む、異なる型式のデータ値を保持することができる８バイトの数量とすることができる。最小データ値及び最大データ値により保持されるデータの実際の型式は、列索引２２０により表される列の定義内で指定される。１つの実施形態において、エクステント識別子２５０は、表識別子２１０により指定される情報空間内の特定のエクステントを指定する、２バイトの数値とすることができる。より大きいストレージパーティションは、４バイトのエクステント識別子又はより大きなエクステントのいずれかを使用することになるであろう。
【００３９】
最小データ値２３０及び最大データ値２４０は、あるエクステント内の特定の種類の情報についての最大データ値及び最小データ値に対応する。情報についてのクエリ評価が値に基づく限定を含む場合、その値を各エクステントに関連付けられたメタデータ、例えば各エクステントの最小データ値と比較して、そのエクステントを検索すべきかどうか決定することができる。これらの技術は、図４並びに図５及び図６に関連して後述する。
【００４０】
ゾーンマップは、典型的には、ディスク空間の利用量が少なく、それが記述する対応データと同じ場所に配置することができ、システムに導入する計算待ち時間は最小限の量であり、高度なデータベース管理経験がなくても維持することができる。ゾーンマップの概念は、図２及び図３に示すメタデータ情報の特定の型式に限定されないことに留意されたい。ストレージ領域（エクステント）を特徴付けるために用いられるメタデータ情報のさらなる型式は、本明細書で開示される実施形態の範囲内に入ることが理解される。
【００４１】
図４は、本発明の実施形態の一般的な概要を示す。動作３１０は、指定された数量の結果についてメモリ内の複数のストレージ領域をスキャンし、ここで各ストレージ領域は、そのストレージ領域内の値についての値範囲を示す第１及び第２の区間値を含む区間に関連付けられる。動作３２０において、第１の区間値は、順序に従ってソートされ、ここで第１の区間値の順序は、複数のストレージ領域のスキャン順序、例えば昇順又は降順を決定する。動作３３０において、結果値が決定され、ここで結果値は、指定された数量の結果の、上限、下限、又は外部にある。動作３４０において、ソートされた第１の区間値が検査され、決定された結果値とそのストレージ領域の第１の区間値との比較に応答して、対応する個々のストレージ領域がスキャンされる。
【００４２】
図５〜図６を参照すると、図４のフローチャートで提供される動作のより詳細な一連の動作のフローチャートの例が示される。本明細書で提供される技術は、図５〜図６に示す１つ又は複数の動作の代替の順序も包含し得ることを理解されたい。例えば、異なる順序で動作を行って同じ結果を達成することができ、これは本明細書に開示される技術に包含される。
【００４３】
本発明の実施形態は、上位Ｎソート（例えば、「ＯＲＤＥＲ  ＢＹ」と「ＬＩＭＩＴ  Ｎ」文節の組合せによる）を含むクエリに適用することができる。上位Ｎソートは一般に、部分ソートアルゴリズムを利用してｍ要素のアレイをソートし、上位Ｎ個の結果が、例えば昇順にソートされる場合は、要素ｍの最小値を含むようにする。一般に、上位Ｎソートは、要素数ｍが上位Ｎ要素の数よりも大きいという条件で、ｍ要素のアレイの要素の部分集合を含む。部分ソートアルゴリズムは、上位結果のみが欲しい場合にはソートに関連した作業をかなり節約するが、このようなアルゴリズムは、読出し／書込みなどのＩ／Ｏ動作に対する作業負荷は低減しない。
【００４４】
本発明の実施形態は、集約データ構造が上位Ｎソートの場合と同様に維持される場合には、グループ分け動作とそれに続く上位Ｎソートとを含むクエリ（例えば、「ＧＲＯＵＰ  ＢＹ」、「ＯＲＤＥＲ  ＢＹ」、及び／又は「ＬＩＭＩＴ  Ｎ」文節によるものであり、ここで順序は、グループ分けされた列のいずれかの部分集合により決定される）にも適用することができる。
【００４５】
本発明の実施形態は、最良Ｎグループが保持される、上位Ｎソートデータ構造を用いたグループ分けを行うこともまた包含することができる。例えば、クエリは、１つ又は複数の列に対してグループ分け動作、例えば「ＳＥＬＥＣＴ．．．ＧＲＯＵＰ  ＢＹ  Ａ，Ｂ」を行うことができる。グループ分け動作の結果は、ソートキーがグループ分けキーの部分集合（例えば「ＯＲＤＥＲ  ＢＹ  Ａ」、「ＯＲＤＥＲ  ＢＹ  Ｂ」、又は「ＯＲＤＥＲ  ＢＹ  Ａ，Ｂ」）になるようにソートすることができる。最後に、結果を「ＬＩＭＩＴ  １０」のように限定することができる。（新規レコードは、それが属する既存グループを見いだすことにより、又は新規グループを作成することにより、グループ分けすることができる）。グループは、１つ又は複数のソートキー（例えば、１つ又は複数のソートキーに対する相等性）に基づいて識別することができ、指定された数量の結果は、相異なるグループを含む（例えば、一般に、指定された数量の結果は、指定された数量の相異なるグループとなる）。「ＧＲＯＵＰ  ＢＹ」動作を伴わない上位Ｎソートと同様に、ストレージ領域をスキャンすることは、昇順ソートに関してはストレージ領域の最小値が上位Ｎデータ構造内の現在の最悪グループ分けキーを超える場合、又は降順ソートにおいてはストレージ領域の最大値が上位Ｎソートデータ構造の現在の最悪グループ分けキーを下回る場合に、回避することができる。
【００４６】
ゾーンマップは、単一の第１の区間値又は単一の第２の区間値に限定されることを意図したものではなく、各々が特定のデータ型式に対する最小値及び最大値に対応する複数の区間を含むことができることもまた理解される。
【００４７】
図５を再度参照すると、動作４１０において、クエリ要求を受け取る。動作４２０において、各ストレージ領域に対してメタデータ（例えばゾーンマップ）が既に作成されているか否か、及びそれを更新すべきか否かが決定される。動作４２５において、ゾーンマップは、既に存在していない場合、作成／更新される。動作４３０において、クエリに関連した（スキャンされる）ストレージ領域／エクステントが決定され、これらの関連ストレージ領域を特徴付けるメタデータを含むリストが構築／作成される。動作４４０において、この領域リストを、Ｉ／Ｏ動作を行う前に、上位Ｎソートの一次ソートキーである列を用いて、昇順又は降順にソートすることができる。処理されるストレージ領域のリストの作成の例として、あるストレージ領域が１００と２００との間の列値を有するレコードを含むものとして既知である（例えば、ゾーンマップメタデータにおいて示されている）場合、既知の範囲外の範囲値を伴うクエリ（例えば値５００を伴うクエリ）が評価されるとき、評価は該ストレージ領域全体をスキャンから除外することができる。本明細書で論じるように、ゾーンマップは、行の各範囲に対して、例えば、各列についての最小データ値及び最大データ値を格納する。したがって、表スキャンの順序を決定するのは、ソートされたリスト内のゾーンマップデータの順序である。情報空間内に含まれるデータを、順序付けることも、部分的に順序付けることも、又はソートされた列に対してバケットする（bucketed）ことも必要としない。
【００４８】
上位Ｎソートが小さい値を優先する場合（例えば昇順ソート）、ストレージ領域のリストは、最小データ値（すなわち第１の区間値）によりソートすることができ、最小値を有さない領域は、リストの最後に移動される。上位Ｎソートが大きい値を優先する場合（例えば降順ソート）、ストレージ領域のリストは、最大データ値（すなわち第２の区間値）によりソートすることができ、最大値を有さない領域は、リストの最後に移動される。
【００４９】
図６（図５の動作４４０からの続き）の動作４５０において、ソートされたリスト内の第１のエントリに対応するストレージ領域が選択される。動作４５５において、選択されたストレージ領域がクエリに基づいて処理される。動作４６０において、上位Ｎソートにおける値の結果値ｘすなわち最悪値ｘ（少なくともＮ個の結果が存在すると仮定する）が決定される。このステップにおいて、簡単にするために、単一のストレージ領域を処理することで上位Ｎ結果に少なくともＮ個の値がポピュレートされるものと仮定することに留意されたい。そうでない場合には、この条件が満たされるまでさらなるストレージ領域が処理されることになる。動作４６２において、ソートされたリストの第１のエントリの領域の最小データ値ｍｉｎ（Ｒ１）が決定される。動作４６２は、結果値ｘをストレージ領域の最小データ値と比較するための条件付き表現式を与える。上位Ｎソートを処理するとき、Ｎ番目の値がｘ（現在の「最悪」値）である場合、ｘより大きい最小データ値を含む領域は、スキャンされる必要はない（昇順ソートの場合）。この条件が満たされない場合、ソートされたリストの次のエントリが動作４７０において選択される。動作４７５において、ストレージ領域は、クエリに基づいて処理される。動作４８０において、最悪値ｘが更新される。この一連の動作を、指定された条件が満たされるまで繰り返す。ひとたびこの条件が満たされると、上位Ｎ値に重なるさらなる値は存在しない。上位ＮサーチのＮ番目の値がｘであり、かつ領域の最小データ値ｍｉｎ（Ｒ１）がｘの値より大きい場合、ストレージ領域全体が棄却される。
【００５０】
さらに、選択されたストレージ領域のリストを最小データ値によりソートすることにより、ひとたびストレージ領域Ｒ１の最小データ値が上位Ｎソートの最悪値ｘより大きいＲ１が見いだされると、全ての後続領域Ｒ２、Ｒ３、以下同様、もまた、ｘより大きい最小データ値を有することになる。結果として、以下の式１で示すように、動作４６５において、スキャンを早期に終了してデータの読出しを停止することができる。
ｍｉｎ（Ｒ１）＞ｘの場合、            （式１）
ｍｉｎ（Ｒ２）＞＝ｍｉｎ（Ｒ１）＞ｘ
【００５１】
最小データ値がｘを超えるストレージ領域は上位Ｎ結果に入る結果を有さないので、したがってストレージ領域全体を、検索に含める必要はないので棄却することができる。さらに、ひとたびリスト内のあるストレージ領域が棄却されると、リスト内の全ての後続ストレージ領域を棄却することができる（但し、ストレージ領域のリストはソートされているものとする）。多くの場合、これは、残りの領域が上位Ｎソートに存続することになる値を保持し得る可能性がない点に到達したときに、表スキャンの早期終了を可能にすることになる。小さいＮの場合、本明細書で提示する技術は、クエリに回答するのに必要なＩ／Ｏを最低限まで減らすのに有効であり、性能への著しい影響をもたらす。
【００５２】
複数のソートキーを有する場合、上記の比較（例えば式１）が適用されることに留意すべきである。すなわち、ｘに等しい値を有するゾーンマップエントリを自動的に棄却することはできず、それは、優先順位が低いソートキー（例えば第２のソートキー）が、そのエントリが含まれるべきであると決定する場合があるためである。しかしながら、単一のソートキーが用いられる場合、上記の比較は、式２に示すように改良することができる。
ｍｉｎ（Ｒ１）＞＝ｘの場合            （式２）
ｍｉｎ（Ｒ２）＞＝ｍｉｎ（Ｒ１）＞＝ｘ
【００５３】
現在の最悪結果は、「結果値」と呼ぶこともできる。図５及び図６は、結果値を上位Ｎソートの現在の最悪値、すなわち昇順ソートの場合の上限及び降順ソートの場合の下限として表しているが、本発明の実施形態は、指定された数量の結果の外部の値を含むこともできることに留意されたい。指定された数量の結果の外部の値は、実際の上限より大きい値並びに実際の下限より小さい値を含む。上限は、上位Ｎソートの値の最大値である。下限は、上位Ｎソートの値の最小値である。
【００５４】
スキャンが進行するにつれて、結果値は一般に時間と共に改善される（例えば、結果値が最小値である場合、結果値は、スキャンが進んで新たな最小値が識別されるにつれて、さらに小さくなり得る）こともまた留意されたい。改善された結果値は、スキャンが進むにつれてより多くのデータがスキップされることを可能にし、したがって、Ｉ／Ｏ動作に起因する計算作業負荷がさらに低減される。
【００５５】
本発明は、計算作業負荷を低減するために、上位ＮソートアルゴリズムからＩ／Ｏ層までフィードバックを提供する。早期終了を行う決定は、上述のように、関連付けられたＩ／Ｏ動作を停止することを可能にし、したがって、Ｉ／Ｏ層に対するフィードバックの形態を提供する。ゾーンマップエントリのリストをソートすることは、最適化をもたらす。すなわち、上位Ｎソートの早期終了の決定がなされるとすぐに、Ｉ／Ｏ動作に起因する関連付けられた計算作業負荷を回避することができる。
【００５６】
それゆえ、クエリが、指定された範囲内の値について大きい情報空間をスキャンする場合、本発明の実施形態によれば、各ストレージ領域に関連付けられたゾーンマップデータのリストを作成し、ソートし、検査して、そのストレージ領域が上位Ｎソートの指定された範囲内の値を含み得る可能性があるか否かが判定される。指定された範囲内の値を含む可能性がある領域のみがスキャンされ、その他の領域を考慮する必要はない。本明細書で説明する技術は、大きい情報空間をスキャンするために必要な時間量を実質的に削減することを可能にする。
【００５７】
本明細書で提示する技術はまた、上位Ｎソートの結果の可能な最良の早期推定の予測を可能にする。例えば、第１のストレージ領域が、１〜５の値の範囲を示す対応するゾーンマップエントリを有し、第２のストレージ領域が、３〜２０の値の範囲を示す対応するゾーンマップエントリを有する場合、妥当なデータは、第１の領域内にある可能性がより高く（昇順ソートが用いられていると仮定する）、この領域が最初に読み出されることになる。従って、ソートされたメタデータの利用は、妥当な結果が最適化された方式で識別されることを可能にする。
【００５８】
他の実施形態において、本明細書で提示する技術は、下流の動作が総計（grand aggregate）ｍｉｎ（列）又はｍａｘ（列）動作である場合、すなわち、制限が１であり、かつ選択された列がソートキーである、上位Ｎソートの縮重した事例である場合に、表スキャンの最適な早期終了を得るために用いることができる。
【００５９】
この場合、部分ソート動作は、１つのレコード、例えばソートキーの最小値を有するレコード又はソートキーの最大値を有するレコードのみを保持する動作に縮重する、又は該動作で置き換えることができる。ソートキーの最小値を有するレコードを保持する動作の場合、対応するゾーンマップエントリにより示されるその最小値がソートキーよりも高いストレージ領域はいずれも、スキップすることができる。（あるいは、ソートキーの最大値を有するレコードを保持する動作の場合、その最大値がソートキーよりも低いストレージ領域はいずれも、スキップすることができる）。この最適化は、データが部分的に又は完全に順序付けられておらず、ゾーンマップを評価する初期プロセスにおいて除外されるストレージ領域がごく少数である場合でさえも有効であり得る。単一のソートキーが存在する場合、動作は、あらゆる残りのゾーンマップエントリの最小値を下回るか又は最小値に等しい値が見いだされたらすぐに終了することができる。複数のソートキーが存在する場合、動作は、あらゆる残りのゾーンマップエントリの最小値を下回る値が見いだされたらすぐに終了することができる。
【００６０】
さらに他の実施形態において、あらゆる領域に対して、ｍｉｎ（領域）−ｍａｘ（領域）がほとんど列の全範囲である、あまり整理されていない列の場合でも、終点にはある程度の変動がある。それゆえ、最小の少数の値が、ごく少数のストレージ領域内に現れる可能性がある。これらのストレージ領域が最初にスキャンされることになり、残りのストレージ領域を除外することになる十分に小さい「結果値」が選択される。それゆえ、上位Ｎソートにおける十分に小さいＮに対して、本明細書で提供される技術は、一般に良好な結果をもたらす。
【００６１】
本発明の実施形態は、特定のタイプのコンピューティング環境に限定されない。例えば、本発明の実施形態は、各々が独立して上位Ｎソートを行って上位Ｎ結果のローカルなリストを生成するいくつかのコンピュータ又はプロセッサを含むシステムに適用することができる。独立したリストの各々をマージして、マージ後の上位Ｎ結果が保持されるようにすることができる。それゆえ、この文脈において、各コンピュータ又はプロセッサは、上位Ｎ結果のリストを独立に生成することができ、互いに独立に、上位Ｎソートを早期に終了することができる。
【００６２】
あるいは、本発明の実施形態はまた、複数のコンピュータが協働して大域結果値を維持することができるシステムに適用することもでき、ここで大域結果値は、複数のコンピュータによって行われる複数の上位Ｎソートの現在の大域的最悪結果値（例えば、大域的最小値又は大域的最大値）に対応する。従って、各コンピュータは、この大域的結果値に基づいて、その対応するスキャンリストを切り捨てる及び／又は上位Ｎソートの早期終了を決定することができる。少数の付加的なストレージ領域をスキャンすることに対する有意な性能ペナルティは存在しないことにもまた留意されたい。したがって、大域的結果値は、非同期的に計算することができ、又は頻繁に更新しなくてもよく、この最適化がシステム内に同期点を導入する又は必要とすることがないようになっている。
【００６３】
図７は、ストレージ領域内のレコードの追加又は削除による以前のゾーンマップエントリの更新のための手順の一般化されたフローチャートである。あるレコードが情報区間から削除されると、そのレコードがレコードのエクステント内の全ての列についての最小値であった列の値を有していた列を含んでいた場合、そのエクステント内のその列についての新たな最小値は、実際には、ゾーンマップエントリ内に記録された最小値よりも大きくなる場合がある。同様に、そのレコードがレコードのエクステント内の全ての列についての最大値であった列の値を含んでいた場合、そのエクステント内のその列についての新たな最大値は、実際には、ゾーンマップエントリ内に記録された最大値よりも小さくなる場合がある。換言すれば、レコードの削除は、エクステント内の列についての値の範囲を狭める効果を有する場合がある。同様に、レコードの作成は、エクステント内の列についての値の範囲の拡張の効果を有する場合がある。
【００６４】
図７の動作５１０において、レコードが追加又は削除される。動作５２０において、追加又は削除されたレコードがレコードのエクステント内の全ての列についての最小値である列値を含んでいるか否か、及び／又は追加又は削除されたレコードがレコードのエクステント内の全ての列についての最大値である列値を含んでいるか否かが判定される。動作５３０において、ゾーンマップは、新たな最小値を反映するように更新され（例えば、少なくとも追加されたレコード内で指定された値まで下げられる又はストレージ領域内の最小値を反映するように上げられる）、及び／又は新たな最大値を反映するように更新される（例えば、少なくとも追加されたレコード内で指定された値まで上げられる又はストレージ領域内の最高値を反映するように下げられる）。他の実施形態において、ゾーンマップが一般に保存的方式で用いられるとき、ゾーンマップを、レコードの削除を反映するように更新する必要がない場合がある。
【００６５】
図８を参照すると、情報サーバ１２０の例示的な実施形態は、ネットワークインタフェース１１２、プロセッサ６２０、及びメモリ６３０を含むことができる。ネットワークインタフェースユニット１１２は、ネットワーク１３０上でのネットワーク通信を可能にするように、例えば、図１に示すように、クライアントシステム１００からのクエリ要求に関して情報サーバ１２０とホストサーバ１１０との間の通信を促進するように構成される。
【００６６】
プロセッサ６２０は、１つ又は複数のマイクロプロセッサ又はマイクロコントローラによって具体化することができ、メモリ６３０内に格納されたコンピュータ可読プログラム命令を実行して、図１〜図７に関連して上述した動作を行う。
【００６７】
メモリ６３０は、コンピュータ可読プログラム命令を含むソフトウェアでコード化されたコンピュータ可読ストレージ媒体を含むことができ、該ソフトウェアがプロセッサ６２０によって実行されたとき、プロセッサ６２０は、本明細書においてゾーンマップ作成、ソート及び評価論理６３５に関連して説明した動作を行うように動作可能である。
【００６８】
サーバシステム１１０及び１２０並びにクライアントシステム１００は、ディスプレイ又はモニタと、本体（例えば、少なくとも１つのプロセッサ、１つ又は複数のメモリ、及び／又は内部若しくは外部ネットワークインタフェース若しくは通信装置（例えばモデム、ネットワークカード等）を含む）と、随意の入力装置（例えば、キーボード、マウス又はその他の入力装置）と、任意の市販のソフトウェア及びカスタム・ソフトウェア（例えば、サーバ／通信ソフトウェア、モジュール、ブラウザ／インタフェースソフトウェア、等）とを装備することが好ましい、任意の従来型又はその他のコンピュータシステムによって実装することができる。
【００６９】
あるいは、１つ又は複数のクライアントシステム１００は、独立型ユニットとして動作しているときに文書を解析することができる。独立型動作モードにおいて、クライアントシステムは、データ（例えばデータベース・ストレージユニット１４０）を格納するか又はこれに対するアクセスを有しており、クエリ要求を構築するため及び／又はホストサーバ１１０に送るためのモジュールを含む。グラフィカルユーザインタフェース（例えば、ＧＵＩ等）又はその他のインタフェース（例えば、コマンドラインプロンプト、メニュスクリーン、等）は、所望の文書及び解析に関係した対応のユーザからの情報を求め、解析結果を含むレポートを提供することができる。
【００７０】
モジュールは、本明細書で説明した本発明の実施形態の種々の機能を行うための１つ又は複数のモジュール又はユニットを含むことができる。種々のモジュール（例えば、論理モジュール６３５、等）は、任意の数量のソフトウェア及び／又はハードウェアモジュール又はユニットの任意の組合せによって実装することができ、プロセッサ６２０による実行のために情報サーバ１２０のメモリ６３０内に常駐することができる。
【００７１】
上で説明し、図面に示した実施形態は、実施形態を実装するための多くの方式のうちのいくつかに過ぎないことが理解されるであろう。
【００７２】
本発明の実施形態の環境は、所望の様式で配置された、任意の数のコンピュータ又はその他の処理システム（例えば、クライアント又はエンドユーザシステム、サーバシステム、等）及びデータベース又はその他のリポジトリを含み、本発明の実施形態は、任意の所望の型式のコンピューティング環境（例えば、クラウドコンピューティング、クライアント・サーバ、ネットワークコンピューティング、メインフレーム、独立型システム、等）に適用することができる。本発明の実施形態により使用されるコンピュータ又はその他の処理システムは、任意の数の、任意のパーソナルコンピュータ又はその他の型式のコンピュータ又は処理システム（例えば、デスクトップ、ラップトップ、ＰＤＡ、移動体装置、等）により実装することができ、任意の市販のオペレーティングシステム及び市販のソフトウェアおよびカスタム・ソフトウェア（例えば、ブラウザソフトウェア、通信ソフトウェア、サーバソフトウェア、プロファイル生成モジュール、プロファイル比較モジュール、等）の任意の組合せ含むことができる。これらのシステムは、情報を入力及び／又は閲覧するための任意の型式のモニタ及び入力装置（例えば、キーボード、マウス、音声認識、等）を含むことができる。
【００７３】
本発明の実施形態のソフトウェア（例えば、論理６３５）は、任意の所望のコンピュータ言語で実装することができ、コンピュータ分野の当業者が、明細書に含まれる機能的説明及び図面に示すフローチャートに基づいて開発することができることを理解されたい。さらに、本明細書における種々の機能を行うソフトウェアへの言及はいずれも、一般に、それらの機能をソフトウェアの制御下で行うコンピュータ又はプロセッサを指すものとする。本発明の実施形態のコンピュータシステムは、任意の型式のハードウェア及び／又はその他の処理回路により代替的に実装することができる。
【００７４】
コンピュータ又はその他の処理システムの種々の機能は、任意の数のソフトウェア及び／又はハードウェアモジュール又はユニット、処理又はコンピュータシステム及び／又は回路の間で任意の方式で分散させることができ、ここでコンピュータ又は処理システムは、互いにローカルに又は遠隔に配置することができ、任意の適切な通信媒体（例えば、ＬＡＮ、ＷＡＮ、イントラネット、インターネット、配線、モデム接続、無線、等）を介して通信することができる。例えば、本発明の実施形態の機能は、種々のエンドユーザ／クライアント及びサーバシステム、及び／又は任意のその他の中間処理装置の間で任意の方式で分散させることができる。上で説明し、フローチャートで示したソフトウェア及び／又はアルゴリズムは、本明細書で説明した機能を達成する任意の方式で修正することができる。さらに、フローチャート又は説明内の機能は、所望の動作を達成する任意の順序で行うことができる。
【００７５】
本発明の実施形態のソフトウェア（例えば、論理６３５に対応するソフトウェア、等）は、独立型システム又はネットワーク若しくは他の通信媒体により接続されるシステムと共に用いるための、固定型又は携帯型のプログラム製品装置又はデバイスの、非一時的なコンピュータ使用可能媒体（例えば、磁気又は光学媒体、磁気光学媒体、フロッピーディスケット、ＣＤ−ＲＯＭ、ＤＶＤ、メモリ装置、等）上で利用可能であり得る。
【００７６】
通信ネットワークは、任意の数の任意の型式の通信ネットワーク（例えば、ＬＡＮ、ＷＡＮ、インターネット、イントラネット、ＶＰＮ、等）によって実装することができる。本発明の実施形態のコンピュータ又はその他の処理システムは、任意の従来型又はその他のプロトコルによりネットワーク上で通信するための、任意の従来型又はその他の通信装置を含むことができる。コンピュータ又はその他の処理システムは、ネットワークへのアクセスのために任意の型式の接続（例えば、有線、無線、等）を利用することができる。ローカル通信媒体は、任意の適切な通信媒体（例えば、ローカルエリアネットワーク（ＬＡＮ）、配線、無線リンク、イントラネット、等）により実装することができる。
【００７７】
システムは、情報（例えば、データベース・ストレージユニット１４０、ゾーンマップ、上位Ｎ結果、等）を格納するために、任意の数の任意の従来型又はその他のデータベース、データストア又はストレージ構造（例えば、ファイル、データベース、データ構造、データ又はその他のリポジトリ、等）を使用することができる。データベースシステムは、情報（例えば、データベース・ストレージユニット１４０、ゾーンマップ、上位Ｎ結果、等）を格納するために、任意の数の任意の従来型又はその他のデータベース、データストア又はストレージ構造（例えば、ファイル、データベース、データ構造、データ又はその他のリポジトリ、等）実装することができる。データベースシステムは、サーバ及び／又はクライアントシステム内に含めるか又はこれに結合することができる。データベースシステム及び／又はストレージ構造は、コンピュータ又はその他の処理システムの遠隔又はローカルとすることができ、任意の所望のデータを格納することができる。
【００７８】
本発明の実施形態は、情報（例えば、クライアント１００からのクエリ要求、上位Ｎ結果、等）を得るため又は提供するために、任意の数の任意の型式のユーザインタフェース（例えば、グラフィカルユーザインタフェース（ＧＵＩ）、コマンドライン、プロンプト、等）を使用することができ、ここでインタフェースは、任意の様式で配置された任意の情報を含むことができる。インタフェースは、任意の適切な入力装置（例えば、マウス、キーボード、等）を介して情報を入力／表示し、所望の動作を始動するために、任意の位置に配置された任意の数の任意の型式の入力又は作動機構（例えば、ボタン、アイコン、フィールド、ボックス、リンク、等）を含むことができる。インタフェース画面は、画面間を任意の様式でナビゲートするために、任意の適切なアクチュエータ（例えば、リンク、タブ、等）を含むことできる。
【００７９】
レポートは、任意の様式で配置された任意の情報を含むことができ、所望の情報をユーザに提供する（例えば、テキスト解析、プロファイルスコア、文献の著者に関する人口統計的情報）ために、規則又はその他の基準に基づいて構成可能なものとすることができる。
【００８０】
本発明の実施形態は、上述の特定のタスク又はアルゴリズムに限定されない。
【００８１】
本明細書において用いられる用語は、特定の例を説明する目的のためのものにすぎず、本発明を限定することを意図したものではない。本明細書で用いられる場合、単数形「１つの（a）」、「１つの（an）」及び「その（the）」は、文脈が明らかにそうでないことを示していない限り、複数形もまた同様に含むことを意図したものである。「備える」、「備えている」、「含む」、「含んでいる」、「有する」、「有している」、「伴う」及び同様の用語は、本明細書で用いられる場合、記述された特徴、整数、ステップ、動作、要素、及び／又は構成要素の存在を指定するが、１つ又は複数のその他の特徴、整数、ステップ、動作、要素、構成要素、及び／又はそれらの群の存在又は付加を排除するものではないことが更に理解されるであろう。
【００８２】
以下の特許請求の範囲における全ての「手段又はステップと機能との組み合わせ（ミーンズ又はステップ・プラス・ファンクション）」要素の対応する構造、材料、動作、及び均等物は、その機能を、明確に特許請求された他の請求要素との組み合わせで実行するためのあらゆる構造、材料、又は動作を含むことが意図されている。本発明の説明は、例証及び説明を目的として提示されたものであるが、網羅的であること又は本発明を開示された形態に限定することを意図したものではない。本発明の範囲及び趣旨から逸脱しない多くの修正及び変形が当業者には明らかとなるであろう。実施形態は、本発明の原理及び実際の用途を最も良く説明するために、そして、当業者が、企図した特定の用途に適した種々の修正を伴う種々の実施形態に関して本発明を理解できるように、選択及び説明したものである。
【００８３】
本発明の種々の実施形態の説明を例証のために提示したが、これらは網羅的であること又は開示された実施形態に限定することを意図したものではない。当業者には、説明した実施形態の範囲及び趣旨から逸脱しない多くの修正及び変形が明白となるであろう。本明細書で用いた用語は、実施形態の原理、実際的用途、又は市場で見いだされる技術に対する技術的改良点を最も良く説明するように、又は、当業者が本明細書で開示した実施形態を理解することができるように、選択されたものである。
【００８４】
本発明は、システム、方法、及び／又はコンピュータ・プログラム製品とすることができる。コンピュータ・プログラム製品は、本発明の態様をプロセッサに実行させるためのコンピュータ可読プログラム命令を有する１つ又は複数のコンピュータ可読ストレージ媒体を含むことができる。
【００８５】
コンピュータ可読ストレージ媒体は、命令実行デバイスが使用するための命令を保持し、格納することができる有形デバイスとすることができる。コンピュータ可読ストレージ媒体は、例えば、電子ストレージ装置、磁気ストレージ装置、光ストレージ装置、半導体ストレージ装置、又は上記のものの任意の適切な組合せとすることが出来るがこれらに限定されない。コンピュータ可読ストレージ媒体のより具体的な例の非網羅的なリストは、ポータブル・コンピュータ・ディスケット、ハードディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能プログラム可能読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）、静的ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、デジタル多目的ディスク（ＤＶＤ）、メモリスティック、フロッピーディスク、パンチカード若しくは記録された命令を有する溝内に隆起した構造のような機械式コード化デバイス、及び上記のものの任意の適切な組合せを含む。コンピュータ可読ストレージ媒体は、本明細書で用いられる場合、無線波若しくは他の自由に伝搬する電磁波、導波路若しくは他の伝送媒体を通って伝搬する電磁波（例えば光ファイバケーブルを通る光パルス）、又は電線を通って伝送される電気信号のような、それ自体が一時的な信号と解釈されるべきではない。
【００８６】
本明細書で説明されるコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体からそれぞれのコンピューティング／処理装置にダウンロードすることも、又は、例えばインターネット、ローカルエリアネットワーク、広域ネットワーク及び／又は無線ネットワークを経由して、外部コンピュータ若しくは外部ストレージ・デバイスにダウンロードすることもできる。ネットワークは、銅伝送ケーブル、光伝送ファイバ、無線伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイコンピュータ及び／又はエッジサーバを含むことができる。各コンピューティング／処理デバイス内のネットワーク・アダプタ・カード又はネットワークインタフェースは、ネットワークからコンピュータ可読プログラム命令を受け取り、コンピュータ可読プログラム命令をそれぞれのコンピューティング／処理装置内のコンピュータ可読ストレージ媒体にストレージのために転送する。
【００８７】
本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械語命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データ（state-setting data）、又は、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語及び「Ｃ」プログラミング言語若しくは類似のプログラミング言語のような従来の手続き型プログラミング言語を含む１つ若しくは複数のプログラミング言語の任意の組合せで記述されたソースコード若しくはオブジェクトコードのいずれか、とすることができる。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で、独立型ソフトウェア・パッケージとして実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部が遠隔コンピュータ上で実行される場合もあり、又は完全に遠隔コンピュータ若しくはサーバ上で実行される場合もある。後者のシナリオにおいては、遠隔コンピュータは、ローカルエリアネットワーク（ＬＡＮ）若しくは広域ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続される場合もあり、又は外部コンピュータへの接続が為される場合もある（例えば、インターネット・サービス・プロバイダを用いたインターネットを通じて）。幾つかの実施形態において、例えばプログラム可能論理回路、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）、又はプログラム可能論理アレイ（ＰＬＡ）を含む電子回路は、本発明の態様を実施するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路を個別化することにより、コンピュータ可読プログラム命令を実行することができる。
【００８８】
本発明の態様は、本明細書において、本発明の実施形態による方法、装置（システム）、及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して説明される。フローチャート図及び／又はブロック図の各ブロック、並びにフローチャート図及び／又はブロック図のブロックの組合せは、コンピュータ可読プログラム命令によって実装することができることが理解されよう。
【００８９】
これらのコンピュータ可読プログラム命令を、汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置のプロセッサに与えてマシンを製造し、それにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサによって実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロック内で指定された機能／動作を実装するための手段を作り出すようにすることができる。これらのコンピュータ・プログラム命令を、コンピュータ、プログラム可能データ処理装置、及び／又は他のデバイスを特定の方式で機能させるように指示することができるコンピュータ可読媒体内に格納し、それにより、その中に格納された命令を有するコンピュータ可読媒体が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作の態様を実装する命令を含む製品を含むようにすることもできる。
【００９０】
コンピュータ可読プログラム命令を、コンピュータ、他のプログラム可能データ処理装置又は他のデバイス上にロードして、一連の動作ステップをコンピュータ、他のプログラム可能データ処理装置又は他のデバイス上で行わせてコンピュータ実装のプロセスを生成し、それにより、コンピュータ、他のプログラム可能装置又は他のデバイス上で実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実装するようにすることもできる。
【００９１】
図面内のフローチャート及びブロック図は、本開示の種々の実施形態による、システム、方法、及びコンピュータ・プログラム製品の可能な実装の、アーキテクチャ、機能及び動作を示す。この点に関して、フローチャート又はブロック図内の各ブロックは、指定された論理機能を実装するための１つ又は複数の実行可能命令を含む、モジュール、セグメント、又は命令の一部を表すことができる。幾つかの代替的な実装において、ブロック内に記された機能は、図中に記された順序とは異なる順序で行われることがある。例えば、連続して示された２つのブロックは、関与する機能に応じて、実際には実質的に同時に実行されることもあり、又はこれらのブロックはときとして逆順で実行されることもある。ブロック図及び／又はフローチャート図の各ブロック、及びブロック図及び／又はフローチャート図中のブロックの組合せは、指定された機能又は動作を実行する専用ハードウェア・ベースのシステムによって実装することもでき、又は専用ハードウェアとコンピュータ命令との組合せを実行することもできることにも留意されたい。
【図１】
0006336096.tif 000002
【図２】
0006336096.tif 000003
【図３】
0006336096.tif 000004
【図４】
0006336096.tif 000005
【図５】
0006336096.tif 000006
【図６】
0006336096.tif 000007
【図７】
0006336096.tif 000008
【図８】
0006336096.tif 000009