(57)【要約】【課題】圧縮データシステムの必要メモリを低減するために、個々のレコードまたはレコード内の値は、格納される際に圧縮され、およびアクセスされる際に圧縮解除（復号）され得る。【解決手段】通常、データ構造内に格納されたレコードの数値属性の値を受信する。数値属性の値を含む数値範囲を生成する。データ構造内のレコードの場所を規定するとともに第１のインデックスキー（１００６）と第２のインデックスキー（１００８）を含むエントリを、データ構造に関連付けられたインデックス（２０４）内に格納する。第１のインデックスキー（１００６）は数値属性と異なるレコードの属性の値に対応し、第２のインデックスキー（１００８）は生成された数値範囲に対応する。【選択図】図１
2014524090.tif 000002
【特許請求の範囲】
【請求項１】
データ構造内に格納されたレコードの数値属性の値を受信する工程と、
前記数値属性の前記値を含む数値範囲を生成する工程と、
前記データ構造内の前記レコードの場所を特定するエントリであり、前記数値属性と異なる前記レコードの属性の値に対応する第１のインデックスキーと前記生成された数値範囲に対応する第２のインデックスキーとを含むエントリを、前記データ構造に関連付けられたインデックス内に格納する工程と
を含む方法。
【請求項２】
前記数値属性の前記値はタイムスタンプにより表され、前記数値範囲はある範囲の時間を規定する、請求項１に記載の方法。
【請求項３】
前記数値範囲を生成する工程は、前記タイムスタンプに対応する時間を所定の時点から分離する時間単位における第１の値を判断する工程を含む、請求項２に記載の方法。
【請求項４】
前記数値範囲は所定の期間の時間範囲であり、前記数値範囲を生成する工程は、前記数値範囲を表す商を与えるために前記第１の値を前記所定の期間で割る工程を含む、請求項３に記載の方法。
【請求項５】
前記エントリはさらに、前記第１のインデックスキーと前記第２のインデックスキーに関連付けられた第２のレコードの前記データ構造内の場所を特定する、請求項１に記載の方法。
【請求項６】
前記第１のレコードと前記第２のレコードは相異なるタイムスタンプにより表される数値属性の値を含む、請求項５に記載の方法。
【請求項７】
前記第１のインデックスキーに関連付けられるとともに、第１の時間と第２の時間の間の時間に関連付けられたレコードの検索を要求する問い合わせを受信する工程をさらに含む、請求項５に記載の方法。
【請求項８】
前記第１の時間と前記第２の時間のそれぞれの数値範囲を生成する工程をさらに含む、請求項７に記載の方法。
【請求項９】
前記それぞれの数値範囲を生成する工程は、
第２の所定の時点から前記第１の時間を分離する時間単位における第２の値を判断する工程と、
前記第２の所定の時点から前記第２の時間を分離する時間単位における第３の値を判断する工程と
を含む、請求項８に記載の方法。
【請求項１０】
前記それぞれの数値範囲を生成する工程は、
前記第１の時間の数値範囲を表す商を提供するために前記第２の値を前記所定の期間で割る工程と、
前記第２の時間の数値範囲を表す商を提供するために前記第３の値を前記所定の期間で割る工程と
を含む、請求項９に記載の方法。
【請求項１１】
前記第１のインデックスキーと、前記第１の時間の前記数値範囲または前記第２の時間の前記数値範囲に等しい数値範囲、または前記第１の時間と前記第２の時間のそれぞれの数値範囲間にある数値範囲に対応する第２のインデックスキーとを含むエントリをインデックス内で特定する工程をさらに含む、請求項１０に記載の方法。
【請求項１２】
計算システムに、
データ構造内に格納されたレコードの数値属性の値を受信させ、
前記数値属性の前記値を含む数値範囲を生成させ、
前記データ構造内の前記レコードの場所を特定するエントリであり、前記数値属性と異なるレコードの属性の値に対応する第１のインデックスキーと前記生成された数値範囲に対応する第２のインデックスキーとを含むエントリを、前記データ構造に関連付けられたインデックス内に格納させる
ための命令を含むコンピュータプログラムを格納するコンピュータ可読記憶媒体。
【請求項１３】
データ構造内に格納されたレコードの数値属性の値を受信するように構成された入力装置またはポートと、
少なくとも１つのプロセッサであって、
前記数値属性の前記値を含む数値範囲を生成し、
前記データ構造内の前記レコードの場所を特定するエントリであり、前記数値属性と異なるレコードの属性の値に対応する第１のインデックスキーと前記生成された数値範囲に対応する第２のインデックスキーとを含むエントリを、前記データ構造に関連付けられたインデックス内に格納するように構成された、少なくとも１つのプロセッサと
を含む計算システム。
【請求項１４】
データ構造内に格納されたレコードの数値属性の値を受信する手段と、
前記レコードにインデックスを付ける手段と
を含む計算システムであって、前記インデックス付け工程は、
前記数値属性の前記値を含む数値範囲を生成する工程と、
前記データ構造内の前記レコードの場所を特定するエントリであり、前記数値属性と異なる前記レコードの属性の値に対応する第１のインデックスキーと前記生成された数値範囲に対応する第２のインデックスキーとを含むエントリを、前記データ構造に関連付けられたインデックス内に格納する工程と
を含む計算システム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は２０１１年７月８日出願の米国出願第６１／５０５，７６０号からの優先権を主張し、参照のためその全体を本明細書に援用する。
【背景技術】
【０００２】
背景
本発明は、範囲に基づく検索のためのデータ格納の管理に関する。データベースシステムは、個々にアクセス可能なデータの単位または「レコード」を格納することができる。各レコードは、クレジットカード決済などの論理エンティティに対応し得、レコードを一意的に特定するために使用される関連一次キーを有し得る。レコードは、レコードフォーマットのそれぞれのフィールドに関連付けられた複数の値を含むことができる。レコードは、１つまたは複数のファイル（例えば、フラットファイル、またはＸＭＬファイルなどの構造化データファイル）内に格納されることができる。圧縮データベースシステム（compressed database system）内では、同システムの必要メモリを低減するために、個々のレコードまたはレコード内の値は、格納される際に圧縮され、およびアクセスされる際に圧縮解除（復号）され得る。
【発明の概要】
【課題を解決するための手段】
【０００３】
概要
一態様では、通常、データ構造内に格納されたレコードの数値属性の値を受信する。数値属性の値を含む数値範囲が生成される。データ構造内のレコードの場所を特定するとともに第１のインデックスキーと第２のインデックスキーを含むエントリを、データ構造に関連付けられたインデックス内に格納する。第１のインデックスキーは数値属性と異なるレコードの属性の値に対応し、第２のインデックスキーは生成された数値範囲に対応する。
【０００４】
様々な態様は以下の特徴の１つまたは複数を含むことができる。
【０００５】
数値属性の値はタイムスタンプにより表され、数値範囲はある範囲の時間を規定する。
【０００６】
数値範囲を生成する工程は、タイムスタンプに対応する時間を所定の時点から分離する時間単位の第１の値を判断する工程を含む。
【０００７】
数値範囲は所定の期間の時間範囲であり、数値範囲を生成する工程は、数値範囲を表す商を与えるために第１の値を所定の期間で割る工程を含む。
【０００８】
エントリはさらに、第１のインデックスキーと第２のインデックスキーに関連付けられた第２のレコードのデータ構造内の場所を特定する。
【０００９】
第１のレコードと第２のレコードは相異なるタイムスタンプにより表される数値属性の値を含む。
【００１０】
第１のインデックスキーに関連付けられ第１の時間と第２の時間の間の時間に関連付けられたレコードの検索を要求する問い合わせを受信する。
【００１１】
それぞれの数値範囲が第１の時間と第２の時間に対して生成される。
【００１２】
それぞれの数値範囲を生成する工程は、第２の所定の時点から第１の時間を分離する時間単位の第２の値を判断する工程と、第２の所定の時点から第２の時間を分離する時間単位の第３の値を判断する工程とを含む。
【００１３】
それぞれの数値範囲を生成する工程は、第１の時間の数値範囲を表す商を与えるために第２の値を所定の期間で割る工程と、第２の時間の数値範囲を表す商を与えるために第３の値を所定の期間で割る工程とを含む。
【００１４】
第１のインデックスキーと、第１の時間の数値範囲または第２の時間の数値範囲に等しい数値範囲または第１の時間と第２の時間のそれぞれの数値範囲間にある数値範囲に対応する第２のインデックスキーとを含むエントリを、インデックス内で特定する。
【００１５】
別の一般的態様では、コンピュータ可読記憶媒体が、計算システムにデータ構造内に格納されたレコードの数値属性の値を受信させるとともに数値属性の値を含む数値範囲を生成させるための命令を含むコンピュータプログラムを格納する。命令はさらに、コンピュータシステムに、データ構造内のレコードの場所を特定するエントリであり、数値属性と異なるレコードの属性の値に対応する第１のインデックスキーと生成された数値範囲に対応する第２のインデックスキーとを含むエントリを、データ構造に関連付けられたインデックス内に格納させる。
【００１６】
さらに一般的な態様では、計算システムはデータ構造内に格納されたレコードの数値属性の値を受信するように構成された入力装置またはポートを含む。計算システムはさらに少なくとも１つのプロセッサを含む。少なくとも１つのプロセッサは、数値属性の値を含む数値範囲を生成するように構成され、さらに、データ構造内のレコードの場所を特定するエントリであり、数値属性と異なるレコードの属性の値に対応する第１のインデックスキーと生成された数値範囲に対応する第２のインデックスキーとを含むエントリをデータ構造に関連付けられたインデックス内に格納するように構成される。
【００１７】
別の一般的態様では、計算システムは、データ構造内に格納されたレコードの数値属性の値を受信する手段と、レコードにインデックスを付ける手段とを含む。インデックスを付ける工程は、数値属性の値を含む数値範囲を生成する工程と、データ構造内のレコードの場所を特定するエントリであり、数値属性と異なるレコードの属性の値に対応する第１のインデックスキーと生成された数値範囲に対応する第２のインデックスキーとを含むエントリを、データ構造に関連付けられたインデックス内に格納する工程とを含む。
【００１８】
様々な態様は、以下の利点の１つまたは複数を含むことができる。
【００１９】
データの格納とインデックス付けとを管理する技術は、圧縮解除され（レコードが圧縮されていれば）、メモリ内にロードされ、および／または所与の問い合わせに合致しなければ廃棄されねばならないレコードの量を低減することができる。いくつかの例では、レコードは時間などの数値属性に従ってグループで格納される（例えば、レコードが電話呼に対応すれば、レコードは、所与の発呼が行われた時間に基づき１日の発呼を表すデータファイルに格納され得る）。それぞれのデータファイル内の各レコードの場所を特定するインデックスが、格納されたレコードのグループ毎に与えられ得る。
【００２０】
いくつかの例では、問い合わせ内に規定されたパラメータに合致する１つまたは複数のレコードを見つけることが望ましい場合もある。しかし、問い合わせ内に規定されたパラメータの１つがある範囲の時間に関係すれば、その期間が比較的短くても（例えば、当該日の１０分）、いくつかのシステムは、丸一日を表すデータファイルが圧縮解除され（データファイルが圧縮されていれば）、メモリ内にロードされ、パラメータと照合されることを必要とし得る。したがって、本開示は、数値範囲（例えば、時間カンタム（time quantum）と呼ばれることがある時間の範囲）を含むエントリであり、少量のレコードを圧縮解除し、ロードし、廃棄する一方で問い合わせを満足する可能性のあるレコードを見つけるためにインデックスを効率的に検索するために使用することができるエントリを、インデックス内に提供するための技術を提供する。本明細書に記載の技術の多くは、新しいインデックスを生成するためにまたは既存のインデックスを更新するために使用することができる。
【００２１】
本発明の他の特徴と利点は以下の説明と特許請求範囲から明らかになる。
【図面の簡単な説明】
【００２２】
【図１】レコードを格納し取り出すためのシステムのブロック図である。
【図２Ａ】システムにより処理され同システム内に格納されるデータの概略図である。
【図２Ｂ】システムにより処理され同システム内に格納されるデータの概略図である。
【図２Ｃ】システムにより処理され同システム内に格納されるデータの概略図である。
【図２Ｄ】システムにより処理され同システム内に格納されるデータの概略図である。
【図３Ａ】様々なシグネチャサイズの偽陽性（false positive）確率を示す表である。
【図３Ｂ】様々なシグネチャサイズの偽陽性確率を示す表である。
【図４Ａ】レコードを検索するための手順のフローチャートである。
【図４Ｂ】レコードを検索するための手順のフローチャートである。
【図５】レコードを検索するための手順のフローチャートである。
【図６Ａ】追加可能ルックアップファイルの概略図である。
【図６Ｂ】追加可能ルックアップファイルの概略図である。
【図７】追加可能ルックアップファイルを検索するための手順のフローチャートである。
【図８】データを格納するための手順のフローチャートである。
【図９】レコードを格納し取り出すためのシステムのブロック図である。
【図１０】例示的インデックスの図である。
【図１１】インデックス内に情報を提供するための手順のフローチャートである。
【発明を実施するための形態】
【００２３】
詳細
図１を参照すると、レコード格納および検索（retrieval）システム１００はソースＡ〜ソースＣなど１つまたは複数のソースからデータを受信する。データは、個々にアクセス可能なデータの単位として表すことができる情報を含む。例えば、クレジットカード会社は、様々な小売り会社から個々の決済を表すデータを受信し得る。各決済は、顧客名、日付、購入額などの属性を表す値に関連付けられる。レコード処理モジュール１０２は、決済に関連付けられた値がレコード内に格納されるように、データが所定のレコードフォーマットに従ってフォーマット化されることを保証する。ある場合には、これはソースからのデータをレコードフォーマットに従って変換することを含み得る。他の場合には、１つまたは複数のソースはレコードフォーマットに従って既にフォーマット化されたデータを提供し得る。
【００２４】
レコード処理モジュール１０２は、格納されたレコードに迅速にアクセスする必要があり得るかどうかなど様々な要因に応じて様々な種類のデータ構造に格納するためのレコードを作成する。高速アクセス可能なレコードを追加可能ルックアップファイル内に作成する際、処理モジュール１０２は、以下にさらに詳細に説明されるように、レコードが到着するとそれを追加可能ルックアップファイル内に追加し、メモリ内インデックスを維持する。圧縮レコードファイル（compressed record file）内に圧縮し格納されるレコードを作成する際、処理モジュール１０２は、各レコードを特定する一次キー値（例えば、単一レコードを特定する固有キー、またはレコードの複数の更新バージョンを特定するキーのいずれか）によりレコードをソートし、そのレコードを一次キー値の非オーバーラップ範囲に対応するレコードの組に分割する。例えば、各レコードの組は所定数のレコード（例えば、１００個のレコード）に対応し得る。
【００２５】
ファイル管理モジュール１０４は、追加可能ルックアップファイル（それが使用される状況では）と圧縮ルックアップファイル（compressed lookup file）の両方を管理する。圧縮レコードファイルを管理する際、ファイル管理モジュール１０４は、各レコードの組を圧縮データブロックに圧縮する。これらの圧縮ブロックは、レコード記憶装置１０６内（例えば、１つまたは複数のハードディスク駆動装置などの不揮発性記憶媒体内）の圧縮レコードファイル内に格納される。
【００２６】
システム１００はまた、ブロックのそれぞれのエントリを含むインデックスを圧縮レコードファイル内に提供するインデックス付けおよび検索モジュール１０８を含む。以下にさらに詳細に説明されるように、インデックスは、所与のレコードを含み得るブロックを見つけるために使用される。インデックスは、インデックス記憶装置１１０内のインデックスファイル内に格納されることができる。例えば、インデックスファイルは、圧縮レコードファイルと同じ記憶媒体内に格納されることができるが、インデックスファイルは、通常圧縮レコードファイルよりはるかに小さいので、インデックスファイルは好適には、比較的速いメモリ（例えば、ダイナミックランダムアクセスメモリなどの揮発性記憶装置媒体）内に格納され得る。インデックスはまた、メモリ内データ構造として維持される動的インデックス１１４である可能性がある。動的インデックス１１４のいくつかの例はハッシュ表、バイナリーツリー、およびｂ−ツリーである。以下にさらに詳細に説明されるように、インデックス付けおよび検索モジュール１０８はまた、追加可能ルックアップファイルを検索するためのインターフェースを提供する。
【００２７】
システム１００の代替実施態様では、複数の組のレコードは、レコードをいくつかのやり方で組み合わせるための圧縮に加えてまたはその代わりに他の機能を使用することにより、ブロックを生成するように処理されることができる（すなわち、ブロックが単に一組の連結されたレコードとならないように）。例えば、いくつかのシステムは、暗号データのブロックを生成するために一組のレコードを処理し得る。
【００２８】
インターフェースモジュール１１２は、格納されたレコードへのアクセスをエージェントＡ〜エージェントＤなどの人間および／またはコンピュータエージェントへ提供する。例えば、インターフェースモジュール１１２は、クレジットカード顧客が自身の決済を監視するためのオンライン口座システムを実現することができる。様々な判定基準を満足する決済情報の要求をシステム１００により処理することができ、対応するレコードを、レコード記憶装置１０６内に格納された圧縮ブロック内から取り出すことができる。
【００２９】
１つまたは複数のソースから入ってくるレコードのストリームは、圧縮レコードファイルを生成するために処理される前に、一時的に格納され得る。
【００３０】
図２Ａ〜２Ｄ、図３Ａ〜３Ｂ、図４Ａ〜４Ｂは、圧縮レコードファイル内のレコードを管理する例を示す。図２Ａを参照すると、システム１００は、圧縮レコードファイル２０２内に格納される一組のレコード２００を受信し、このレコードを一次キーの値に従ってソートする。
【００３１】
一次キー値は、１つまたは複数のレコードにより表され得るデータベース内の所与の事項を一意的に特定することができる（例えば、所与の一次キー値を有する各レコードは異なる更新バージョンの項目に対応し得る）。一次キーは、レコードの１つまたは複数の既存フィールドに対応する「自然キー」である可能性がある。項目毎に固有であることを保証されたフィールドが無ければ、一次キーは、併せて項目毎に固有であることを保証されたまたはその可能性が高いレコードの複数のフィールドを含む集合キー（compound key）であり得る。あるいは、一次キーは受信された後に各レコードに割り当てることができる「統合キー（synthetic key）」である可能性がある。例えば、システム１００は、連続的にインクリメントされる整数として固有一次キー値、または単調に進む値（例えば、タイムスタンプ）の他のある系列を割り当てることができる。この場合、同じ項目の異なるバージョンを表すレコードが、異なる統合キー値を割り当てられ得る。整数が使用される場合、可能な一次キー値の範囲（例えば、使用されるビット数により判断されるような）は、一次キーがロールオーバー（roll over）したとしても所与の一次キー値を前に割り当てられた任意のレコードが圧縮レコードファイルから除去されてしまうように十分に大きくすることができる。例えば、古い決済は除去され、かつアーカイブまたは廃棄され得る。
【００３２】
図２Ａに示す例では、レコード２００はアルファベット順（Ａ，ＡＢ，ＣＺ，．．．）にソートされた一次キー値により特定される。システム１００は、一次キー値Ａ〜ＤＤを有する第１の組のＮ個のレコードを圧縮して、ブロック１と標記された、対応する圧縮ブロックを生成する。次の組のレコードは、一次キー値ＤＸ〜ＧＦを有する次のＮ個のソートされたレコードを含む。ファイル管理モジュール１０４は、様々な無損失データ圧縮アルゴリズムのうちの任意のもの（例えば、Lempel-Zivタイプアルゴリズム）を使用することができる。次の各圧縮ブロックが、圧縮レコードファイル２０２を形成するために組み合わせられる。
【００３３】
圧縮ブロックを生成するために使用されるレコードの数Ｎは、圧縮効率と圧縮解除（復号）速度とをトレードオフするように選択することができる。圧縮は、圧縮されるデータの性質と圧縮されるデータのサイズに依存する所与の係数Ｒだけ平均でデータのサイズを低減し得る（例えば、Ｒは通常、多くのデータが圧縮される場合は小さい）。圧縮はまた、平均サイズＯの関連付けオーバーヘッド（例えば、圧縮関連データ）を有し得る。Ｍ個のレコード（それぞれのサイズはＸ）から生成された結果の圧縮レコードファイルの平均サイズは、［Ｍ／Ｎ］（ＲＮＸ＋Ｏ）と表すことができる（多数のブロックでは、ＲＭＸ＋ＯＭ／Ｎと近似することができる）。したがって、より大きなＮの値は、ある場合には、Ｒを低減することとファイルのサイズに対するオーバーヘッドの寄与を低減することの両方により、より大きな圧縮を実現することができる。より小さなＮの値は、ブロック内に含まれ得るレコードにアクセスするために所与の圧縮ブロックを圧縮解除するのに必要な時間を低減する。
【００３４】
他の実施態様では、様々な圧縮ブロックが様々な数のレコードを含み得る。各ブロックは所定範囲に基づき多数のレコードを有し得る。例えば、第１のブロックは、一次キー値１〜１０００を有するレコードを含み、第２のブロックは、一次キー値１００１〜２０００を有するレコードを含む。この例の圧縮ブロック内のレコードの数は、すべての一次キー値が必ずしも存在するとは限らないので（例えば、自然キーとして使用される既存の数値フィールドの場合）、異なる可能性があるだろう。
【００３５】
いくつかの実施形態では、様々な圧縮ブロックが場合によっては目標数のレコードを含み得、例外的にはより多いまたは少ないレコードを含み得る。例えば、一組のレコードが、その一次キー値がソートされた順序の次のレコードの一次キー値とは異なるレコードで終われば、それらのレコードは圧縮ブロックを生成するために使用される。一組のレコードがその一次キー値がソートされた順序の次のレコードの一次キー値と同じであるレコードで終われば、その一次キー値を有するすべての追加レコードはその組に追加される。このようにして、同じ一次キー値が１つの圧縮ブロックから次のものへと跨ることはない。
【００３６】
インデックス付けおよび検索モジュール１０８は、圧縮ブロックのそれぞれのインデックスファイル２０４内にエントリを生成する。インデックスエントリは、例えば対応する未圧縮の組のレコード内の第１のレコードの一次キーにより各圧縮ブロックを特定するキーフィールド２０６を含む。エントリはまた、圧縮レコードファイル２０２内の特定された圧縮ブロックの格納場所を特定する場所フィールド２０８を含む。例えば、場所フィールドは、レコード記憶装置１０６内の絶対アドレスの形式、またはレコード記憶装置１０６内の圧縮レコードファイル２０２の開始のアドレスからオフセットの形式のポインタを含むことができる。
【００３７】
圧縮レコードファイル２０２内の所与のレコードを検索するために、モジュール１０８はキーフィールド２０６に基づきインデックスファイル２０４の検索（例えば、バイナリサーチ）を行うことができる。提供されるキー値（例えば、エージェントの１人により提供される）に対して、モジュール１０８は、提供されたキー値を含むキー値の範囲に対応するレコードを含むブロックを見つける。提供されたキー値を有するレコードは、見つけられたブロックを生成するために使用された一組のレコード内に含まれることもあれば、含まれないこともある。しかし、当該レコードがレコード２００内に存在すれば、当該レコードは、レコード２００が一次キー値によりソートされたので、含まれることになるだろう。次に、モジュール１０８は見つけられたブロックを圧縮解除し、提供されたキー値によりレコードを検索する。一次キー値がレコード毎に固有でない場合、モジュール１０８は、提供されたキー値を有する複数のレコードを圧縮ブロック内に発見し得る。キーフィールド２０６が第１のレコードの一次キーを一組の中に含むこの例では、モジュール１０８は、提供されたキー値より先および後のキー値を有する２つの連続インデックスエントリをそれぞれ検索し、先のキー値を有するエントリに対応するブロックを戻す。ある場合には、提供されたキー値は、インデックスエントリ内のキー値と同じかもしれず、この場合、モジュール１０８はそのエントリに対応するブロックを戻す。
【００３８】
異なる実施態様では、対応ブロックが生成されたレコードに対応するある範囲のキー値を、インデックスファイル２０４内のエントリが特定する様々なやり方がある。図２Ａに示す実施態様と同様に、キー値の範囲は、ブロックを生成するために使用されるレコードの２つの極限キー値間の範囲（例えば、ソートされたアルファベットの一次キー値の系列内の最初と最後、またはソートされた数値一次キー値の系列内の最小および最大）である可能性がある。インデックスエントリは、範囲を規定する極値のいずれかまたはその両方を含むことができる。いくつかの実施形態では、インデックスエントリが所与のブロックの範囲を規定する最小キー値を含めば、圧縮レコードファイル内の最後のブロックに関連付けられた最後のインデックスエントリはまた、当該ブロックの範囲を規定する最大キー値を含み得る。次に、いつ所与のキー値が範囲外となるかを判断するために圧縮レコードファイルを検索する際に、この最大キー値を使用することができる。
【００３９】
あるいは、キー値の範囲は、ブロックを生成するために使用されるレコードのキー値を越えて拡大する範囲となる可能性がある。例えば、１〜１０００の数値一次キー値を有するレコードから生成されたブロックの場合、レコード内に表される最小のキー値は１より大きいことがあり、レコード内に表される最大キー値は１０００より小さいことがある。インデックスエントリは、範囲を規定する極値１と１０００のいずれかまたはその両方を含むことができる。
【００４０】
追加レコードが、当初のレコードのグループが圧縮レコードファイルを生成するために処理された後に到着すると、それらのレコードはバッファ内に格納され、未圧縮形式で検索されることができる。あるいは、追加のレコードのグループは、増分的に処理され、追加インデックスファイルによりアクセス可能な追加の圧縮レコードファイルとして格納されることができる。ある場合には、少数の追加レコードを圧縮することが格納サイズの大きな削減をもたらし得ない場合でも、レコードにアクセスするための一貫した手順を維持するために追加レコードを圧縮することは依然として有利であり得る。追加レコードは、定期的時間間隔で（例えば、３０秒または５分毎）または所定数の追加レコードが受信された後（例えば、１０００個のレコード毎または１０，０００個のレコード毎）に繰り返し処理されることができる。入力レコードが時間間隔に基づき処理される場合、いくつかの時間間隔では、入力レコードが存在し得ない、またはそのすべてが単一の圧縮ブロックに圧縮された少数のレコードが存在し得る。
【００４１】
図２Ｂを参照すると、当初の圧縮レコードファイル２０２が生成された後に追加レコードがシステム１００により受信された例では、集合圧縮レコードファイル（compound compressed record file）２１１を形成するために追加の圧縮レコードファイル２１０を当初の圧縮レコードファイル２０２に追加することができる。システム１００は、一次キー値により追加レコードをソートし、複数の組のＮ個のレコードを圧縮して圧縮レコードファイル２１０の圧縮ブロックを生成する。ブロック９１と標記された追加ファイル２１０内の最初の圧縮ブロックは、一次キー値ＢＡ〜ＦＦを有する。モジュール１０８は、追加ファイル２１０内に表された追加レコードを検索するために利用することができるエントリを含む追加のインデックスファイル２１２を生成する。新しいインデックスファイル２１２は、前のインデックスファイル２０４に追加されることができる。
【００４２】
集合圧縮レコードファイルを形成するために任意の数の圧縮レコードファイルを追加することができる。インデックス付けおよび検索モジュール１０８が集合圧縮レコードファイル内の所与のキー値を有するレコードを検索する場合、モジュール１０８は、対応するインデックスファイルを利用することにより、追加された圧縮レコードファイルのそれぞれの中のレコードを検索する。あるいは、所与のレコードを要求するエージェントは、検索される集合圧縮レコードファイルを有する一定数の圧縮レコードファイル（例えば、１０個のごく最近生成されたもの、または最後の一時間内に生成された任意のもの）を特定することができる。
【００４３】
所与の時間後（例えば、２４時間毎）、または所与の数の圧縮レコードファイルが追加された後、システム１００は、集合圧縮レコードファイルから単一の圧縮レコードファイルを生成して新しい対応するインデックスファイルを生成するためにファイルを統合することができる。統合後、所与のレコードを含み得る圧縮ブロックを見つけるために単一インデックスを検索することができ、より効率的レコードアクセスとなる。統合時、システム１００は、対応するソートされたレコードの組を復元するために圧縮レコードファイルを圧縮解除し、一次キー値によりレコードをソートし、新しい圧縮レコードファイルおよびインデックスを生成する。復元されたレコードの組のそれぞれは既にソートされているので、レコードは、単一のソートされたレコードの組を生成するために、前にソートされたリストを一次キー値に従ってマージすることにより効率的にソートされることができる。
【００４４】
図２Ｃを参照すると、集合圧縮レコードファイル２１１は、当初の圧縮レコードファイル２０２、追加の圧縮レコードファイル２１０、およびどのくらいの数の追加レコードが到着しどれくらい頻繁にレコードが処理されたかに応じ多くの追加の圧縮レコードファイル２２０、２２１，．．．を含む。各圧縮レコードファイルは、当該ファイルの圧縮ブロック内の所与のレコードを検索するために利用することができる関連インデックスファイルを有することができる。この例では、圧縮レコードファイル２２０の１つは、単一の圧縮ブロックだけ（ブロック９５）を有するためには十分に小さく、したがって関連インデックスファイルを必ずしも必要としないが、ブロック内のある範囲の一次キー値および記憶装置内のその場所を示す関連データを有することができる。統合後、様々な追加された圧縮レコードファイルから復元されたレコードは、単一の圧縮レコードファイル２３０を生成するために処理される。
【００４５】
単調に割り当てられた一次キーの場合、レコードは、圧縮レコードファイル内だけなく、１ファイルから次のファイルへも自動的にソートされ、単一インデックス検索（single index search）でレコードにアクセスするためにファイルを統合する必要性を無くす。図２Ｄを参照すると、システム１００は、レコードの一次キーとして到着順に割り当てられた連続整数により特定される一組のレコード２５０を受信する。したがって、レコード２５０は一次キーにより自動的にソートされる。当初の圧縮レコードファイル２５２は、この例ではそれぞれが１００個のレコードを含む圧縮ブロックを含み、インデックスファイル２５４は、圧縮ブロック内の第１のレコードの一次キー値のキーフィールド２５６と、対応する格納場所を特定する場所フィールド２５８とを含む。当初の圧縮レコードファイル２５２が生成された後に到着するレコードはその後、ソートされた順序で一次キー値を自動的に有するので、追加された圧縮レコードファイル２６０および対応するインデックスファイル２６２は、単一インデックス検索に基づき効率的レコードアクセスを可能にするために統合される必要がない。例えば、インデックスファイル２６２はインデックスファイル２５４に単純に追加されることができ、両方のインデックスは、圧縮レコードファイル２５２または２６０のいずれかの中の圧縮ブロックを見つけるために一緒に（例えば、単独のバイナリ検索で）検索されることができる。
【００４６】
集合圧縮レコードファイル２６１は、圧縮レコードファイル２５２の終わりに挿入された可能性もある不完全ブロックをなくすために任意選択的に統合され得る。このような統合では、第１のファイル２５２内の最後の圧縮ブロックだけが圧縮解除される必要があるだろう。また、圧縮解除されたレコードの組をマージする代わりに、レコードの組を単純に連結して、新しい圧縮レコードファイルを形成するために次に再び圧縮される１００個のレコードの組に分割される新しいソートされたレコードの組を形成することができるかもしれない。
【００４７】
連続整数の統合的な一次キー値（consecutive integer synthetic primary key value）を使用することの別の利点は、レコードが一次キー値に基づき分割されようとすれば、キー値には隙間がないので、分割を自動的にバランスさせることができるということである。
【００４８】
レコードを更新するために、および圧縮レコードファイル内に存在し得るレコードの任意の旧バージョンを無効にするために様々な技術のうちの任意のものを使用することができる。ある場合には、レコード（例えば、ログ記録、決済、電話呼）は個々に除去または更新される必要はない。これらの場合、古いレコードは、例えば圧縮レコードファイルの始めから、除去され、廃棄されるまたは所定数の圧縮ブロックのグループにアーカイブされる。ある場合には、圧縮レコードファイル全体を除去することができる。
【００４９】
ある場合には、レコードの１つまたは複数の値は、圧縮ブロック内に格納するために新しい更新レコードを追加することにより更新され、前に受信されたバージョンのレコード（同じ一次キー値を有する）は異なる圧縮ブロック内に残され格納され得る。このとき、複数のバージョンのレコードが存在し得、どれが有効なバージョンのレコードかを判断するためにいくつかの技術が使用される。例えば、任意の圧縮レコードファイル内に現われる最後のバージョン（ごく最近受信された）が有効なバージョンとして暗黙的または明示的に示され得、他のすべてのバージョンは無効である。所与の一次キーを有するレコードの検索は、この場合、出現順に当該一次キーにより特定される最終レコードを発見することを含むことができる。あるいは、レコードは、いかなる旧バージョンのレコードも有効ではないということを示す「レコードを無効にする」と書くことにより、新バージョンのレコードを必ずしも追加することなく、無効にすることができる。
【００５０】
システム１００は、様々な処理により、レコード記憶装置１０６内に格納された圧縮レコードファイルへのアクセスを仲介する。１つまたは複数の圧縮レコードファイル内の圧縮ブロックへのアクセスを仲介するために、様々な同期技術のうちの任意のものを使用することができる。システム１００は、（例えば、データを追加または統合することにより）ファイルを修正するいかなる処理も互いに干渉しないことを保証する。例えば、統合が発生している間に新しいレコードが到着すれば、システム１００は統合処理が終了するまで待つことができる、または圧縮ブロックを生成し、それらを既存の圧縮レコードファイルに追加する前に一時的に格納することができる。圧縮レコードファイルから読み込んだ処理は、完全なファイルの一部をロードすることができ、修正中であり得るすべての不完全な部分を無視することができる。
【００５１】
システム１００は、一次キー以外のレコードの属性に基づきレコードの検索を可能にする追加データを格納する。圧縮レコードファイルの二次インデックスは、二次キーとして指定された属性の値に基づき１つまたは複数の一次キー値を提供する情報を含む。二次キーとして指定された各属性は、対応する二次インデックスに関連付けられることができる。例えば、各二次インデックスは、関連二次キーによりソートされた列を有する表として編成されることができる。各列は、二次キー値と、当該二次キー値を含むレコードの１つまたは複数の一次キー値とを含む。したがって、エージェントが所与の二次キー値を含むすべてのレコードの検索を開始すると、システム１００は当該レコードを含む圧縮ブロックの圧縮レコードファイルのインデックスの検索に使用する一次キーを参照する。二次インデックスは大きい（例えば、レコードの数のオーダ）こともあり、ある場合には、圧縮レコードファイルを格納する記憶媒体内に格納され得る。
【００５２】
ある場合には、二次キーとして指定された属性の値はレコード毎に固有であり得る。そのような場合、当該二次キーと一次キー間に１対１の対応があり、インターフェースモジュール１１２は当該二次キー属性をあたかも一次キーであるかのようにエージェントに提示することができる。
【００５３】
各二次インデックスは、新しい圧縮レコードファイルが集合圧縮レコードファイルに追加されるので、更新されることができる。あるいは、二次キーは、圧縮レコードファイル毎に異なる二次インデックスに関連付けられることができ、二次インデックス群は、圧縮レコードファイルが統合される際に単一の二次インデックスに統合されることができる。
【００５４】
スクリーニングデータ構造（screening data structure）は、「所与の属性値を含むレコードがファイルの圧縮ブロック内に含まれる」可能性を判断するための圧縮レコードファイルに関連付けられることができる。例えば、重複コード化シグネチャ（overlap encoded signature：ＯＥＳ）をスクリーニングデータ構造として使用することで、システム１００は、所与のキー値（一次キーまたは二次キー）を有するレコードが明確に存在しない（「否定的」結果）ということまたは所与のキー値を有するレコードが存在する可能性（「肯定的」結果）を有するかどうかを判断できる。肯定的結果に対して、本システムは、レコード（「確認された肯定的」結果）を取り出すため、またはレコードが存在しない（「誤りの肯定的」結果）ということを判断するためのいずれかのために適切な圧縮ブロックにアクセスする。否定的結果に対して、本システムは、存在しないレコードの圧縮ブロックを圧縮解除および検索する時間を費やす必要無しに否定的結果をエージェントに提供することができる。ＯＥＳのサイズは、どれくらい頻繁に肯定的結果が誤った肯定となるかに影響を与え、一般的には、ＯＥＳサイズが大きければ大きいほど誤りの肯定的結果は少なくなる。所与のＯＥＳサイズに対して、より少ない個別の可能なキー値は通常、より少ない誤った肯定をもたらす。
【００５５】
他のタイプのスクリーニングデータ構造が可能である。一次または二次キーのスクリーニングデータ構造を圧縮レコードファイル毎に設けることができる。あるいは、キーのスクリーニングデータ構造を圧縮ブロック毎に設けることができる。
【００５６】
図３Ａと図３Ｂは、例示的ＯＥＳスクリーニングデータ構造の様々なサイズのキー値（列）と圧縮レコードファイルに表される個別キー値の様々な数（行）とに対する、誤りの肯定的結果を得るための確率値を与える表を示す。ＯＥＳに対して、ＯＥＳのサイズと個別キー値の数に応じて、２つ以上のキー値の存在がＯＥＳの同じ部分に示され得、それらのキー値のうちの１つが、他方が存在すれば誤った肯定を生じる可能性がある。この例示的なＯＥＳのサイズは２１０＝１０２４ビット（図３Ａの表内）から２２８＝２５６メガビット（図３Ｂの表内）まで変わる。個別キー値の数は１００（図３Ａの表内）から１００，０００，０００（図３Ｂの表内）まで変化する。両方の表では、右上の空白セルは０％に対応し、左下の空白のセルは１００％に対応する。誤りの肯定確率が低い（例えば、ほぼ零）セルでは、スクリーニングデータ構造は適切なスクリーニングを行うために必要なものより大きい場合がある。誤りの肯定確率が大きな（例えば、＞５０％）セルでは、スクリーニングデータ構造は適切なスクリーニングを行うには小さすぎる場合がある。この例は、１つのキー値当たり４つのハッシュ符号を使用してＯＥＳを生成する技術に対応する。ＯＥＳスクリーニングデータ構造の他の例は、個別キーの所与の数に対し、誤りの肯定確率の異なる表を生じ得る。
【００５７】
圧縮レコードファイル内に表された個別キー値の数は知られていないこともあるので、システム１００は、ファイルが生成されたレコードの数に基づき圧縮レコードファイルのスクリーニングデータ構造のサイズを選択することができる。サイズを選択する際、偽陽性確率を低減することとスクリーニングデータ構造を格納するために必要なメモリ空間との間にトレードオフがある。このトレードオフにおける１つの要素は不在キー値（absent key value）を検索する尤度である。参照されるキー値のほとんどが圧縮解除済みレコード内に存在する可能性が高ければ、スクリーニングデータ構造は全く必要ではないこともある。キー値が発見されない確率が高ければ、比較的大きなスクリーニングデータ構造の格納スペースを割り当てることでかなりの時間を節約し得る。
【００５８】
圧縮レコードファイルに関連付けられたスクリーニングデータ構造のサイズは、ファイルがレコードの当初のデータベースまたは統合された大きなデータベースに対応するかに依存し得る。比較的小さなスクリーニングデータ構造サイズは、各更新時には概して少数の個別キー値が存在するので、定期的更新期間中に追加される圧縮レコードファイルに使用されることができる。また、圧縮レコードファイルの数は多くの更新後増大するので、小サイズのスクリーニングデータ構造は必要な格納スペースを低減することができる。スクリーニングデータ構造のサイズは、更新時におけるレコードおよび／または個別キー値の予測数と予測更新数とに基づくことができる。例えば、更新ファイルが２４時間の期間にわたって５分毎に追加されれば、その日の終わりには２８８個の圧縮レコードファイルが存在することになる。少なくとも１つの誤りの肯定的結果の確率は、図３Ａと図３Ｂの表から適切値の２８８倍になる（相異なる更新の結果が独立であると仮定する）。統合後、個別キー値の数は著しく増加し得るので、統合された圧縮レコードファイルにはより大きなスクリーニングデータ構造が適切であり得る。
【００５９】
圧縮レコードファイルは、一次キーのおよび二次キー毎の、またはキーのあるサブセットのスクリーニングデータ構造を有することができる。例えば、システム１００は、一次キーの、およびほとんどの場合レコードの検索時に使用されると予測されるそれらの二次キーだけのスクリーニングデータ構造を提供し得る。
【００６０】
図４Ａは、所与の一次キー値を有する１つまたは複数のレコードの検索のための手順４００のフローチャートを示す。手順４００は、第１の圧縮レコードファイルに関連付けられたスクリーニングデータ構造があるかどうかを判断する（４０２）。そうならば、手順４００は、肯定的または否定的のいずれかの結果を得るためにスクリーニングデータ構造を処理する（４０４）。所与の一次キー値がスクリーニングに合格しなければ（否定的結果）、手順４００は、次の圧縮レコードファイルがあるかどうかをチェックし（４０６）、存在すれば、当該ファイルについて繰り返す。所与の一次キー値がスクリーニングに合格すれば（肯定的結果）、手順４００は、所与の一次キー値を有するレコードを含み得るブロックのインデックスを検索する（４０８）。圧縮レコードファイルに関連付けられたスクリーニングデータ構造が無ければ、手順４００はスクリーニングを行うことなくインデックスを検索する（４０８）。
【００６１】
インデックスの検索（４０８）後、所与の一次キー値を含むキー値の範囲に関連付けられた圧縮ブロックが発見されれば（４１０）、手順４００は、インデックスエントリにより特定された場所のブロックを圧縮解除し（４１２）、所与の一次キー値を有する１つまたは複数のレコードのその結果のレコードを検索する（４１４）。次に、手順は次の圧縮レコードファイルがあるかどうかをチェックし（４１６）、存在すれば当該ファイルについて繰り返す。圧縮ブロックが発見されなければ（例えば、所与の一次キー値が第１のブロック内の最小キー値より小さいまたは最後のブロック内の最大キー値より大きければ）、手順４００は次の圧縮レコードファイルがあるかどうかをチェックし（４１６）、存在すれば当該ファイルについて繰り返す。
【００６２】
図４Ｂは、所与の二次キー値を有する１つまたは複数のレコードの検索の手順４５０のフローチャートを示す。手順４５０は、第１の圧縮レコードファイルに関連付けられたスクリーニングデータ構造があるかどうかを判断する（４５２）。そうならば、手順４５０は、肯定的または否定的のいずれかの結果を得るためにスクリーニングデータ構造を処理する（４５４）。所与の二次キー値がスクリーニングに合格しなければ（否定的結果）、手順４５０は次の圧縮レコードファイルがあるかどうかをチェックし（４５６）、存在すれば、当該ファイルについて繰り返す。所与の二次キー値がスクリーニングに合格すれば（肯定的結果）、手順４５０は、所与の二次キーを含むレコードに対応する一次キーを参照する（４５８）。圧縮レコードファイルに関連付けられたスクリーニングデータ構造が無ければ、手順４５０は、スクリーニングを行うことなく一次キーを参照する（４５８）。
【００６３】
発見された一次キーのそれぞれに対して、手順４５０は、所与の一次キー値を有するレコードを含み得るブロックのインデックスを検索する（４６０）。インデックスの検索（４６０）後、所与の一次キー値を含むキー値の範囲に関連付けられた圧縮ブロックが発見されれば（４６２）、手順４５０は、インデックスエントリにより特定された場所のブロックを圧縮解除し（４６４）、所与の一次キー値を有する１つまたは複数のレコードの結果レコードを検索する（４６６）。次に、手順は次の圧縮レコードファイルがあるかどうかをチェックし（４６８）、存在すれば当該ファイルについて繰り返す。圧縮ブロックが発見されなければ、手順４５０は次の圧縮レコードファイルがあるかどうかをチェックし（４６８）、存在すれば当該ファイルについて繰り返す。
【００６４】
所与の一次または二次キーにより発見された複数のレコードは、手順４００または手順４５０により出現順に戻すことができる、または場合によっては最後のバージョンのレコードだけが戻される。
【００６５】
ファイル管理モジュール１０４はまた、追加可能ルックアップファイルを使用することによりレコードの格納とアクセスを管理する。追加可能ルックアップファイルを使用する１つの例では、システム１００は大きな一次データセット（例えば、数百テラバイトの一次データを含む）を管理する。この一次データセットは通常、１つの圧縮レコードファイルまたは一連の複数の圧縮レコードファイル内に格納されることになる（集合圧縮レコードファイルに連結される可能性がある）。しかし、データが到着した直後（例えば、１分以内）に可視である必要があれば、追加可能ルックアップファイルにより圧縮レコードファイルを補足することが有用であり得る。追加可能ルックアップファイルは、新しいデータが到着した時間とそのデータが様々な問い合わせ処理に利用可能となる時間との間の待ち時間を低減することができる。新しいデータは例えば、データをファイルへ能動的に書き込む別の処理から生じる可能性がある。システム１００は、不完全である場合もある部分的追加可能ルックアップファイルへのアクセスを管理することができる。いくつかのシステムでは、問い合わせ処理が部分的ファイルに遭遇すれば、プログラムエラーが結果として生じるだろう。このプログラムエラーを避けるために、これらのシステムのいくつかは、ファイルが問い合わせられるたびに、ファイルに関連付けられたインデックスを再ロードするだろう。すべての問い合わせ上にインデックスを再ロードすることは場合によっては非効率である可能性があり、システム資源のかなりの量を消費し得る。
【００６６】
通常、追加可能ルックアップファイルは、ファイルの終わりに部分的レコードが追加されることに寛容な未圧縮データファイルである。追加可能ルックアップファイルは不完全レコードを認識することができ、問い合わせられたファイルが不完全レコードを含む場合でも問い合わせ要求を処理することができる。追加可能ルックアップファイルは圧縮レコードファイル用の上に述べたようなタイプのインデックスファイルを有するのではなく、むしろ、追加可能ルックアップファイルは、比較的速い作業メモリ（例えば、ダイナミックランダムアクセスメモリなどの揮発性記憶装置媒体）内に格納されたデータ構造内の各レコードの場所をマッピングする「動的インデックス」を有する。例えば、これらの動的インデックスは、ハッシュ表、バイナリーツリー、ｂ−ツリー、または別のタイプの連想型データ構造であり得る。
【００６７】
図５と図６Ａ〜６Ｂは、追加可能ルックアップファイルを使用することによりレコードを管理する例を示す。図５は、追加可能ルックアップファイルが問い合わせられる処理の例である。追加可能ルックアップファイルの操作に関する処理フロー５００は、負荷処理５０２と問い合わせ処理５０４を含む。ファイルがロードされた（５０６）後（ファイルが問い合わせられると）、ファイルの長さが判断される（５０８）。ファイルの長さが判断された（５０８）後、判断された長さは作業メモリ内など記憶場所に格納される（５１０）。
【００６８】
次に、システムはファイル内の最後の完全なレコードの終わりを表す場所である「エンドポイント」を判断する（５１２）。新しいデータがファイルに書き込まれていないことなどがある場合には、エンドポイントは単純にファイルの終わりを表すだろう。エンドポイントはまた、新しいデータの第１のセグメントの直前の場所を表し得る（図６を参照）。エンドポイントが判断された（５１２）後、エンドポイントは主メモリ内など記憶場所に格納される（５１４）。
【００６９】
問い合わせ処理（５０４）中、システム１００は、問い合わせを処理すべきか（５２２）または問い合わせられたファイルに関連付けられた連想型データ構造を更新すべきか（５１８）を判断する。この判断を行うために、システムはファイルの現在長と前に判断されメモリ内に格納されたファイルの長さとを比較する（５１６）。この判断は、多くのやり方で行うことができる。例えば、システムはファイル「メタデータ」、ファイル「ヘッダ」を調べることができる、またはファイルの改行文字を検索することができる。ファイルの長さが前に格納されたファイルの長さを越えなければ、いかなる新しいデータもデータファイルの終わりに追加されておらず、問い合わせは処理される（５２２）。ファイルの現在長が前に格納されたファイルの長さを越えれば、前に格納されたエンドポイントで始まる連想型データ構造が更新される（５１８）。このようにして、連想型データ構造は、それを全く再ロードまたは再構築する必要無く更新することができる。その代りに、メモリ内に既にロードされたデータはロードされたままであり、前に格納されたエンドポイントで始まる新しいデータが追加される。問い合わせを処理する前に、ファイルの長さとエンドポイントが更新される（５２０）。エラーチェックなど他の工程がこの処理において行われる可能性がある。例えば、ファイルの現在長が前に格納されたファイルの長さより短いとシステムが判断すれば、エラーフラグを立てることができる。
【００７０】
図６Ａと図６Ｂは、図５の工程５１２により判断されるようなファイル内のエンドポイントの場所の例である。図６Ａにおいて、追加可能ルックアップファイル６００は完全なレコード６０２と不完全なレコード６０４とを含む。この場合、エンドポイント６０６は、追加可能ルックアップファイル６００内の最後の完全なレコードの終わりを表す場所であり、不完全なレコード６０４の始まりの直前にある。
【００７１】
図６Ｂの例では、追加可能ルックアップファイル６５０は全く完全なレコード６５２からなる。この場合、エンドポイント６５４は再び、追加可能ルックアップファイル６５０内の最後の完全なレコードの終わりを表すが、エンドポイント６５４はまた、ファイルの終わりを表す。
【００７２】
データは、追加可能ルックアップファイルに連続的に追加され得、次に追加可能ルックアップファイルは連続的に更新される。その結果、追加可能ルックアップファイルはますますサイズが大きくなり、追加可能ルックアップファイルをロードするためにかかる時間はそれに応じて増加する。追加可能ルックアップファイルは、追加可能ルックアップファイルがあまりにも大きくなり望ましい時間内にロードできなくなるのを避けるために他の形式の動的ロード可能なインデックスファイルと組み合わせられ得る。
【００７３】
いくつかのアプリケーションでは、問い合わせ可能なデータ構造内にロードされるデータの連続ストリームは高速で到着し得、到着した後すぐにデータにアクセスすることが望ましい場合もある。データが到着すると、データは二重プロセス（dual process）により処理される。最初に、データは複製され、追加可能ルックアップファイルと第２のファイルまたは「バッファ」との両方に同時に追加される（直ちに可視となり、ファイルシステムによりアクセス可能となるように）。データは、所定の条件が満足されるまで追加可能ルックアップファイルとバッファの両方の中で蓄積し続ける。所定の条件は多くの判定基準であり得る。例えば、所定の判定基準は、時間の長さ、ファイルサイズ、データの量、またはデータ内のレコードの数であり得る。
【００７４】
所定の条件が満足された後、バッファ内に蓄積されたデータブロックは圧縮レコードファイルに追加され長期保存される。データが圧縮レコードファイルに追加された後、新しい追加可能ルックアップファイルが生成され、データストリームからデータを収集し始める。古い追加可能ルックアップファイルは終了され、圧縮レコードファイルが対応データのすべてを含んだ後消去される。
【００７５】
データがバッファと追加可能ルックアップファイルの両方により受信されている間、バッファ内のデータをソートすることができる。データをソートすることは相当な時間およびシステム資源を消費するので、データがより迅速に圧縮レコードファイルへ転送されるように、ソート処理をできるだけ早期に開始することが有利である。
【００７６】
あるいは、追加可能ルックアップファイルをバッファとして使用することができる。この実施形態では、データは、所定の条件が満足されるまで追加可能ルックアップファイル内に蓄積される。次に、追加可能ルックアップファイルのコンテンツが圧縮レコードファイルに追加され、一方同時に、古い追加可能ルックアップファイルは終了され、新しい追加可能ルックアップファイルが生成されデータストリームからデータを収集し始める。再び、古い追加可能ルックアップファイルは、圧縮レコードファイルが対応データのすべてを含んだ後、消去される。
【００７７】
この処理の各サイクル中、データを圧縮レコードファイルへ同時に追加し、追加可能ルックアップファイル内のデータをすべて消去することが望ましいだろう。しかし、２つの更新は競合状態を引き起こし得るので、古い追加可能ルックアップファイルは消去されたが圧縮レコードファイルはそのデータによりまだ更新されてなかったという大きな時間帯があり得る。これにより、データの一時的喪失を生じるだろう。これを防ぐために、古い追加可能ルックアップファイルをこの処理の追加のサイクルの間維持することができる。インデックス付けおよび検索モジュール１０８は、追加可能ルックアップファイルと圧縮レコードファイルの両方内に重複データが存在し得る状態を検出するように構成され、インデックス付けおよび検索モジュール１０８は問い合わせがこの状態中に行われれば重複データをフィルタで除去する。
【００７８】
あるいは、ファイル管理モジュール１０４は、データバッファが圧縮ルックアップファイルに書かれた後または追加可能ルックアップファイルのコンテンツが圧縮ルックアップファイルに追加された後のいずれかに追加可能ルックアップファイルの退去（retirement）を調整するために、例えばステータス情報ファイル１０７内にステータス情報を維持し得る。ステータス情報ファイル１０７は、現在アクティブなレコード関連データ構造を特定する。例えば、ステータス情報ファイル１０７は、圧縮データファイルのすべてと、圧縮データファイルが、現在アクティブな追加可能ルックアップファイルのすべてと共に含むブロックの数とを特定する。インデックス付けおよび検索モジュール１０８は、任意の追加可能ルックアップファイル、圧縮データファイル、およびステータス情報ファイル内に現われない圧縮データファイル内のブロックを無視する。以下は、新しい追加可能ルックアップファイルを生成するときにファイル管理モジュール１０４により遵守されるプロトコルの例である。ファイル管理モジュール１０４は新しいデータを圧縮データファイルへ追加し、新しい追加可能ルックアップファイルを生成する；ファイル管理モジュール１０４は、ステータス情報ファイルがインデックス付けおよび検索モジュール１０８によりアクセスされるのを防ぐためにステータス情報ファイルをロックする；ファイル管理モジュールは、圧縮データファイルへの新しいデータの追加、古い追加可能ルックアップファイルの除去、および新しい追加可能ルックアップファイルの生成を反映するためにステータス情報ファイルを更新する；ファイル管理モジュールはステータス情報ファイルをロック解除し、ステータス情報ファイルがインデックス付けおよび検索モジュール１０８により再度アクセスできるようにする；ファイル管理モジュール１０４は古い追加可能ルックアップファイルを除去する。
【００７９】
インデックス付けおよび検索モジュール１０８は、以下の例示的なプロトコルに従う。インデックス付けおよび検索モジュール１０８は、ファイル管理モジュール１０４がステータス情報ファイルを更新するのを防ぐためにステータス情報ファイルをロックする；インデックス付けおよび検索モジュール１０８は、ステータス情報ファイル内に特定された追加可能ルックアップファイルと圧縮データファイルとに従って問い合わせを行う；インデックス付けおよび検索モジュール１０８は、ステータス情報ファイルをロック解除して、ファイル管理モジュール１０４がステータス情報ファイルを更新するのをもう一度許可する。
【００８０】
ステータス情報ファイル１０７は、ディスク上またはメモリ内のいずれかに格納され得る。このプロトコルは、検索モジュールが、古い追加可能ルックアップファイルからのデータの取り込み前に古い追加可能ルックアップファイルと圧縮データファイル、または新しい追加可能ルックアップファイルと更新された圧縮データファイルのいずれかを見ることを保証する。
【００８１】
新しい追加可能ルックアップファイルと古い追加可能ルックアップファイルの両方が同時に存在する場合に問い合わせが行われると、一実施形態では、システムはどの追加可能ルックアップファイルが現在アクティブか(例えば、新しい追加可能ルックアップファイルは生成後のある遅延量までアクティブとなり得ないので、新しい追加可能ルックアップファイルまたは古い追加可能ルックアップファイルのいずれかがアクティブであり得るか)を調べるためにディレクトリの中を見る。あるいは、システムが問い合わせを処理する場合、システムは最初に最新の追加可能ルックアップファイル、次に古い追加可能ルックアップファイルの中を見る。問い合わせられたデータが依然として見つけられなければ、システムは圧縮レコードファイルの中を見る。
【００８２】
図７において、システム１００により行われる手順７００は、ファイルの長さを判断し（７０２）、ファイルの長さを第１の記憶場所内に格納する（７０４）。手順７００は、ファイル内の最後の完全なレコードのエンドポイントを判断し（７０６）、エンドポイントを第２の記憶場所に格納する（７０８）。本手順は、ファイルの第１の記憶場所に格納されたファイルの長さと現在長とを比較し（７１０）、ファイルの現在長が第１の記憶場所に格納されたファイルの長さを越えれば、エンドポイントで始まるファイルに関連付けられたデータ構造を更新する（７１２）。
【００８３】
図８において、システム１００により同時に行われる手順８００は、データストリームからのデータを第１のファイルとバッファに追加し（８０２）、所定の条件が満たされた後、バッファに関連付けられたデータを圧縮ファイルへ転送する（８０４）。手順８００は、バッファからのデータが圧縮ファイルへ転送された後、データストリームからデータを受信するために第２のファイルを生成する（８０６）。
【００８４】
図９に、インターフェース１１２、レコード処理モジュール１０２、ファイル管理モジュール１０４、レコード格納モジュール１０６、インデックス付けおよび検索モジュール１０８、およびインデックス格納モジュール１１０を含むレコード格納および取り出しシステム９０２を含むシステム９００を示す。いくつかの例では、レコード格納モジュール１０６は、上述のものなど１つまたは複数の圧縮技術を使用することにより多くのレコードを格納する。例えば、レコード（例えば、レコードのそれぞれに関連付けられたタイムスタンプに基づき同じ発生日付に関連付けられたレコード）はレコードの数値属性に従ってグループ化されることができる。上述のように、レコードの各グループは、レコードを格納する１つまたは複数のデータファイル（例えば、圧縮レコード）と、データファイル内の各レコードの場所とレコードの属性（例えば、レコードの一次または二次キーを表す属性）に対応し得る１つまたは複数のインデックスキーの両方を格納するインデックスと、の両方に関連付けられ得る。所与のレコードのグループ毎に、データファイルとそのデータファイルに関連付けられた１つまたは複数のインデックスは個別に格納され得る。例えば、１つまたは複数のインデックスはインデックス格納モジュール１１０内に格納され得、データファイルはレコード格納モジュール１０６内に格納され得る。
【００８５】
インデックス付けおよび検索モジュール１０８内の問い合わせ処理エンジン９１０は、検索問い合わせ（例えば、インターフェース１１２を介しユーザから受信された問い合わせ）を処理するように構成される。いくつかの例では、問い合わせ処理エンジン９１０により受信された問い合わせ内に特定される１つまたは複数のレコードを取り出すために、問い合わせを満足するレコードを含む可能性のある任意のデータファイルを圧縮解除し、そのレコードをメモリ内にロードさせ、そのレコードを問い合わせの仕様と照合させることができるであろう。合致レコードが特定され、さらに処理され（例えば、インターフェース１１２へ）出力され得、一方問い合わせの仕様に合致しないレコードはメモリから単純に除去され得る。上記例を使用することにより、圧縮レコードが特定の発生日に対応するデータファイル内に格納されると、レコード格納および取り出しシステム９０２は１日の１時間に関連付けられたすべてのレコード（例えば、２０１１年６月１日の１：００ＡＭ〜２：００ＡＭの時間に関連付けられたすべてのレコード）の取り出しを要求する問い合わせを受信し得る。この単純化した例では、２０１１年６月１日の日付に関連付けられたデータファイルだけが検索されるだろう。しかし、全データファイルが圧縮解除され、メモリ内にロードされ、１：００ＡＭ〜２：００ＡＭの期間の問い合わせ仕様と照合された後、データファイル内の多くのレコードがこの制約に合致しないと判断され得る。その結果、圧縮解除、ローディング、および非合致レコードを検索することは無駄な操作と見なされ得る。同じ例示データファイル構造を使用すると、例えば、問い合わせが、全一年間の同じ期間に関連付けられたすべてのレコードの取り出しを要求すれば、たとえ毎日の単一時間内のレコードだけが問い合わせ用語に関係があっても３６５個のデータファイルが圧縮解除され、ロードされ、検索されるので、問題は悪化する可能性がある。
【００８６】
いくつかの例では、システム９００は、レコード格納モジュール１０６内に格納されたレコードが、上述の技術より高精度で見つけられ、特定され、取り出されるようにし得る。例えば、インデックス付けおよび検索モジュール１０８は、所与のレコードに関連付けられた数値属性より範囲は粗いが全データファイルに関連付けられた数値属性値のスパンより範囲が細かい数値範囲（例えば、一定期間）との関連性を含むエントリを含むインデックスを構築（または含むために既存のインデックスを更新）し得る。上記例を再び参照すると、レコードはそれぞれタイムスタンプを含み得る。例えば、レコードが外線電話呼を表す場合、レコードは、どの電話番号にかけられたか、どの電話番号が発呼したかのみならず、いつ呼が受信されたかを示すタイムスタンプと、他の情報とを含み得る。いくつかの例では、タイムスタンプは、時間、分、および秒の形式（例えば、フォーマットＨＨ：ＭＭ：ＳＳ）であり得る。したがって、所与のデータファイルは、１日（例えば、２０１１年６月１日）に含まれるタイムスタンプに関連付けられたレコードを含み得、そのデータファイルに関連付けられたインデックスは、レコードの１つまたは複数の属性（例えば、発呼さられた電話番号）だけでなくデータファイル内のそれらのレコードのそれぞれの場所を与えるエントリを含み得る。インデックス内のエントリはそれぞれ、また、対応するレコードのタイムスタンプが含まれる数値範囲を記載する情報（数値属性が時間である場合「タイムカンタム(time quantum)」と呼ばれることがある）を含み得る。
【００８７】
例えばタイムスタンプを含むレコードの数値範囲を計算するために、インデックス付けおよび検索モジュール１０８に付随する数値範囲処理モジュール９１２は、数値範囲を提供するためにタイムスタンプを処理し得る。数値範囲は、所望の数値範囲のサイズ（例えば、数値属性が時間である場合は期間）を規定する数値グラニュール（numerical granule）９１３に部分的に基づく。例えば、数値グラニュール９１３は、「タイムスタンプ毎に提供される数値範囲は一日の１０分間を包含する」と規定し得る。例えば、レコードが１：００：００ＡＭのタイムスタンプを含み、数値グラニュール９１３が１０分（６００秒）の値を規定すれば、数値範囲を計算することができる。いくつかの例では、タイムスタンプ（１：００：００ＡＭ）は、計算の一部として様々な単位に変換されることができる。例えば、特定日の１：００：００ＡＭは、前日の真夜中から経過した多くの時間単位（例えば、１時間または３６００秒）により表すことができる。
【００８８】
いくつかの例では、数値範囲は、タイムスタンプを時間グラニュール（例えば、秒）に関連付けられた同じ時間単位に変換することにより計算することができる。次に、数値範囲は、例えば時間グラニュール（６００秒）で変換されたタイムスタンプ（３６００秒）を割ることにより次のように決定することができる。
【数１】
2014524090.tif 000003
したがって、上記例については、数値キー処理モジュール９１２は、数値グラニュール９１３に基づき、１：００：００ＡＭタイムスタンプを有するレコードと関連する数値範囲を判断し得る。いくつかの例では、数値キー処理モジュール９１２は、除算から生じる商だけを使用し、数値範囲計算から整数値にならない剰余を四捨五入または落とし得る。
【００８９】
数値範囲が所与のレコードについて数値キー処理モジュール９１２により計算された後、インデックス付けおよび検索モジュール１０８は、数値範囲９１６を含むエントリ（またはエントリに対する更新）９１４をインデックス記憶装置１１０へ提供することができる。次に、インデックス記憶装置１１０は、１つまたは複数のレコードアドレス９１８により表されたレコードを格納するデータファイルに関連付けられた１つまたは複数のインデックス内にエントリ９１４を格納し得る。エントリ９１４はまた、１つまたは複数のレコードアドレス９１８だけでなく第１のキー９０６も（例えば、エントリが新しいエントリであれば）含み得る。いくつかの例では、１つまたは複数のレコードアドレス９１８は、第１のキー９０６と数値範囲９１６とに関連付けられたレコードを含む１つまたは複数の場所（例えば、レコード格納モジュール１０６内に格納されたデータファイル内）を特定する。
【００９０】
上述のように、エントリ９１４は、１つまたは複数のレコードアドレス９１８を含み得る。例えば、３つのレコード（それぞれデータファイル内に一意的に格納されている）が数値範囲９１６（例えば、上に計算されたような数値範囲６）だけでなく第１のキー９０６（例えば、通常の電話番号）にも関連付けられていれば、レコードアドレス９１８（例えば、ポインタであり得る）は、エントリ９１４内に集められ一緒に格納されることができる。エントリ９１４など単一エントリ内に複数のレコードアドレスを一緒に格納することで、インデックスがより少ないエントリを格納できるようにすることにより格納スペースを保存することができる。
【００９１】
図１０は、４つのエントリ、すなわち第１のエントリ１００２、第２のエントリ１００３、第３のエントリ１００４、および第４のエントリ１００５を含む例示的インデックス１０００を示す。エントリ１００２〜１００５のそれぞれは、第１列１００６により表される第１のキー（「値キー」と呼ばれる）と第２の列１００８により表される第２のキー（「範囲キー」と呼ばれる）とを含む。この例では、値キーは電話番号であり、範囲キーは上述のタイプの数値範囲である。すなわち、この例では、各エントリ１００２〜１００５は、発呼された電話番号とこの呼の時間に関連付けられた数値範囲とのレコードを表す。インデックス１０００は、最初に値キー１００６によりソートされ、次に範囲キー１００８によりソートされる。あるいは、他の例では、値キーは範囲キーを組み込むために修正されることができる（例えば、範囲キーの値と値キーの値とを連結することにより）。
【００９２】
エントリ１００３は、「電話番号１」の値キーの値と範囲キーの値２（商２に対応する数値範囲を表す）とを含む。この場合、２の数値範囲は、１つまたは複数のレコードに関連付けられたタイムスタンプと数値グラニュール（例えば、数値グラニュール９１３）とを使用することにより上に示されたやり方で計算されるタイムカンタムを表す。
【００９３】
エントリ１００３はまた、２つ以上のレコードアドレスに関連付けられたエントリの例である。例えば、エントリ１００３は３つのアドレス（アドレス１  １０１２、アドレス４  １０１３、アドレス５  １０１４）に関連付けられる。アドレス１０１２〜１０１４点のそれぞれは、レコード格納モジュール１０６内に格納された１つまたは複数のデータファイル１０１０内の場所を指す。時間カンタムなどの数値範囲をインデックス内のキーとして格納することで、単一エントリ内のレコードアドレスの集合化またはグループ化を容易にする。例えば、タイムスタンプは３２ビットの文字ストリングにより表され得るが、タイムカンタムなどの数値範囲は、タイムカンタムがタイムスタンプの分解能に応じて時間、分、秒、および１秒の何分の一の組合せの代わりに単一整数により表され得るので８ビット列により表され得る。さらに、時間カンタムなどの数値範囲が例えばタイムスタンプより粗いグラニュティを有することができるので、所与の数値範囲は複数のレコードを包含する可能性が高い。例えば、数値範囲が２時間の期間を表す場合、タイムスタンプは数値範囲より高精度である可能性がある（およびしたがって一意的である可能性か高い）のでより多くのレコードが共通のタイムスタンプより共通の２時間の期間に関連付けられる可能性が高い。アドレス１０１２〜１０１４はまた、単一エントリ下にそれらを集める必要が無いのでインデックス１０００内の対応エントリにより表され得る。エントリ１００２〜１００５のそれぞれに関連付けられたレコードアドレスは、例えば、インデックス１０００に関連付けられた１つまたは複数の追加の列内に格納され得、各列はエントリに関連付けられた１つまたは複数のレコードアドレスを含むことができる。
【００９４】
これらの技術を使用することによりレコードを格納しインデックス付けすることで、判定基準を満足するレコードの問い合わせがより効率的に処理されるようにする。例えば、再び図９を参照すると、インデックス付けおよび検索モジュール１０８はインターフェース１１２から問い合わせを受信し得る。上記例と同様に、問い合わせは、１日の１時間に関連付けられたすべてのレコード（例えば、２０１１年６月１日の１：００ＡＭ〜２：００ＡＭの時間に関連付けられたすべてのレコード）の取り出しを要求し得る。問い合わせは、照合対象の第１の属性（値キーに対応する属性）の特定の値と、照合対象の第２の属性の値（範囲キーに対応する属性）の範囲とを特定する形式であり得る。この例では、第１の属性の値は発呼電話番号を表し得、第２の属性の値域は最小時間により表される期間（１：００ＡＭ〜最大時間２：００ＡＭ）を表し得る。
【００９５】
レコードがそれぞれの日付によりデータファイル内でグループ化される（例えば、各データファイルは１日からのレコードを格納する）と仮定すると、２０１１年６月１日の日付に関連付けられたデータファイルは問い合わせを満たすレコード（問い合わせを満たし得ない多くのレコードだけでなく）をすべて含むだろう。しかし、メモリ内に全データファイルをロードする代わりに、インデックス付けおよび検索モジュール１０８の問い合わせ処理モジュール９１０は、期間を、時間カンタムなどの数値範囲に対し照合することができる形態に変換し得る。例えば、期間を表す最小時間と最大時間の両方を上述のやり方でそれぞれの数値範囲に変換することができる。６００秒の同じ数値グラニュール９１３が使用されると仮定する例示的変換を以下に示す。
【数２】
2014524090.tif 000004
【００９６】
したがって、問い合わせにより規定された１：００ＡＭ〜２：００ＡＭの期間を、対応する数値範囲６と１２にそれぞれ変換することができる。次に、修正された問い合わせは、インデックス（例えば、インデックス１０００）が第１の属性（例えば、問い合わせ内に規定された電話番号）に対応する値キーと第２の属性に対応する範囲キー（例えば、問い合わせ内に規定された期間から生成された数値範囲６〜１２）とに基づき検索されることができるように、インデックス記憶装置１１０内のレコードに対し行われ得る。所与のデータファイルに関連付けられたインデックスは、それぞれの時間カンタムに対応する範囲キーを含むので、インデックス付けおよび検索モジュール１０８は、「所与のデータファイル内のレコードのサブセットだけが６と１２の間のタイムカンタムに関連付けられる」ということを判断することができる（我々は用語「間」を、例えばいずれかの極値に等しい値を含むように広義に使用する）。その結果、全データファイルは、メモリ内にロードされ、圧縮解除され（データファイルが圧縮データファイルであれば）、検索される必要が無く、その代りに、６から１２までの時間カンタムに関連付けられているインデックス内に特定されたレコードだけが圧縮解除され（データファイルが圧縮データファイルであれば）、メモリ内にロードされ、検索される。各タイムカンタムは、照合用タイムカンタム（matching time quantum）の範囲に入るが元の問い合わせ内に規定された期間の外のレコードを含み得るので、問い合わせを満足するレコードが圧縮解除されたおよび／またはメモリ内にロードされた後、インデックス付けおよび検索モジュール１０８は、元の問い合わせを満足しないすべてのレコードを特定し排除するために、ロードされたレコードを元の問い合わせに対し照合し得る。照合が行われた後は残りのレコードはインターフェース１１２から受信された問い合わせを満足するはずであり、結果として生じたレコード（またはそれらのレコードのリスト）を例えばインターフェース１１２を介しユーザへ戻すことができる。
【００９７】
図１１に、インデックス内に数値範囲を格納する処理１１００を示す。処理１１００は、新しいインデックスを生成する、既存のインデックス内に新しいエントリを生成する、または既存のインデックス内のエントリを更新するために使用することができる。
【００９８】
データ構造内に格納されたレコードに関連付けられた数値属性を受信する（１１０２）。例えば、データファイルはタイムスタンプなどの関連数値属性を有するレコードを含み得、インデックス付けおよび検索モジュール１０８は、タイムスタンプを抽出するために、データファイルおよび／またはデータファイルに関連付けられたインデックスにアクセスし得る。タイムスタンプは、数値属性の単に一例であり、また、数値順（例えば、１つまたは複数の項目の線形順）を含み得る。
【００９９】
数値属性を含む数値範囲を生成する（１１０４）。例えば、数値属性がタイムスタンプであれば、上述のやり方で数値範囲を計算することができる。例えば、所定の時点（例えば、所与の日の真夜中）からのタイムスタンプにより表される時間を分離する時間単位で表される値は、タイムスタンプを数値範囲を判断するために使用することができる時間単位の量に変換するために判断されることができる。次に、時間単位は、数値範囲を提供するために数値グラニュール（例えば、時間グラニュール）により除されることができる。いくつかの例では、時間グラニュールなどの数値グラニュールはユーザにより規定され、任意のサイズ（例えば、１０分または６か月）であり得る。
【０１００】
データ構造内のレコードの場所を特定するとともに値インデックスキーと範囲インデックスキーとを含むエントリは、データ構造に関連付けられたインデックス内に格納され、範囲インデックスキーの値は数値範囲に関連付けられる（１１０６）。例えば、値キーと範囲キーの両方を含むエントリをインデックス（例えば、図１０のインデックス１０００）内に提供することができる。いくつかの例では、範囲キーに関連付けられた数値範囲はタイムカンタムである。
【０１０１】
システムのモジュールとシステムにより行われる手順とを含む上述のレコード格納および取り出し手法は、コンピュータ上で実行するためのソフトウェアを使用して実施することができる。例えば、ソフトウェアは、それぞれが少なくとも１つのプロセッサ、少なくとも１つのデータ記憶システム（揮発性および不揮発性メモリおよび／または記憶素子を含む）、少なくとも１つの入力装置またはポート、および少なくとも１つの出力装置またはポートを含む１つまたは複数のプログラムされたまたはプログラム可能なコンピュータシステム（分散型、クライアント／サーバーまたはグリッドなどの様々なアーキテクチャであってよい）上で実行する１つまたは複数のコンピュータプログラム内の手順を形成する。ソフトウェアは、例えば計算グラフの設計と構成に関する他のサービスを提供するより大きなプログラムの１つまたは複数のモジュールを形成し得る。グラフのノードと要素は、コンピュータ可読媒体内、またはデータレポジトリに格納されたデータモデルに準拠する他の編成データ内に格納されたデータ構造として実施することができる。
【０１０２】
ソフトウェアは、汎用または専用プログラム可能コンピュータにより読み出し可能なＣＤ−ＲＯＭなどの記憶媒体上に提供され得る、またはネットワークの通信媒体上で、ソフトウェアが実行されるコンピュータに配送され得る（伝播信号内に符号化され得る）。機能のすべては、専用コンピュータ上で、またはコプロセサなどの専用ハードウェアを使用することより、実行され得る。ソフトウェアは、ソフトウェアにより規定された計算の様々な部分が様々なコンピュータにより実行される分散的やり方で実施され得る。このような各コンピュータプログラムは、記憶媒体または装置が本明細書に記載の手順を実行するためにコンピュータシステムにより読み取られるとコンピュータを構成し動作させる汎用または専用のプログラム可能コンピュータにより読み出し可能な記憶媒体または装置（例えば、固体メモリまたは媒体、あるいは磁気または光学的媒体）上に格納されるあるいはそれにダウンロードされることが好ましい。本発明のシステムはまた、コンピュータプログラムにより構成されるコンピュータ可読記憶媒体として実現されると考えられ得る。そのように構成された記憶媒体は、コンピュータシステムを、本明細書に記載の機能を実行するように特定および所定のやり方で動作させる。
【０１０３】
本発明の多くの実施形態が説明された。それにもかかわらず、本発明の精神及び範囲を逸脱すること無く他の様々な変更が可能であることが理解されるであろう。例えば、上に記載された工程のいくつかは、順序に無関係であってもよく、したがって記載されたものと異なる順序で実行することができる。
【０１０４】
これまでの説明は、例証することを意図していること、そして添付の請求の範囲により定義される本発明の範囲を限定しないように意図されていることとを理解すべきである。例えば、上に記載された多くの機能工程は、全体処理に実質的に影響を与えることなく異なる順序で実行され得る。他の実施形態は以下の特許請求の範囲に含まれる。
【図１】
2014524090.tif 000005
【図２Ａ】
2014524090.tif 000006
【図２Ｂ】
2014524090.tif 000007
【図２Ｃ】
2014524090.tif 000008
【図２Ｄ】
2014524090.tif 000009
【図３】
2014524090.tif 000010
【図４Ａ】
2014524090.tif 000011
【図４Ｂ】
2014524090.tif 000012
【図５】
2014524090.tif 000013
【図６】
2014524090.tif 000014
【図７】
2014524090.tif 000015
【図８】
2014524090.tif 000016
【図９】
2014524090.tif 000017
【図１０】
2014524090.tif 000018
【図１１】
2014524090.tif 000019
【国際調査報告】
2014524090.tif 000020
2014524090.tif 000021