(57)【特許請求の範囲】
【請求項１】
迅速なデータ解析のための方法であって、
クエリエンジン（１４０）において、クエリを受け取り且つ読み取るステップであって、前記クエリを読み取るステップが、文字列変換器を用いて整数に前記クエリの文字列を変換することを具え、前記クエリを読み取るステップが、さらに、前記クエリに関するデータを含む事象データベース（１１０）のデータ片の第１のセットを識別することを具える、ステップと、
前記クエリエンジン（１４０）において、前記事象データベース（１１０）のデータ片の第１のセットから第１のデータサンプルを収集するステップであって、前記第１のデータサンプルを収集するステップが、前記データ片の第１のセットのそれぞれからデータを収集することを具えており、前記データ片の第１のセットのそれぞれからデータを収集することが、前記データ片の第１のセットのそれぞれの中に含まれるデータのサブセットのみを収集することを具える、ステップと、
前記クエリエンジン（１４０）において、前記第１のデータサンプルの解析に基づいてクエリに中間結果を計算するステップと、
前記クエリエンジン（１４０）において、前記中間結果に基づいて前記事象データベース（１１０）のデータ片の第２のセットを識別するステップと、
前記クエリエンジン（１４０）において、前記事象データベース（１１０）のデータ片の第２のセットから第２のデータサンプルを収集するステップであって、前記第２のデータサンプルを収集するステップが、前記データ片の第２のセットのそれぞれからデータを収集することを具えており、前記データ片の第２のセットのそれぞれからデータを収集することが、前記データ片の第２のセットのそれぞれの中に含まれるデータの完全なセットを収集することを具える、ステップと、
前記クエリエンジン（１４０）において、前記第２のデータサンプルの解析に基づいて前記クエリに最終結果を計算するステップと、
を具えることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
前記データ片の第１のセットから前記第１のデータサンプルを収集するステップが、前記データ片の第１のセットの列のデータセットからデータを収集することを具えることを特徴とする方法。
【請求項３】
請求項２に記載の方法において、
前記データ片の第１のセットが、時間によって整理された事象データを具えることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、
前記クエリを受け取り且つ読み取るステップが、さらに、インプリシットデータへの参照を読み取ることを具えることを特徴とする方法。
【請求項５】
請求項４に記載の方法において、
前記クエリを受け取り且つ読み取るステップが、さらに、順序付け機能及び分類機能のうちの少なくとも一方を選択することを具えることを特徴とする方法。
【請求項６】
請求項１に記載の方法において、
データ片の第１のセットを識別するステップが、構成データベースを用いて前記データ片の第１のセットのノードの場所を識別することを具えることを特徴とする方法。
【請求項７】
請求項１に記載の方法において、
文字列変換器を用いて整数に前記クエリの文字列を変換するステップが、プレフィクスマッチングを可能にするフォーマットで記憶された文字列識別器を用いて文字列を変換することを具えることを特徴とする方法。
【請求項８】
請求項１に記載の方法において、
前記クエリが、少なくとも１の時間範囲及び少なくとも１の事象データソースを有することを特徴とする方法。
【請求項９】
請求項８に記載の方法において、
前記クエリに前記最終結果を計算するステップが、さらに、抽出データの統計分布の解析に基づいて結果の精度の推定のための信頼帯を計算することを具えることを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、
前記クエリに前記最終結果を計算するステップが、さらに、クエリ結果としてコホートに関連するコホート及び集計データ双方を戻すことを具えることを特徴とする方法。
【請求項１１】
請求項９に記載の方法において、
前記クエリに中間結果を計算するステップが、さらに、抽出データの統計分布の解析に基づいて結果の精度の推定のための信頼帯を計算することを具えることを特徴とする方法。
【請求項１２】
迅速なデータ解析のための方法であって、
クエリエンジン（１４０）において、クエリを受け取り且つ読み取るステップであって、当該クエリを読み取るステップが、文字列変換器（１３０）を用いて整数に前記クエリの文字列を変換することを具え、前記クエリを読み取るステップが、さらに、前記クエリに関するデータを含む事象データベース（１１０）のデータ片の第１のセットを識別することを具える、ステップと、
前記クエリエンジン（１４０）において、前記事象データベース（１１０）のデータ片の第１のセットから第１のデータサンプルを収集するステップであって、前記第１のデータサンプルを収集するステップが、前記データ片の第１のセットのそれぞれからデータを収集することを具えており、前記データ片の第１のセットのそれぞれからデータを収集することが、前記データ片の第１のセットのそれぞれの中に含まれるデータのサブセットのみを収集することを具える、ステップと、
前記クエリエンジン（１４０）において、前記第１のデータサンプルの解析に基づいて前記クエリに第１の中間結果を計算するステップと、
前記クエリエンジン（１４０）において、多くの中間サーチを実行するステップであって、各中間サーチが、
前記第１の中間結果及びさらなる中間結果のうちの少なくとも一方に基づいて、前記事象データベース（１１０）のデータ片のさらなるセットを識別するステップと、
前記データ片のさらなるセットからさらなるデータサンプルを収集するステップと、
前記さらなるデータサンプルの解析に基づいてさらなる中間結果を計算するステップと、を具える、ステップと、
前記クエリエンジン（１４０）において、前記クエリに最終結果を計算するステップと、
を具えることを特徴とする方法。
【請求項１３】
請求項１２に記載の方法において、
前記中間サーチの数が、固定数であることを特徴とする方法。
【請求項１４】
請求項１２に記載の方法において、
さらに、前記クエリエンジン（１４０）において、抽出データの統計分布の解析に基づいて、それぞれのさらなる中間結果について信頼帯を計算するステップを具えることを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、
多くの中間サーチを実行するステップが、さらなる中間結果の信頼帯が信頼閾値を過ぎるまで中間サーチを実行することを具えることを特徴とする方法。
【請求項１６】
請求項１５に記載の方法において、
前記信頼閾値が、スピード／精度変数に応じて自動的に設定されることを特徴とする方法。
【請求項１７】
請求項１５に記載の方法において、
前記クエリを受け取り且つ読み取るステップが、さらに、クエリツリーの中にＳＱＬタイプのクエリの文字列を解析することを具えることを特徴とする方法。
【請求項１８】
請求項１６に記載の方法において、前記スピード／精度変数が、前記クエリの部分として通過されることを特徴とする方法。
【請求項１９】
請求項１８に記載の方法において、前記クエリが、少なくとも１の時間範囲及び少なくとも１の事象データソースを有することを特徴とする方法。
【請求項２０】
請求項１４に記載の方法において、さらに、前記クエリエンジン（１４０）において、前記信頼帯が信頼閾値を下回っていることをユーザに知らせるステップを具えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照  
本出願は、２０１４年３月１０日に出願され、参照することによりその全体が盛り込まれた米国仮出願第６１／９５０，８２７号の利益を請求する。
【０００２】
本発明は、一般に、データ解析の分野、特にデータ解析の分野における迅速なデータ解析のための新規且つ有用なシステム及び方法に関する。
【背景技術】
【０００３】
今日のビジネスは、販売、マーケティング、及び他の重要な業務に関する大量のデータを収集する。このようなデータの問い合わせ（クエリ）は、多くの場合、特に複雑なクエリに関して困難且つ資源集約的なプロセスである。ある程度、クエリの性能は、データ集合体及び索引の予計算によって改善できるが、これを大きなデータセットの中で全ての次元にわたって行うことは実行不可能である。このために、クエリの性能の問題が、多くの場合、データ解析を遅くする。したがって、データ解析のフィールドに迅速なデータ解析のためのシステム及び方法を作る必要性がある。本発明は、このような新規且つ有用なシステム及び方法を提供する。
【図面の簡単な説明】
【０００４】
【図１】図１は、好適な実施例のシステムの概略図である。
【図２】図２は、好適な実施例のシステムの事象ストリームの典型的な表である。
【図３】図３は、好適な実施例のシステムの一実施形態の概略図である。
【図４】図４は、好適な実施例の方法の図表である。
【発明を実施するための形態】
【０００５】
本発明の好適な実施例の以下の記載は、これらの好適な実施例に本発明を限定することを意図するものではなく、むしろ、当業者が本発明を製造且つ使用し得ることを意図するものである。
【０００６】
図１に示すように、迅速なデータ解析のためのシステム１００が、事象データベース１１０、文字列参照データベース１２０、文字列変換器１３０及びクエリエンジン１４０を有している。このシステム１００は、追加的又は代替的に、インタフェースモジュール１５０、構成データベース１６０及び／又はデータマネージャ１７０を有する。
【０００７】
システム１００は、分散コンピューティングを、大容量のデータのためにクエリスピードを高めるよう特別に設計されたアーキテクチャを駆動するよう結び付けることによって、迅速なデータ解析をし得るよう機能する。システム１００は、好ましくは、事象データのために使用され、事象データベース１１０の各エントリが、好適には、タイムスタンプを有しており、そのタイムスタンプ順に初めに記憶される。追加的又は代替的に、各エントリが、シーケンスナンバ、又は事象がどのような順番となっているかを示す何らかの他のフィールドを有する。別の代替例として、データ記憶の順によって事象の順番を判定し得る。タイムスタンプ順にデータを記憶することにより、貴重な処理時間を費やさずに、大量のリアルタイムデータを記憶でき、データを整理し及び／又は書き換える。また、システム１００は、好適には、事象データベース１１０内で高性能のデータ圧縮を可能にする文字列変換器１３０及び文字列参照データベース１２０を用いて整数に事象データの文字列を変換する。事象データベース１１０は、好適には、分散コンピューティングシステムにわたってデータ片に分布される。システム１００に問い合わせると、クエリエンジン１４０が、好適には、分散コンピューティングシステムにわたってデータ片からサンプルを抽出し、迅速な並列読み出しを可能にする。そして、このクエリエンジン１４０は、好適には、一部には選択されたサンプルに基づいてクエリの回答を判断し、全てのデータに問い合わせをした場合よりもはるかに素早い応答を可能にする。クエリエンジン１４０は、好適には、クエリエンジンのサンプリング方法を調整でき、所望の比率のスピード対精度を達成し、クエリエンジン１４０を、多種多様なクエリのタイプに対して適合性のあるものにする。少なくとも部分的に上記の態様を利用して、システム１００は、好適には、大量のデータの迅速な解析を可能にする一方で、大がかりな前処理又はオーバーヘッドを最小限にし又は無くす。
【０００８】
事象データベース１１０は、システム１００のための主要な情報ストアとして機能する。事象データベース１１０は、好適には、例えば時間要素又は事象の順番の表示を含むデータといった、事象データを記憶する。事象データは、好適には、少なくとも関連する時間フィールド及びセッションフィールドを有するが、何らかの適切な一連のフィールドを含んでもよい。事象データベース１１０は、追加的又は代替的に、適切な組織的スキーマに適切なデータを記憶する。事象データベース１１０は、好適には、様々な方法でデータを記憶するための多数のデータセットを有する。例えば、図２に示すように、１つのデータセットは、ユーザＩＤ（ＵＩＤ）によってグループ化され（例えば、共有され）時間によって整理される事象の一覧を有する一方、他のデータセットが、同じ事象の一覧を有するがＩＰアドレスによってグループ化され時間によって整理される。データ共有は、好適には、データを分割及び／又はグループ化するよう使用されるが、データは、追加的又は代替的に任意の適切な方法でグループ化してもよい。上記の例のように、異なるデータセットが、同一のデータを記憶してもよいが、異なるデータセットはまた、同じデータの異なるサブセット、又は異なるデータ全体を記憶してもよい。例えば、１つのデータセットは、ＵＩＤによってグループ化され時間で整理されたた事象の一覧を有しており、事象はまた、ＩＰアドレス及びロケーションフィールドを有している。第２のデータセットが、ＩＰアドレスによってグループ化され時間で整理された同じ事象の一覧を有しているが、事象情報は、ロケーション又はＵＩＤを有していない。事象データベース１１０は、好適には、全てのデータセットを列のデータセットとして整理し、代替的に、データセットが任意の適切な方法で整理される。列のフォーマットで記憶されたデータセットは、好適には、列の圧縮を使用して、記憶されるデータの数を減らす。列の圧縮は、好適には、列に記憶されたデータのシーケンシャル特性を用いたテクニックを有しており、スペースを省く。
【０００９】
事象データベース１１０は、好適には、明示的及び暗黙的なデータ双方の記憶を可能にする。暗黙的なデータは、好適には、暗黙的に添付されたオブジェクトデータソースを有しており、クエリで参照し得る。例えば、セータの販売データの事象ストリームでは、各事象が、売主（「e.merchnat_id」）、末端（「e.terminal_id」）、取引の金額（「e.dollar_amount」）、及び販売されたセータのタイプ（「e.sweater_id」）を特定する明示的なデータフィールドを持ち得る。また、各事象は、オブジェクトデータソース又はこれらの明示的データフィールドに関連する他のタイプの暗黙的データを有しており、例えば、サイズ（「sweater_size」）及び色（「sweater_color」）といった、セータのタイプに関する各「e.sweater_id」特性に関連するオブジェクトデータがある。事象データベース１１０は、好適には、これらの関連データの特性をクエリにとって自動的に役立つものにし、例えば、「e.sweater_id.sweater_color」というフィールドによって、セータの色にアクセスする。事象データベース１１０は、テーブルジョインの必要性を無くすよう機能し得る、属性フィールドへのダイレクトなアクセスを有する。属性フィールドへのアクセスは、ジョインテーブルとして宣言されるテーブルをインポートすることによって促される。ジョインテーブルを宣言することは、好適には、関連する事象データテーブルの大きさにジョインテーブルをリンクし得る。ジョインテーブルは、好適には、属性ネームバリュー対として記憶される。
【００１０】
事象データベース１１０は、好適には、分散コンピューティングシステムのコンピュータにわたって分散する。分散コンピューティングシステムの各ノードは、好適には、事象データベース１１０に含まれるデータの一部を記憶する。このデータは、好適には、永続的メモリ（例えば、ハードディスクドライブ、フラッシュメモリ）に記憶されるが、データのいくつか又は全てを、追加的又は代替的に一時的メモリ（例えば、ＲＡＭ）に記憶し得る。事象データベース１１０のデータは、好適には、各ノードでデータ片にさらに分割される。データ片は、好適には、横方向及び縦方向のテーブルパーティションであるが、データ片が、好適には、データテーブルの全ての行の一部及び全ての列の一部の交点から形成される。各データ片は、好適には、少なくとも時間情報を含むが、追加的又は代替的に他の情報を含み得る。データ片は、時間で分割でき、例えば、各データ片が特定の２４時間にわたって発生した一連の事象を含む。データ片は、追加的又は代替的に、他の適切な情報（例えば、ＵＩＤ、ＩＰアドレス、セッションＩＤ、等）によって分割され得る。データ片のパーティションは、好適には、縦方向のパーティションが好適には一定数のフィールドを有し、各縦方向のパーティションについて一定数の横方向のパーティションがある、という規則によってなされる。例えば、データセットが時間フィールド、ＵＩＤフィールド、ＩＰアドレスフィールド、及びロケーションフィールドを有する場合、データセットが縦方向に３つに分割され得る。第１の縦方向のパーティションは、時間フィールド及びＵＩＤフィールドを有しており、第２の縦方向のパーティションは、時間フィールド及びＩＰアドレスフィールドを有しており、第３の縦方向のパーティションは、時間フィールド及びロケーションフィールドを有する。そして、データセットが日付によって横方向に分割され、１週間のデータがある場合、これは、７個の横方向のパーティションである。したがって、データが、２１個のデータ片に分割される。データ片の分割は、追加的又は代替的に、他の規則セット又はアルゴリズムによって自動的になされ、又は手動でなされる。
【００１１】
各データ片は、好適には、データ片ナンバー（又は他の識別子）を有しており、各データ片ナンバーが好適には、データ片が存在するノードとともに、構成データベース１６０に記憶される。このリンクされたデータは、追加的又は代替的に、適切な場所に記憶される。データ片とノードとのリンクについての中心となるリストをキープすることで、クエリエンジン１４０が特定のデータについてクエリに対する正しいノードを判断できる。データ片／ノードのリンクのリストが、データ片に含まれるデータの概要といった他の情報を追加的に有する。
【００１２】
文字列参照データベース１２０は、文字列を一意的に特定する整数に文字列をリンクする情報を記憶するよう機能する。この文字列参照データベース１２０は、文字列変換器１３０によって使用され、文字列をそれらの各整数識別子に変換し、逆もまた同様に行う。文字列参照データベース１２０の識別子への文字列のマッピングは、好適には、（例えば、トライデータ構造の使用により）プレフィクスマッチングを可能にする方法で記憶されるが、追加的又は代替的に、任意の適切な方法で記憶される。文字列参照データベース１２０は、好適には、分散コンピューティングシステムにコンピュータにわたって分散する。分散コンピューティングシステムの各ノードは、好適には、文字列参照データベース１２０に含まれるデータの一部を記憶する。このデータは、好適には、永続的メモリ（例えば、ハードディスクドライブ、フラッシュメモリ）記憶されるが、データのいくつか又は全てを、追加的又は代替的に一時的メモリ（例えば、ＲＡＭ）に記憶し得る。文字列参照データベース１２０のデータは、好適には、各ノードでデータ片にさらに分割される。文字列参照データベース１２０のデータ片は、好適には、事象データベース１１０のデータ片に対応するが、代替的に、事象データベース１１０の分割とは独立して分割される。
【００１３】
事象データベース１１０の各フィールドは、好適には、文字列参照データベース１２０の独立した文字列参照データ片に対応する。これにより、異なるフィールドの異なる文字列について同じ整数識別子を使用し得る。文字列参照データ片と対応する事象データベース１１０フィールドとの間の関係が、好適には、構成データベース１６０に記憶されるが、代替的に、任意の適切な場所に記憶される。文字列参照データ片が事象データ片に対応する場合、その関係は、単に、２つのデータ片がデータ片識別ナンバーを共有するということである。文字列参照データ片と事象データベース１１０フィールドとの間の関係は、好適には１対１であるが、代替的に、任意の適切な関係とすることができ、例えば、２つのフィールドが類似する文字列データ（例えば、ミドルネーム及びファーストネーム）を含む場合、それらは、文字列参照データ片を共有する。
【００１４】
文字列変換器１３０は、入力事象データの文字列を整数識別子に変換するよう機能する。整数識別子への文字列の変換は、事象データを記憶するのに要するスペースの量を大いに省くことができ、また（好適にはクエリエンジン１４０によって使用されるオペレーションを含む）特定のオペレーションを最適化し得る。文字列変換器１３０は、好適には、事象データが事象データベース１１０に書かれる前に、受け取った事象データの文字列を文字列識別子に変換するが、追加的又は代替的に、任意の適切な時に文字列識別子に文字列を変換する。文字列変換器１３０は、好適には、受け取った事象データの全ての文字列を変換するが、代替的に、受け取った事象データの全ての文字列のうちのサブセットのみを変換する。文字列変換器１３０は、好適には、文字列参照データベース１２０の文字列に対応する識別子を検索することによって、文字列を変換する。対応する識別子は、好適には、特定の文字列にリンクされる識別子であるが、対応する識別子が、追加的又は代替的に、他のデータにリンクされる。例えば、文字列が特定値を有し、文字列が事象データの特定のフィールド又はタイプの一部である場合に、識別子がある文字列に対応するに過ぎない。これにより、識別子を異なるデータのタイプに関して再使用可能となり、例えば、整数識別子「４２」が、「国」のフィールドのデータに関して文字列「カナダ」に対応し、「月」のフィールドに関して文字列「１月」に対応する。この「他のデータ」は、文字列参照データベース１２０に明示的に存在し、又は黙示的に存在しており、例えば、文字列参照データが異なる事象データフィールドに対応する場合、（文字列参照データベースのセクションで説明したように）文字列参照データが異なる場所に記憶される。
【００１５】
文字列が文字列参照データベース１２０に対応する識別子を有する場合、文字列が事象データベース１１０に書き込まれる前に、その識別子に変換される。文字列が対応する識別子を有しない場合、対応する識別子が好適にはその文字列のために形成される。対応する識別子は、好適には、文字列参照データベース１２０の中の次の利用可能な識別子であるが、代替的に、文字列の値にしたがって選択され得る。例えば、ａ、ｂ、又はｃで始まる全ての文字列の値が、「１」で始まる整数識別子を有する。識別子が文字列の値にしたがって選択される場合、識別子参照データが、好適には、プレフィックスマッチングを可能にするフォーマットで記憶される。
【００１６】
また、文字列変換器１３０は、クエリに関する文字列の変換を扱うよう機能する。クエリエンジン１４０がクエリを受け取ると、クエリの文字列が、好適には、文字列変換器１３０に送られて識別子に変換される。そしてクエリは、好適には、識別子を用いて処理される。クエリが処理された後に、クエリの結果の識別子が、好適には文字列変換器１３０によって処理されて文字列に戻され、文字列変換器１３０からのさらなる干渉なしに、クエリの結果を一覧又は処理可能である。
【００１７】
クエリエンジン１４０は、事象データの入力されるクエリを処理し、クエリの結果を戻すよう機能する。クエリエンジン１４０は、好適には、事象データソース、時間範囲、フィルタ、パーティション機能、及びメトリック機能を有するクエリを取り込む。事象データソースは、好適には、事象データベース１１０の事象データフィールドに関しており、例えば、「e.sweater_id」が、販売されたセータのタイプに対応する事象データフィールドに関するものである。時間範囲はクエリが検索すべき時間の範囲であり、クエリは、好適には、「e.time」値が特定の時間範囲の外にある事象データを無視する。フィルタによって、好適には、フィルタリング条件に基づいてデータをクエリに含ませたりクエリから除外することができ、フィルタは、好適には、時間範囲を満足する事象データに適用され得るが、追加的又は代替的に、他の事象データに適切される。フィルタを満足しない事象データは、好適には、クエリ結果から除外される。このような方法では、時間範囲は、好適には、時間範囲が好適には他のフィルタよりも高い優先順位を有するという点を除いて他のフィルタと類似する。例えば、フィルタの組が「e.sweater_id>10」と記述するフィルタを有する場合、「フィルタ」は、「e.sweater_id≦10」を備える任意の事象「e」について「偽」を返す。パーティション機能は、好適には、時間範囲及びフィルタの双方を満足する事象データについて評価されるが、追加的又は代替的に、他の事象データに適用される。パーティション機能は、好適には、１又はそれ以上の関係を満足することによって事象をグループ化している。パーティション機能は、好適には、パーティション機能を満足する全ての事象を返し、例えば、「partition(e.sweater_id=23)」が、「e.sweater_id=23」を満足するものを含む全ての事象を返す。メトリック機能は、好適には、パーティション機能から統計データを作成する。メトリック機能は、好適には、所定の条件を満足する事象データの和、パーセンタイル、比率及び／又はパーセンテージを作成する機能を有する。パーティション機能の結果がより大きな母集団からの代表サンプルとして解釈される場合、メトリクスが、対応するより大きな母集団のメトリクスのサンプルベースの評価であるとみなされる。これらのケースでは、クエリエンジン１４０が、好適には、評価のための信頼帯を提供し、これは統計的なブート処理によって取得されるものに相当する。信頼帯は、好適には、観察される統計分布の解析を通して計算されるが、追加的又は代替的に、任意の適切な方法で提供される。ユーザは、信頼性の指標として信頼帯を提供され得るが、例えば、ユーザは、信頼性が低い場合、疑わしいサンプルバイアスが知らされる。
【００１８】
事象及びメトリクスを返すのに加えて、クエリエンジン１４０は、追加的又は代替的に、オブジェクト及び／又はオブジェクトのグループ（コホートと称される）を返し得る。例えば、クエリは、パーティション機能「partition(e.sweater_id,23)」を満足する事象に関する「terminal_id」値の組を要求する。コホートは、例えば、特定の事象シーケンスを満足するユーザのグループといった、例えば、１週間にわたって１０時間を超えて特定のウェブサイトで活動したユーザのグループのような行動コホートを有している。
【００１９】
クエリが、追加的又は代替的に、機能の整理及び／又はグループ化を有する。整理機能は、好適には、クエリの結果の整理を可能にする。整理機能は、好適には最終結果に適用されるが、追加的又は代替的に、（クエリステップでの計算に整理された結果が必要な場合）中間結果に適用される。グループ化機能は、好適には、クエリの結果のグループ化を可能にする。整理機能と同様に、グループ化機能は、好適には最終結果に適用されるが、追加的又は代替的に、中間結果に適用される。整理及びグループ化機能は、好適には、第１のパス（例えば、第１の中間結果の生成の間）で選択され又は特定されるが、追加的又は代替的に、適切な時間で特定される。グループ化機能は、追加的に、コホート機能を有する。コホート機能は、対象の母集団をコホートの組に分割するグループ化機能の特別なケースであり、各対象が、ちょうど１つのコホートに現れる。
【００２０】
クエリエンジン１４０は、好適には、クエリの第１の予処理によってクエリを処理するが、これは、クエリを解析し、文字列変換器１３０を用いて整数にクエリの文字列を変換することを有する。予処理は、追加的又は代替的に、ユーザ認証の実行、ユーザが使用し易い文字列の分解（例えば、「今」を現在のタイムスタンプに分解する）、ＳＱＬタイプのクエリの文字列をクエリツリーに解析することを有する。また、予処理は、好適には、（計算又は構成データベース１６０への参照のいずれかを介して）クエリに関連するデータがどこに存在するのかを分解すること、エラー処理、スケーリング、テーブルジョイン、及び／又はクエリの評価に必要な計算を有する。
【００２１】
クエリの予処理の後に、クエリが、好適にはマルチプルパス法を用いて評価される。第１のパスで、クエリエンジン１４０が、好適には、事象データベース１１０の多数のデータ片から小さなサンプルを同時に取り込む。そして、クエリエンジン１４０は、好適には、サンプルについて中間計算を実行し、可能性のあるクエリの結果を特定し又は絞り込む。そして、このような可能性のあるクエリの結果は、次のパスのための入力として使用される。次のパスは、（第１のパスと同様であるが、異なる入力を備える）別の特定／絞り込みパスであり、又は次のパスは最終パスである。最終パスは、好適には、クエリへの疑わしい関連情報を含むデータ片のフルスキャンを有するが、追加的又は代替的に、データ片の部分スキャンのみを有する。クエリの結果は、好適には、最終パスの結果から計算される。
【００２２】
例えば、クエリエンジン１４０がクエリを受け取り、特定のウェブサイトに関して過去の月にわたって最も活動的なユーザのトップ１００を特定する。第１のパスでは、クエリエンジン１４０が、ユーザＩＤ及び活動データを含む（分散コンピューティングシステムの多くのノードにわたって分散する）事象データベース１１０のデータ片に問い合わせを行い、各ノードにおいて、少ないデータサンプルからトップユーザを特定しようと試みる。そして、クエリエンジン１４０は、第１のパスの結果を比較し、データサンプルからユーザのトップ１０，０００のリストを出す。そして、クエリエンジン１４０は、これら１０，０００のユーザに関するデータを含む全てのデータ片のフルスキャンを行い、このリストからユーザのトップ１００を判定する。
【００２３】
パスの数は、好適には手動で割り当てられ、２つのパスが初期値であるが、追加的又は代替的に、自動的に設定し得る。（どのくらいの量のデータが各パスでサンプリングされ、どのくらいのサンプルが各パスで選択されるといったことを含む）サンプリング方法は、好適には、所望の信頼区間及び信頼水準にしたがって自動的に判断される。例えば、特定の信頼水準において特定の信頼区間内にあることが望ましい母集団推定に関して選択されたサンプルが、好適には、ランダムに選択され、サンプルの数は、このような信頼区間及び信頼水準に要する最小数に対応する。サンプリング方法は、追加的又は代替的に、普通に分布していないことが分かっている及び／又は独立した且つランダムな変数から成るものではないことが分かっている、データに関するランダムなサンプリング以外のサンプリングを有する。例えば、データセットが（過去のクエリ又は他のデータソースのいずれかから）特定の分布にしたがうことが一般的に分かる場合、データセットが、この特定の分布にしたがってサンプリングされる。
【００２４】
本発明の一実施例では、クエリエンジン１４０が、クエリの一部として又はクエリに適用される一般的設定として、スピード／精度変数を取り込む（好適には、構成データベース１６０に記憶される）。このスピード／精度変数は、好適には、パスの数及び／又は結果を与えるよう取り込まれるサンプルの数を調整する。例えば、「最高スピード」値に近いスピード／精度変数セットを備えるクエリは、非常に少ない数のサンプルを取り込むが、不正確な回答を返す可能性がある。スピード／精度変数が「最大精度」の側に向かって調整される場合、クエリはより多くの時間及び／又は処理能力を取り込むが、より正確な結果を返す。このような実施例におけるクエリエンジン１４０は、追加的又は代替的に、クエリ推定器を有する。クエリ推定器は、好適には、特定のクエリ及びスピード／精度変数に関して、クエリがどのくらいの時間取り込み、クエリの結果がどのくらい正確であるかの推定値を生成する。クエリ推定器は、好適には、直接的（例えば、所望の時間及び／又は精度を設定し、特定のスピード／精度の変数の設定を受け取るクエリエンジンのユーザによって）又は間接的（例えば、クエリエンジンのユーザが、異なるスピード／精度の変数の設定に関するクエリの時間／精度を見積もって、正しいスピード／精度の変数の設定を選択し得る）に使用され得る。
【００２５】
インタフェースモジュール１５０は、システム１００へのグラフィックユーザインタフェースを提供するよう機能する。インタフェースモジュール１５０は、好適には、クエリエンジンのユーザがデータを閲覧して編集し、クエリを形成し、及び／又はクエリの結果を視覚化するための方法を提供する。また、インタフェースモジュール１５０は、好適には、ジョインテーブルの途切れのない導入を可能にし、ジョインテーブルからのデータが、好適には、事象データの列として自動的に示されるが、追加的又は代替的に、適切な方法で表されてもよい。インタフェースモジュール１５０は、好適には、メトリクスタブ、派生フィールドタブ、調査タブ、及び／又はコホートタブを有する。
【００２６】
メトリクスタブは、好適には、クエリエンジンのユーザが、メトリクスを規定し、名前を付け、及び編集することを可能にする。メトリクスタブは、顧客がデータを実行する標準メトリクスのツールボックスを有することができ、追加的又は代替的に、メトリクスタブは、事象データフィールド及び／又は事象データベース１１０に存在するコンテンツに基づいて自動的に生成されたメトリクスを有する。例えば、事象データが「page」及び「user」フィールドを有する場合、「page」フィールドの値が「user」フィールドからユーザのユニークなカウントによって分割される「Photo_view」である事象の数を計算する自動的に生成されるメトリクスが、メトリクスタブに存在し得る。
【００２７】
派生フィールドタブにより、好適には、クエリエンジンのユーザが事象データに関して派生フィールドを形成できる。派生フィールドタブは、好適には、存在するフィールドから新たな（派生）フィールドを形成するための選択肢を提供するのに加えて、存在する事象データベース１１０フィールドを見せる。派生フィールドは、好適には、他のフィールドのデータから計算されるフィールドである。例えば、「利益」は、「歳入」−「費用」によって得られるフィールドである。派生フィールドは、インタフェースモジュール１５０内のみに存在し、又は事象データベース１１０の関係として存在し（そのため、クエリが派生フィールドを計算する）、又は事象データベース１１０の中の記憶されたデータとして存在する（すなわち、派生フィールドの値が前もって計算される）。
【００２８】
調査タブにより、好適には、クエリエンジンのユーザが事象データベース１１０の事象データとやりとりし得る。調査タブにより、好適には、クエリエンジンのユーザが、事象データに（カウント、ユニークなカウント、和、等の）基本的機能の組み合わせ、メトリクス、及びフィルタを適用し得る。例えば、クエリエンジンのユーザは、異なるスケーリングを備えるフィルタリングされたデータに関する２つのメトリクスの和（例えば、「２*Metric1(Filter(event_data))+Metric2(Filter(event_data))」）を計算できる。調査タブは、追加的又は代替的に、事象データ及びそれに基づく計算が、事象データベース１１０のデータ例又は実際のデータのいずれかに視覚化され又は示される領域を有する。
【００２９】
コホートタブにより、好適には、クエリエンジンのユーザが事象データのオブジェクトをカテゴリー毎にグループ化でき、例えば、ウェブサイトのメンバーをサイトの活動に基づいてコホートに分割する。コホートタブにより、好適には、クエリエンジンのユーザがオブジェクトを分割するカテゴリーを特定し得る。追加的又は代替的に、コホートタブは、オブジェクトを分割するカテゴリーを自動的に形成する。例えば、コホートタブは、ウェブサイトのメンバーが１週間にログインする日数に基づいてコホートを自動的に形成し、ウェブサイトのメンバー８つのカテゴリー（０、１、２、３、４、５、６又は７日のログイン）の１つに分割される。コホートタブは、好適には、（時間によるグループ化のような）１セットの頻繁に使用されるコホート機能を有しており、コホートを生成するのにクエリエンジンのユーザを補助する。コホートタブにより、好適には、追加的にクエリエンジンのユーザがオブジェクトの特性を規定し得る。オブジェクトの特性は、好適には、事象データのシーケンスに基づいて規定され、統計機能、統計議論、及びフィルタの組み合わせで形成される。例えば、「hours_active」オブジェクトの特性が、「count_unique(align_time(event.time,3600))」によって計算される。コホートタブにより、追加的又は代替的に、クエリエンジンのユーザが予め規定されたオブジェクトの特性（例えば、署名タイムスタンプ）を閲覧又は修正できる。
【００３０】
構成データベース１６０は、システム１００の動作に関する設定を保存するよう機能する。構成データベース１６０は、好適には、事象データベース１１０の事象データ片と分散コンピュータシステムのノードとの間のマッピングを記憶する。構成データベース１６０は、追加的又は代替的に、事象データ片に関する他の情報（例えば、それらの内容、又は事象データ片と事象データフィールドとの間のマッピング）を記憶する。また、構成データベース１６０は、好適には、文字列参照データベース１２０の文字列のデータ片と分散コンピュータシステムのノードと間のマッピングを記憶する。構成データベース１６０は、追加的又は代替的に、文字列データ片に関する他の情報（例えば、文字列データ片と事象データ片との間のマッピング又は文字列データ片と事象データフィールドとの間のマッピング）を記憶する。また、構成データベース１６０は、好適には、システム１００の動作に関する一般的設定を記憶するが、例えば、構成データベース１６０は、（スピード／精度のトレードオフ変数のような）クエリに関するグローバルの設定を記憶する。また、構成データベース１６０は、データの記憶又は分類に関するグローバルな設定を記憶する。
【００３１】
好適な実施例のバリエーションでは、メタデータ（例えば、データ片とノード等の間のマッピング）が、別々のメタデータ記憶部に記憶される一方、構成データベース１６０が、他の設定（例えば、クエリに関するグローバル設定）のみを記憶する。
【００３２】
データマネージャ１７０は、事象データベース１１０のデータを保持又は修正して、システム１００のパフォーマンスを最大化するよう機能する。データマネージャ１７０は、好適には、どのようにしてデータセットが整理され、既存のデータから新たなデータセットを生成すべきか否かを判断する。データマネージャ１７０は、記憶されたデータに応じて一連の規則又は他のアルゴリズムに基づいて及び／又はクエリに応じて一連の規則又は他のアルゴリズムに基づいて、クエリエンジンのユーザの手入力によるインプットに基づいてこれを行う。例えば、データマネージャ１７０は、クエリエンジンのユーザコマンドに応じて、ＩＰアドレスによってグループ化され時間によって記憶された事象のリストを含むデータセットを生成する。そして、データマネージャ１７０は、ＩＰアドレスによってデータをグループ化するデータセットが存在する場合、場所によってデータをグループ化するよう構成された別のデータセットを生成するということを記述する構成データベース１６０の規則に基づいて、同じ事象を含むが今度は場所によってグループ化されたデータセットを自動的に生成する。クエリエンジンのユーザが特定のウェブサイトのユーザに関する反復クエリを作成する場合、データマネージャ１７０は、このようなデータをＵＩＤによって記憶させることが有益であることを認識し、その後、同じ事象を含むがＵＩＤによってグループ化されたデータセットを生成する。同様に、データマネージャ１７０が特定のデータセットがあまり使用されていないことを認識する場合、データマネージャ１７０は、そのデータセットを削除し又は別にそのデータセットを整理する。
【００３３】
また、データマネージャ１７０は、好適には、いかにしてデータ片を事象データベース１００でエンコードするのかを制御する。データマネージャ１７０は、好適には、事象データベース１１０をカバーするセクションで説明したように、データ片を分割する。データマネージャ１７０は、好適には、システム１００のパフォーマンスを最適化するために、データ片を分割又は再分割する。データマネージャ１７０は、記憶されたデータに応じた一連の規則又は他のアルゴリズムに基づいて、及び／又はクエリに応じた一連の規則又は他のアルゴリズムに基づいて、クエリエンジンのユーザの手入力によるインプットに基づいてこれを行う。
【００３４】
また、データマネージャ１７０は、好適には、システム１００のパフォーマンスを最適化するために、データ集合体を生成する。データ集合体は、好適には、事象データに和、平均、又は他の数学的演算を実行することによって形成される。データ集合体は、好適には、共通のクエリによって実行される動作を予測し、これらのクエリが呼ばれたときに時間又は処理能力を節約する。データマネージャ１７０は、記憶されたデータに応じた一連の規則又は他のアルゴリズムに基づいて、及び／又はクエリに応じた一連の規則又は他のアルゴリズムに基づいて、クエリエンジンのユーザの手入力によるインプットに基づいて、データ集合体を生成する。
【００３５】
図３に示すように、システム１００の一実施例では、クエリがインタフェースモジュール１５０によって初期化される。そして、クエリが、ＳＳＬ終端のためのＮｇｉｎｘウェブサーバによって受信され、レガシーサーバのレガシーＰＨＰコード、そして、ユーザの認証のためにクエリＡＰＩサーバ、ユーザが使い易い文字列の解像度、及びクエリ解析（例えば、ＳＱＬタイプの文字列のクエリツリーへの解析）を通過する。そして、クエリは、クエリエンジン１４０（データサーバ）によって処理される。クエリエンジンは、文字列参照データベース１２０（文字列リーブス／ハッシュ）及び事象データベース１１０（データクエリリーブス／ローカルなデータ片）にそれぞれアクセスする文字列変換器１３０（文字列アグリゲータ）及びマージサーバからのデータを用いて、クエリを処理する。そして、クエリの結果が、同じサーバパスを通してインタフェースモジュール１５０に返される。
【００３６】
２．迅速なデータ解析のための方法
図４に示すように、迅速なデータ解析の方法２００が、クエリを読み取るステップＳ２１０と、クエリに基づいて第１のデータサンプルを実行するステップＳ２２０と、データサンプルからのクエリの中間結果を計算するステップＳ２３０と、クエリの中間結果に基づいて第２のデータサンプルを実行するステップＳ２４０と、第２のデータサンプルに基づいて最終的なクエリの結果を計算するステップＳ２５０とを有する。この方法２００は、好適には、上記のシステム１００によって実施されるが、追加的又は代替的に、任意の適切なシステムによって実施され得る。
【００３７】
方法２００は、好適には、分散コンピューティングを使用して、多くのデータセットを同時にサンプリングし、それらの全体を検索する必要なしに、これらのデータセットからの結果を戻すことによって、迅速なデータ解析を可能にするよう機能する。方法２００のマルチパスクエリプロセスにより、好適には、（Ｓ２２０及びＳ２３０を介して）潜在的に関連するデータを即座に識別でき、さらなる解析のための対象とすることができ（Ｓ２４０及びＳ２５０）、無関係なデータに関して時間を浪費することを防止する。各ステップの範囲は、好適には調整可能であり、スピード対精度の理想的な比のため、クエリを最適化、強化又はそうでなければ改善し得る。これらのステップを通して、方法２００により、好適には、膨大な予処理又はオーバーヘッド（間接的処理）なしに、大量のデータの迅速な解析が可能となる。
【００３８】
クエリの読み込みステップＳ２１０は、いかにしてデータに問い合わせを行うかを特定するよう機能する。ステップＳ２１０によって読み込まれたクエリは、好適には、システム１００に記載されているのと実質的に同じである。クエリの読み込みステップＳ２１０は、好適には、クエリの第１の予処理を有しており、これはクエリの解析及び整数へのクエリの文字列の変換を有する。整数へのクエリの文字列の変換は、好適には、識別子（例えば、文字列参照データベース１３０）への文字列のマッピングを含むデータベースに文字列（及び潜在的に参照データフィールドといった他のデータ）を渡すことを有する。予処理は、追加的又は代替的に、ユーザ認証の実行、ユーザが使用し易い文字列の分解（例えば、「今」を現在のタイムスタンプに分解する）、クエリツリーの中にＳＱＬタイプのクエリの文字列を解析することを実行することを有する。また、予処理は、好適には、（計算又は構成データベース１６０への参照のいずれかを介して）クエリに関連するデータがどこに存在するのかを分解すること、エラー処理の実行、スケーリング、テーブルジョイン、及び／又はクエリの評価に必要な計算を有する。
【００３９】
ステップＳ２１０は、追加的に、グルーピング及び／又は順序付け機能の特定又は選択を有する。順序付け機能により、好適には、クエリの結果の順序付けを可能にする。順序付け機能は、好適には最終結果に適用されるが、（例えば、順序付けられた結果をクエリステップでの計算に必要な場合）追加的又は代替的に中間結果に適用され得る。グループ化機能により、好適には、クエリの結果のグループ化を可能にする。順序付け機能と同様に、グループ化機能は、好適には最終結果に適用されるが、追加的又は代替的に中間結果に適用され得る。グループ化機能は、追加的にコホート機能を有する。コホート機能は、対象の母集団を一連のコホートに分解するグループ化機能の特定のケースであり、それぞれの対象がちょうど１つのコホートに現れる。
【００４０】
クエリに基づいて第１のデータサンプルを実行することＳ２２０は、ステップＳ２３０で使用すべきデータを特定且つサンプリングする機能を有する。第１のデータサンプルを実行することＳ２２０は、好適には、サンプリングすべきデータを特定することを有する。サンプリングすべきデータの特定は、好適には、所望の信頼区間及び信頼度に基づいてサンプリングすべきデータの特定を有しており、例えば、ある信頼度である信頼区間内であることが望まれる母集団の評価のために選択されるサンプリングすべきデータが、好適にはランダムに選択され、サンプルの数は、このような信頼区間且つ信頼度に要する最小数に対応する。サンプリングすべきデータの特定は、追加的又は代替的に、ノーマルに分布していない及び／又は独立且つランダムな変数から成るものではないと分かっているデータのランダムなサンプリング以外のサンプリングをすることを有する。例えば、データセットが（過去のクエリ又は他のデータソースのいずれかから）特定の分布に従うことが一般に分かっている場合、データセットをその特定の分布にしたがってサンプリングできる。第１のデータサンプリングＳ２２０を実行することはまた、好適には、ステップＳ２３０によって解析すべき第１のデータサンプルを収集することを有する。第１のデータサンプルを収集することは、好適には、分散コンピューティングシステムの多くのノードに含まれる大量のデータ片から小さなサンプルを取得することを有する。これにより、好適には、大量の並列読み出しが同時に生じることが可能となり、時間を節約する。
【００４１】
第１のデータサンプルからクエリの中間結果を計算することＳ２３０は、クエリの結果の第１の評価を与えるよう機能し、その後、それは第２のデータサンプルに向かわせるよう使用され得る。ステップＳ２１０によって処理されるクエリは、好適には、第１のデータサンプルで実行され、クエリの中間結果のセットを決定する。そして、クエリの中間結果は、好適には、第２のデータサンプルを決定するよう使用される。例えば、クエリが、特定のウェブサイトについて過去の月にわたって最も活動的なトップ１００のユーザを特定しようとする場合、第１のデータサンプルを実行することＳ２２０は、ユーザｉｄ及び活動データを含む、多くの分散コンピューティングシステムのノードのデータ片をサンプリングすることを有する。クエリの中間結果を計算することＳ２３０は、それらのデータ片の小さなサンプルから各ノードについてトップユーザを特定することを試み、これらのトップユーザを比較し、データサンプルから見積もられるトップ１０，０００ユーザのリストを見つけ出すことを有する。
【００４２】
クエリの中間結果に基づいて第２のデータ収集を実施することＳ２４０は、Ｓ２３０の結果に基づいてデータを特定且つ収集するよう機能する。第２のデータ収集を実施することＳ２４０は、好適には、クエリの中間結果のためのデータソースを特定し、これらのソースから全ての利用可能なデータを収集することを有する。追加的又は代替的に、Ｓ２４０は、利用可能な全てのデータソースの収集されたサブセットのみを有する。前のセクションの例に言及すると、データソースを特定すること且つ利用可能な全てのデータを収集することは、予想された上位１０，０００ユーザ（データソース）に関連する（問い合わせされた時間枠の中で）全ての活動データを見つけ、Ｓ２５０で計算するためにこの活動データを収集することを有する。
【００４３】
ステップＳ２３０及びＳ２４０は、一連のデータセットに関して繰り返すことが可能であり、例えば、クエリの中間結果を、第３のデータサンプル等を生成するために、第２のデータサンプルから計算し得る。同様に、ステップＳ２５０を任意の適切なデータサンプルに関して実行し得る。
【００４４】
第２のデータサンプルに基づいてクエリの最終結果を計算すること（ステップＳ２５０）は、ステップＳ２４０で特定される第２のデータサンプルに基づいてクエリの結果を判定するよう機能する。クエリの最終結果を計算すること（ステップＳ２５０）は、好適には、第２のデータサンプルに関してＳ２１０によって処理されるクエリを実行し、結果を返すことを有する。クエリの最終結果を計算すること（ステップＳ２５０）は、追加的又は代替的に、信頼区間、信頼度、又はクエリの最終結果の精度に関する他の評価を返すことを有する。
【００４５】
好適な実施方法及びその変形例を、コンピュータが可読な命令を記憶するコンピュータが可読な媒体を受容するよう構成された少なくとも部分的にマシンとして実施及び／又は実行できる。この命令は好適には、好適にはコンピュータシステムと一体となったコンピュータが実行可能な構成要素によって実行される。コンピュータが可読な媒体は、ＲＡＭ、ＲＯＭ、フラッシュメモリ、ＥＥＰＲＯＭ、光デバイス（ＣＤ又はＤＶＤ）、ハードディスクドライブ、フロッピーディスクドライブ、又は任意の適切なデバイスといった、任意の適切なコンピュータが可読な媒体に記憶し得る。コンピュータが実行可能な構成要素は、好適には、汎用の又は特定用途向けのプロセッサであるが、任意の適切な専用のハードウェア又はハードウェア／ファームウェアの組み合わせデバイスが、代替的又は追加的に命令を実行し得る。
【００４６】
当業者は、上記の詳細な説明、図面及び以下の特許請求の範囲の記載から、以下の特許請求の範囲に規定されている本発明の範囲から逸脱することなしに本発明の好適な実施例の変形及び変更をすることができることを認識するであろう。
【図１】
0006307169.tif 000002
【図２】
0006307169.tif 000003
【図３】
0006307169.tif 000004
【図４】
0006307169.tif 000005