(57)【要約】  本発明に従う方法および装置は、時系列データを編成、インデックス付与、検索、およびその検索に基づいて提示する能力を提供する。時系列データはタイムスタンプされたレコードの列であり、１つまたは複数の通常は連続的なストリームで発生し、何らかのタイプのアクティビティを表す。一実施形態では、正規化したタイムスタンプで時系列データを離散的なイベントに編成し、イベントを時間およびキーワードでインデックス付与する。検索を受信し、関連するイベント情報を、全体として、または部分的に、時間インデックス付与機構、キーワードインデックス付与機構、または検索の時点で計算した統計的なインデックスに基づいて取り出す。
2010506311.tif 000002
【特許請求の範囲】
【請求項１】
データを時間検索するためのコンピューター実行型の方法であって、
時系列データストリームを受信するステップと、
前記時系列データストリームをタイムスタンプしてタイムスタンプ付きイベントを生成するステップと、
前記タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成するステップと、
時系列検索要求を受信するステップと、
少なくとも部分的には前記タイムバケット化インデックスを検索することによって、前記時系列検索要求を実行するステップと
を含むことを特徴とする方法。
【請求項２】
時系列データストリームを受信する前記ステップは、時間的に順不同の時系列データストリームを受信するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
時系列データストリームを受信する前記ステップは、２つ以上の物理位置で前記時系列データストリームを収集するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
時系列データストリームをタイムスタンプする前記ステップは、
前記時系列データストリームを集約してイベントを作成するステップと、
前記イベントをタイムスタンプするステップと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
時系列データストリームをタイムスタンプする前記ステップは、
イベントを領域で分類するステップと、
前記イベントをそれらの領域に従ってタイムスタンプするステップと
をさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
イベントをそれらの領域に従ってタイムスタンプする前記ステップは、既知のタイムスタンプ形式で領域に分類したイベントについて、タイムスタンプを前記イベントから抽出するステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項７】
イベントをそれらの領域に従ってタイムスタンプする前記ステップは、既知のタイムスタンプ形式で領域に分類されないイベントについて、タイムスタンプを前記イベントについて補間するステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項８】
タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成する前記ステップは、タイムスタンプ付きイベントをそれらのタイムスタンプに従って複数のタイムバケットに割り当てるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記複数のタイムバケットのうち少なくとも２つは、異なる時間長を有することを特徴とする請求項８に記載の方法。
【請求項１０】
前記複数のタイムバケットを、遅延割当てポリシーを用いてインスタンス化することを特徴とする請求項８に記載の方法。
【請求項１１】
タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成する前記ステップは、前記タイムスタンプ付きイベントをセグメント化するステップをさらに含むことを特徴とする請求項８に記載の方法。
【請求項１２】
タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成する前記ステップは、前記タイムスタンプとセグメントとに基づいてタイムバケット化インデックスを生成するステップをさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
タイムスタンプ付きイベントに時間でインデックス付与する前記ステップは、
検索可能でなく永続的でないホットインデックスを生成するステップと、
検索可能で永続的であるが不変ではないウォームインデックスを生成するステップと、
ホットインデックスをウォームインデックスに適宜変換するステップと
をさらに含むことを特徴とする請求項８に記載の方法。
【請求項１４】
タイムスタンプ付きイベントに時間でインデックス付与する前記ステップは、推測的にインデックス付与するステップをさらに含むことを特徴とする請求項８に記載の方法。
【請求項１５】
前記時系列検索要求を、時系列検索言語で表現することを特徴とする請求項１に記載の方法。
【請求項１６】
時系列検索要求を実行する前記ステップは、メタイベントを生成するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１７】
少なくとも部分的にはタイムバケット化インデックスを検索することによって時系列検索要求を実行する前記ステップは、
異なるタイムバケットについてサブ検索を生成するステップと、
対応するタイムバケット化インデックスにわたって前記サブ検索を実行するステップと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１８】
時間で編成した検索結果を表示するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１９】
時間で編成した検索結果を表示する前記ステップは、ユーザー入力に従って前記表示をズームするステップをさらに含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
前記時系列データストリームは、サーバーログを含むことを特徴とする請求項１に記載の方法。
【請求項２１】
前記時系列データストリームは、トランザクション記録を含むことを特徴とする請求項１に記載の方法。
【請求項２２】
前記時系列データストリームは、記録した測定値を含むことを特徴とする請求項１に記載の方法。
【請求項２３】
データを時間検索するための時系列検索エンジンであって、
時系列データストリームを受信する手段と、
前記時系列データストリームをタイムスタンプしてタイムスタンプ付きイベントを生成する手段と、
前記タイムスタンプ付きイベントを時間でインデックス付与してタイムバケット化インデックスを生成する手段と、
時系列検索要求を受信する手段と、
少なくとも部分的には前記タイムバケット化インデックスを検索することによって、前記時系列検索要求を実行する手段と
を備えたことを特徴とする時系列検索エンジン。
【請求項２４】
時系列データストリームをタイムスタンプする前記手段は、
前記時系列データストリームを集約してイベントを作成する手段と、
前記イベントをタイムスタンプする手段と
をさらに備えたことを特徴とする請求項２３に記載の時系列検索エンジン。
【請求項２５】
時系列データストリームをタイムスタンプする前記手段は、
前記イベントを領域で分類する手段と、
前記イベントをそれらの領域に従ってタイムスタンプする手段と
をさらに備えたことを特徴とする請求項２４に記載の時系列検索エンジン。
【請求項２６】
タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成する前記手段は、タイムスタンプ付きイベントをそれらのタイムスタンプに従って複数のタイムバケットに割り当てる手段をさらに備えたことを特徴とする請求項２３に記載の時系列検索エンジン。
【請求項２７】
前記複数のタイムバケットを、遅延割当てポリシーを用いてインスタンス化することを特徴とする請求項２６に記載の時系列検索エンジン。
【請求項２８】
タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成する前記手段は、前記タイムスタンプ付きイベントをセグメント化する手段をさらに備えたことを特徴とする請求項２６に記載の時系列検索エンジン。
【請求項２９】
タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成する前記手段は、前記タイムスタンプとセグメントとに基づいてタイムバケット化インデックスを生成する手段をさらに備えたことを特徴とする請求項２８に記載の時系列検索エンジン
【請求項３０】
タイムスタンプ付きイベントに時間でインデックス付与する前記手段は、
検索可能でなく永続的でないホットインデックスを生成する手段と、
検索可能で永続的であるが不変ではないウォームインデックスを生成する手段と、
ホットインデックスをウォームインデックスに適宜変換する手段と
をさらに備えたことを特徴とする請求項２６に記載の時系列検索エンジン。
【請求項３１】
少なくとも部分的にはタイムバケット化インデックスを検索することによって時系列検索要求を実行する前記手段は、
異なるタイムバケットに対してサブ検索を生成する手段と、
対応するタイムバケット化インデックスにわたって前記サブ検索を実行する手段と
をさらに備えたことを特徴とする請求項２３に記載の時系列検索エンジン。
【請求項３２】
前記時系列データストリームはサーバーログを備えたことを特徴とする請求項２３に記載の時系列検索エンジン。
【請求項３３】
データを時間検索するためのコンピューター実行型の方法をコンピューターシステムに実行させる命令を記憶するコンピューター読取可能媒体であって、
前記方法は、
時系列データストリームを受信するステップと、
前記時系列データストリームをタイムスタンプしてタイムスタンプ付きイベントを生成するステップと、
前記タイムスタンプ付きイベントに時間でインデックス付与してタイムバケット化インデックスを生成するステップと、
時系列検索要求を受信するステップと、
少なくとも部分的には前記タイムバケット化インデックスを検索することによって、前記時系列検索要求を実行するステップと
を含むことを特徴とするコンピューター読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に情報の編成、検索、および取出しに関し、より具体的には、時系列データの編成、検索、および取出しに関する。
【背景技術】
【０００２】
時系列データは、通常は連続的な１つまたは複数のストリーム内で発生する、タイムスタンプされたレコードの列であり、離散的イベントから成るある種のアクティビティを表す。例としては、情報処理のログ、市場取引、およびリアルタイムなモニター（サプライチェーン、軍事作戦ネットワーク、またはセキュリティシステム）からのセンサーデータがある。関連する検索結果にインデックスを付与できること、関連する検索結果を検索できること、および関連する検索結果を提示できることが、大量の時系列データを発するシステムを理解し、そのシステムで作業するためには重要である。
【０００３】
既存の大規模な検索エンジン（例えば、Ｇｏｏｇｌｅ（登録商標）やヤフー（登録商標）のウェブ検索）は時間依存のより少ないタイプのデータのニーズに取り組むように設計されており、例えば、ウェブ検索インデックス内のＵＲＬ、顧客データベース内のレコード、またはファイルシステムの一部としてのドキュメントのような、データの１つの状態のみをインデックスリポジトリに格納しなければならないとの仮定に基づいて構築されている。情報の検索は、一般に、キーワード検索項目に基づいて情報の１回のコピーのみ、即ち、数日前にインデックスを付したウェブサイトからのＵＲＬの集合、昨日の営業終了時からの顧客記録、または特定のバージョンのドキュメントを取り出す。
【０００４】
一方、図１に示す一般的な情報処理環境からの時系列データの例を考える。ファイアウォール、ルーター、ウェブサーバー、アプリケーションサーバーおよびデータベースは、恐らく毎秒何百または何千回も発生するイベントの形でデータストリームを絶えず生成する。ここで、長い時間にわたる履歴データ値およびデータ変動のパターンは、最新のデータ値と同程度に重要である。既存の検索ソリューションは、一般に時間ベースのインデックス付与および検索、または結果表示中の関連性という概念をほとんど持たず、時系列データのニーズを満たさない。
【０００５】
最も高い関連度（relevance score）でドキュメントを取り出すことが最も効率的であるように、インデックスを編成するフルテキスト検索エンジンと比べて、時系列データを検索するためのエンジンは、あまり最近ではない時間範囲を含めた様々な時間範囲へのアクセスが効率的であるようにインデックスを構成することが望ましい。例えば、多くの現代の検索エンジンと異なり、時系列の検索エンジンが特定のキーワードに対して上位１０００個の結果をキャッシュする利点はほとんどない可能性がある。
【０００６】
他方、時系列データの反復性を考えると、インデックス構築を効率化し、および検索を最適化する機会は有効である。しかしながら、データは複数の異なる情報源から非同期におよび順不同に収集される可能性があるので、時系列データのインデックス付与はさらに複雑である。ある情報源からのデータストリームが１秒古く、別の情報源からのデータが他の情報源にインタリーブされる場合、または他の情報源より数日、数週間、もしくは数ヶ月も古い場合がある。さらに、データソースの時刻が互いに同期しておらず、インデックス付与後に時間オフセットを調整する必要がある場合がある。さらに、タイムスタンプはほぼ無限の数の形式を有することが可能であり、それにより識別および解釈が困難になる。位置、形式、または時間的粒度（例えば、日、時、分、秒、ミリ秒）に対する基準がなければ、データ中のタイムスタンプを発見するのは困難となる恐れがある。
【０００７】
時系列データの検索は、一般に、検索結果を、指定の時間窓（time windows）、並びに頻度、到着時間間隔の分布、および出現または結果の種類の総数など他の時間ベースのメタデータに、効率的に制限する能力を必要とする。キーワードベースの検索は重要性において二次的であるが、時間ベースの検索機構と組み合わせると強力なものになる。時系列データの検索には、検索を表現する全く新しい方法が必要である。今日の検索エンジンにより、ユーザーはデータ中で最も頻繁に現れる項目またはキーワードで検索することができ、一般に時間ベースの検索概念をほとんど持たない。時系列データの大量および反復的な特性を考えると、ユーザーは、時間ベースの検索機構を用いて潜在的な検索結果のセットを絞り込むことから始めて、次にその結果を検証し、１つまたは複数のキーワードを選択して検索パラメータに加える必要がある場合が多い。頻度、分布、および出現の可能性のような時間枠および時間ベースのメタデータは、時系列データを検索するときに特に重要であるが、現在の検索エンジンの手法で実現するのは困難である。例えば、２００５年５月１０日の午前１０時から午前１１時の間の「Ｓｐａｃｅ  Ｓｈｕｔｔｌｅ」に関する全ての記事、または、同じ日の１時間当たりの「Ｓｐａｃｅ  Ｓｈｕｔｔｌｅ」に関する記事の平均数を、ニュースサイトのウェブベースの検索エンジンで見出そうと試みる。データの発生時に焦点を絞った時間ベースの検索機構および検索要求が、時系列データの検索に役立つ。
【０００８】
特定の小規模な領域では、時間ベースの検索の適用が限られているものもある。例えば、電子メールの検索は、多くの主要な電子メールプログラムおよびウェブベースの電子メールサービスで今日利用することができる。しかしながら、検索は前、後、または時間範囲のような単純な時間関数に限られており、データセットは一般に小規模で単一領域から高度に構造化されていて、リアルタイムのインデックス付与機構は追加のみであり、通常は新規のデータをインタリーブするためにインデックス全体を再構築する必要がある。
【０００９】
有用な結果を提示する課題も、時系列データの循環性に特有である。従来の検索エンジンは、一般に結果を、大衆性や共通性で順位付けて提示する。これと対照的に、時系列データに対しては、データパターンおよび頻度の低い出現、または異常な結果に着目できることが重要である場合がある。有用とするためには、時系列検索の結果を時間ベースのパターンおよび振舞いにより編成し、提示できることが望ましいであろう。ユーザーは、複数レベルの粒度（例えば、秒、分、時間、日）および分布（例えば、予期しないまたは最も頻度の低い出現）で結果を参照する機能、ならびに結果セットにわたってパターンおよび振舞いを反映する要約情報を表示する機能を必要とする。他方、既存の検索エンジンは、一般に、最も人気がある結果を最初に表示するために、キーワード密度、使用統計でソートしたテキストの結果、または、ドキュメントおよびウェブページへのリンクもしくはドキュメントおよびウェブページからのリンクを返す。
【００１０】
時系列検索エンジンのある種類では、エンジンがインデックスを付与し、リアルタイムのデータ検索を可能とすることが望ましいであろう。時間データ間の任意の遅延を収集し、検索に利用できる時間を最小化すべきである。大規模で頻繁に変化するデータセットに対してリアルタイムの動作を可能とすることは、高速なデータ可用性を犠牲にして小規模な検索に対する応答時間を最適化する従来の大規模な検索エンジンでは困難となる可能性がある。例えば、ウェブ検索エンジンおよびドキュメント検索エンジンは、一般に種（seed）から始めて、ある特定の時間が経過するか、または収集サイズに達するまでゆっくり進んで（crawl）データを収集する。収集結果のスナップショットは保存され、インデックスが構築、最適化、および格納される。次いで、頻繁にアクセスされるインデックスをキャッシュの仕組みにロードして、検索の応答時間を最適化する。このプロセスは、データセットのサイズおよびインデックスの密度次第で、完了するのに何時間または何日も費やす可能性がある。これを、データ収集時点とデータが検索可能となった時点との間の時間を最小化するよう設計されたリアルタイムの時系列インデックス付与機構と対比する。インデックス構造を再構築せずにインデックスをデータ収集時にオンザフライで挿入、削除および再編成する能力は、時系列データにインデックスを付与し、リアルタイムの検索結果を提供するこの種類の時系列検索エンジンにとって不可欠である。
【００１１】
時系列に着目した他のソフトウェア、例えば、ＳａｗｍｉｌｌまたはＧｏｏｇｌｅのＳａｗｚａｌｌなどのログイベントアナライザーは、リアルタイムの分析機能を提供することができるが、アドホックな検索を提供しないのでそれ自体は検索エンジンではない。任意の分析の前に、レポートを定義して構築しなければならない。さらに、一般的なキーワードベースまたは時間ベースの検索機構を利用することができない。他のストリーミングデータ研究プロジェクト（Ｓｔａｎｆｏｒｄ  ＳｔｒｅａｍｓプロジェクトおよびＳｔｒｅａｍＢａｓｅ  Ｓｙｓｔｅｍｓなどの会社の製品を含む）では、ストリーミングデータの分析および警告を実現することもできるが、永続性のあるデータ、インデックス付与、時間ベースまたはキーワードベースの検索は提供しない。
【００１２】
従って、時系列データからの検索結果をインデックス付与、検索および提示するための他の技術を開発する必要がある。
【発明の概要】
【００１３】
本発明に従う方法および装置は、時系列検索エンジン（ＴＳＳＥ）を用いて、時系列データのインデックス付与、検索、および取出しを可能とすることで、これらおよび他のニーズを解決する。一実施例では、ＴＳＳＥの１つの態様は、検索結果のインデックス付与、検索、および／または提示のための主要な機構として時間を使用することである。時間ベースの検索機構に固有な時系列検索言語（ＴＳＳＬ）を用いて人間が読める形式で検索を表現し、時系列データに固有な相関性アルゴリズムを用いて結果を提示する。検索式および結果提示は、時間窓、頻度、分布、出現パターン、および複数の異種の情報源からの関連する時系列データポイントが含まれるがこれらに限らない、時系列データの検索に重要な主要概念に基づく。
【００１４】
本発明の１つの態様では、複数の情報源の時系列データを検索のために編成およびインデックス付与し、ユーザーまたはマシンが検索を開始すると結果を提示する。別の態様では、時系列検索エンジン（ＴＳＳＥ）は４つの部分、（１）タイムスタンププロセス、（２）インデックス付与プロセス、（３）検索プロセス、および（４）結果提示プロセスを含む。
【００１５】
本発明の１つの態様では、データを時間検索するコンピューター実行方法は、以下のステップを含む。時系列のデータストリームを受信する。時系列データストリームの例としては、サーバーログおよび他の種類のマシンデータ（即ち、マシンが生成したデータ）がある。時系列データストリームにタイムスタンプして、タイムスタンプ付きイベントを生成する。タイムスタンプ付きイベントは、時間のインデックスを付され、タイムバケット化インデックス（time bucketed index）を生成する。当該インデックスは、検索要求を満たすために用いる。少なくとも部分的にはタイムバケット化インデックスを検索することで、時系列検索要求を実行する。
【００１６】
ある特定の実施例では、時系列データストリームにタイムスタンプするステップは、時系列データストリームを集約してイベントを形成し、そのイベントにタイムスタンプするステップを含む。例えば、イベントを領域で分類して、それらの領域に従ってタイムスタンプすることができる。１つの手法では、既知のタイムスタンプ形式で領域に分類したイベントについて、タイムスタンプをそのイベントから抽出する。一方、既知のタイムスタンプ形式で領域に分類されないイベントについては、タイムスタンプを補間する。
【００１７】
本発明の別の態様では、タイムスタンプ付きイベントをそれらのタイムスタンプに従ってタイムバケットに割り当てることで、タイムバケット化インデックスを生成する。様々なバケットポリシーを使用することができる。例えば、タイムバケットは全て同一の時間長（time duration）を有してもよいし、異なる時間長を有してもよい。さらに、タイムバケットを、遅延割当てポリシーを用いてインスタンス化できる。タイムスタンプ付きイベントをセグメント化することもでき、そのセグメントを用いてタイムバケットインデックスを決定できる。ホットインデックス付与（hot indexing）、ウォームインデックス付与（warm indexing）および推測的インデックス付与（speculative indexing）を含む、様々な形態のインデックス付与も使用できる。
【００１８】
タイムバケットインデックスの生成により、時系列検索の実行が促進される。１つの手法では、影響を受けるタイムバケットのために時系列検索要求を様々なサブ検索に分割し、それぞれのサブ検索を対応するタイムバケットインデックスにわたって実行する。
【００１９】
本発明の他の態様は、上述の方法に対応するソフトウェア、コンピューターシステムおよび他の装置、ならびに前述の全てに対するアプリケーションを含む。
【００２０】
本発明は他の利点および機能を有し、それらは以下の発明の詳細な説明および添付の特許請求の範囲を添付の図面とともに考慮するとより容易に明白となるであろう。
【図面の簡単な説明】
【００２１】
【図１】従来技術の時系列データ環境を示す図である。
【図２】本発明に従う時系列検索エンジンを示す図である。
【図３】図２の時系列検索エンジンでの使用に適したタイムスタンププロセスを示す図である。
【図４】図３のタイムスタンププロセスでの使用に適したイベント集約プロセスを示す図である。
【図５】図２の時系列検索エンジンでの使用に適したインデックス付与プロセスを示す図である。
【図６】図２の時系列検索エンジンでの使用に適した検索プロセスを示す図である。
【図７】図２の時系列検索エンジンでの使用に適した結果提示プロセスを示す図である。
【００２２】
本図面は、例示のみの目的のために本発明の実施形態を示す。当業者は、以下の議論から、本明細書で例示した構造および方法の代替的な実施形態を、本明細書で説明している本発明の原理から逸脱することなく利用できることを容易に理解するであろう。
【発明を実施するための形態】
【００２３】
図１に、複数の領域にわたる多数のデータソースと時系列データストリームとを滞在的に有する時系列データ環境の様々な例を示す。この図面では、第１の図に、ウェブサーバー、アプリケーションサーバー、データベースからの時系列データをサーバーログの形で有する情報処理環境を表す。第２の図は、複数の買い手と売り手の間、および２つ以上の市場の間で取引を行う一般的な市場取引環境である。時系列データは、意図もしくは取引または取引の最終決済を例として表すトランザクション記録の形で生成される。第３の図では、記録した測定値の形で時系列データを生成する複数のセンサーを有するリアルタイム監視環境を示す。これらの３つの環境は全て、ＴＳＳＥに対して適用可能な例である。
【００２４】
本発明の態様を図１の第１の図である情報処理環境に関して説明するが、本発明を、図１に示す他の環境を含めた他の時系列データ環境およびアプリケーションで使用することもできる。
【００２５】
図２に、ＴＳＳＥを設計するための１つの手法２００を示す。時系列データストリーム２０５は、複数の情報源から同期的または非同期的に到着し、複数の検索２５５をユーザーおよび／またはシステムが表現し、結果セット２７５を、例えば、アプリケーションプログラミングインターフェースおよびウェブベースのユーザーインターフェースを含む様々な機構を通して提示する。
【００２６】
ＴＳＳＥ２００に時系列データストリーム２０５を直接収集させるか、ユーザー指定のスクリプトに時系列データストリーム２０５を収集させ、前処理させ、およびデフォルトのＴＳＳＥの収集場所にそれらを伝えさせることで、ＴＳＳＥ２００で時系列データストリーム２０５の到着を達成することができる。本アーキテクチャは、遅れて到達するデータおよび時間的に順不同なデータを許容することが望ましい。現状、時系列データの情報源の多くは高度なデータ処理向けに設計されておらず、従ってＴＳＳＥは一般に、原形に近い生の時系列データを収集するか、または提供されることになる。時系列データにアクセスできる限り、ＴＳＳＥを様々な位置に配置することができる。例えば、ＴＳＳＥの１つのコピーを単一の中央コンピューター上で実行することができ、または複数のコピーを、同一の時系列データストリームもしくは異なる時系列データストリームに作用する各コピーを備えるピアツーピアに構成することができる。
【００２７】
図２に、４つの主要なプロセス、タイムスタンププロセス２１０、インデックス付与プロセス２２０、検索プロセス２３０および提示プロセス２４０を有するＴＳＳＥ２００の一例を示す。タイムスタンププロセス２１０は生の時系列データ２０５を、インデックス付与プロセス２２０に提供すべきタイムスタンプ付きイベント２１５に変換する。本発明の情報処理例に従って、複数のウェブサーバー、アプリケーションサーバーおよびデータベースからの生のログ２０５をタイムスタンププロセス２１０で処理して、様々なログ形式中の個々のイベント２１５を識別し、時間および他のイベントデータを正確に抽出することができる。当該イベントデータ２１５をインデックス付与プロセス２２０で使用して、そのイベントのタイムバケット化インデックス２２５を構築する。これらのインデックス２２５を検索プロセス２３０で利用する。当該検索プロセス２３０は、ユーザーまたはシステムから検索２２５を受け継ぎ、その検索を分解して、インデックス集合にわたって検索を実行する。
【００２８】
例えば、ユーザーは特定のウェブサーバーおよび特定のアプリケーションサーバーからの、直前の１時間以内に発生し特定のＩＰアドレスを含む全てのイベントを確認するといいかもしれない。さらに、検索プロセス２３０は、反復的な時間データを通した検索に有用な時間ベースのおよび統計に基づく要約インデックスを処理するために、検索時にメタイベント２３７の作成を開始することを選ぶことができる。例えば、メタイベント２３７は、実際のイベントの平均値、中間値もしくは数、またはより高度なパターンベースの振舞いを表すことができる。この場合、ユーザーは毎分３回の頻度で発生する全てのイベントを見つけるために検索するといいかもしれない。
【００２９】
完了後、検索プロセス２３０は、選択したインデックス２３５からの結果を提示プロセス２４０に渡す。当該提示プロセス２４０は結果セットをマージし、結果を順位付け、結果２７５を提示用のＡＰＩまたはユーザーインターフェースに提供する。
【００３０】
（Ｉ．  タイムスタンププロセス）
図２に示す、ＴＳＳＥの例示的な実施例２００のプロセス２１０は、ストリーミング時系列データを取得し、そのストリーム中の個々のイベントを識別し、タイムスタンプをそれぞれのイベントに割り当てる。タイムスタンププロセス２１０のブロック図の例を図３に示す。当該タイプスタンププロセス２１０は、イベント集約３１０、領域識別３２０、時間抽出３３０、および時間補間３４０を含むいくつかのステップを含む。時系列データストリーム２０５をタイムスタンププロセス２１０への入力として受け取り、次に個々のタイムスタンプ付きイベント２１５に加工する。
【００３１】
（Ｉ．Ａ  イベント集約）
図３のタイムスタンププロセス２１０におけるステップ３１０は、ストリーミング時系列データ２０５を収集して個々のイベント３１５を形成する。本発明の情報処理の例では、ウェブサーバーの時系列データストリームはイベント当り単一の行を有することができ、識別が簡単である。しかしながら、アプリケーションサーバーの時系列データストリームは、多数の行を伴う単一のイベントを含むことができるため、そのストリーム中で個々のイベントを識別することは困難となる。
【００３２】
一実施例では、イベント集約３１０は特徴抽出（例えば、先頭の句読点、重要な単語、空白、および改行文字）および機械学習アルゴリズムを用いて、イベント境界の場所を判定する。図４は、図３のタイムスタンププロセスでの使用に適したイベント集約プロセスの図である。
【００３３】
（Ｉ．Ａ．１  情報源識別〜領域への分類）
本発明の情報処理の例（本例ではデータをマシンデータ２０５またはＭＤ２０５と呼ぶ）における時系列データ２０５の反復的であるにもかかわらず動的な性質を考えると、（図４に示すような）効果的な集約プロセス３１０がデータの形式および構造について自動的に学習することが望ましい。一実施例では、学習をＭＤ２０５の情報源に基づいて様々な領域に分ける。領域は、ログファイル、メッセージバストラフィック（message bus traffic）、およびネットワーク管理データなどの一般的なシステムタイプ、または、Ｓｅｎｄｍａｉｌ（登録商標）のロギングデータ、Ｏｒａｃｌｅ（登録商標）データベースの監査データ、およびＪ２ＥＥメッセージングといった所与のアプリケーションもしくは技術の出力などの特定のタイプとすることができる。
【００３４】
この例のイベント集約プロセス３１０では、領域固有な編成方法を適用できるように、所与のＭＤの情報源について領域を識別する（４１５）。領域は学習プロセスを通して決定する。学習プロセスでは、周知の領域からのＭＤ集合を入力として使用し、それぞれの領域に対して情報源署名４１２を生成する。一実施例では、句読文字をそれらの頻度にマッピングするハッシュテーブルを生成することで、ＭＤ２０５の代表的なサンプルから情報源署名４１２を生成する。トークンやトークン値はＭＤ集合内で変化する可能性があるが、この特定の実施例では、句読点の頻度により生成した署名４１２は特定の領域内で非常に安定しており、および信頼性がある。他の実施例では、行の最初に句読文字が現れる頻度または行の最初に大文字が現れる頻度などの、句読点およびトークンの関数を使用することができる。情報源署名４１２が大規模および判読困難である可能性がある場合、署名は、機械が生成したまたは人間が割当てた数字またはテキストの形式で対応するラベルを持つことができる。例えば、Ａｐａｃｈｅウェブサーバーのログに対する情報源署名４１２にラベル「２０５」をプログラム的に割り当てることができ、またはユーザーがラベル「Ａｐａｃｈｅ  Ｓｅｒｖｅｒ  Ｌｏｇ」を割り当てることができる。
【００３５】
一実施形態では、クラスタリングを用いて、収集したＭＤ２０５をそれらの情報源署名４１２に従って領域に分類する（４１５）。ＭＤ２０５の集合に遭遇すると、最近傍検索を実行することにより、各集合の署名を既知の情報源署名４１２のセットと照合する。最も近いマッチング署名４１２の距離が閾値内にある場合、最も近いマッチング署名４２０の領域はその情報源の領域であると考えられる。最もマッチするものが見つからない場合、新たな情報源署名４１２をサンプル署名から生成することができ、それにより新たな情報源領域が生成される。あるいは、デフォルトの情報源領域を使用することができる。一実施例では、２つの署名間の距離を、署名距離の合計がそれぞれの属性に対する距離の平均となるように、その２つの署名の属性の和集合にわたって反復することで計算する。それぞれの属性Ａに対して、署名１および署名２上のＡの値、Ｖ１およびＶ２を比較して距離を計算する。属性Ａに対する距離は（Ｖ１−Ｖ２）＊ＩＤＦの平方である。ここで、ＩＤＦはｌｏｇ（Ｎ／｜Ａ｜）、Ｎは署名の数、および｜Ａ｜は属性Ａを伴う署名の数である。
【００３６】
（Ｉ．Ａ．２  情報源識別〜テキスト／バイナリに分類）
いくつかのＭＤ２０５情報源は、非テキストまたはバイナリであり、バイナリＭＤをテキスト形式に変換することが可能である既知のプロセスが利用できない限り、容易に処理することはできない。情報源をテキストまたはバイナリに分類するために、サンプルのＭＤ集合を分析する。テキストのＭＤには、メモリーダンプなどのバイナリＭＤが埋め込まれている可能性もあり、本分類でそれをそのように識別することが望ましい。一実施例では、テキスト／バイナリ分類は以下のように動作する。サンプルはデータの行セットであり、行は改行（即ち‘＼ｎ’）、キャリッジリターン（即ち、‘＼ｒ’）、またはそれらの組合せ（即ち、‘＼ｒ＼ｎ’）の間にあるデータとして定義される。それぞれの行に対し、行の長さが２キロバイトの文字などの、何らかの広い閾値より長い場合、または行が零（０）のアスキー（ＡＳＣＩＩ）値の文字を含む場合、バイナリとみられる行のカウントを進める。そうでなく、行の長さが、２５６文字などの、一般に多くのテキスト行が下回ると期待されるであろう長さより短い場合、テキストとみられる行のカウントを進める。テキストとみられる行の数がバイナリとみられる行の２倍である（状況により他の比率を使用することができる）場合、情報源をテキストに分類する。そうでなければ、情報源をバイナリに分類する。
【００３７】
（Ｉ．Ａ．３  マシンデータを集約して生のイベントを作成）
ＭＤの集合について情報源署名４２０を識別すると（４１５）、対応する集約規則をそのＭＤ集合に適用する（４２５）。集約規則には、ＭＤ集合中のイベントの境界を識別することでＭＤ２０５を特定の領域からイベントデータ３１５に編成する（４２５）方法、例えば、離散的イベントの開始と終了を見つけることでそのイベントの場所を見つける方法が記載されている。一実施例では、集約４２５の方法は、事前の知識なしに、ＭＤ２０５のサンプルから複数行をグループ化することで学習する。多くの場合、ＭＤ２０５は、何らかの方法で論理的にグループ化された１行から何百行の間のどこかにあるイベント３１５を含む。
【００３８】
ＭＤ集合は事前に既知とすることができ、または集約を実行する前に単一行タイプ（即ち、単一行のイベントのみを含む）もしくは複数行タイプ（即ち、複数行のイベントを含む可能性がある）に分類することができる。単一行タイプに分類したこれらのＭＤ集合に対し、集約４２５は単純であり、単一行タイプのＭＤ集合を各行で別々のイベントとして分ける。複数行タイプのＭＤ集合を集約のために処理する（４２５）。一実施例では、１）大部分が空白で始まるか、またはブランクである場合（例えば、５％を超える行が空白で始まるか、またはブランクである場合）、または２）最初のＮ個の句読文字に含まれる句読文字の種類が多すぎる場合、ＭＤ集合を複数行タイプに分類する。例えば、各行で見つかった最初の３つの句読文字から成るセットが５個のパターン（例えば、‘:::’、‘!:!’、‘,,,’、‘:..’、‘()*’）を超えるパターンを有する場合、その集合を複数行に分類することができる。
【００３９】
集約方法４２５の別の態様は、ＭＤのサンプルを分析することで、行間の改行を構成し、従ってイベント間の境界を構成するものを学習し、規則に体系化する機能である。例えば、一実施例では、集約方法４２５は、全ての２行から成る組を比較して統計的に類似な構造（例えば、空白、インデント、およびタイムスタンプの使用）を探し、どの２つがグループを成し、どの２つが独立であるかを迅速に学習する。一実施例では、集約４２５は以下のように動作する。それぞれの行に対し、行がタイムスタンプで開始するかどうかを最初にチェックする。タイムスタンプで開始する場合、改行する。一般に、タイムスタンプで始まる行は新たなイベントの始まりである。タイムスタンプで始まらない行に対して、現在の行を直前の行と結合して、どのくらいの頻度で行の組が連続して生ずるかを、ＭＤサンプルにおける全ての組の割合として調べる。行署名がより安定した行のバージョンであり、単純な数字およびテキストの変更の影響を受けない場合は、行署名を行の代わりに使用する。本実施例では、先頭の空白、行の任意の句読点、および行の最初の単語を連結した文字列へ行を変換することで、署名を生成することができる。行「10:29:03 Host 191.168.0.1 rebooting:normally」は「::..:Host」に変換される。
【００４０】
ここで、現在の行署名を直前の行署名と連結し（即ち、署名１を署名２と結合）、改行規則テーブルへの結合キーとして使用することができる。改行規則テーブルは、結合キーを改行規則にマッピングする。当該改行規則は、２つの行の間に「改行」があるべきか否か（即ち、それらの行が異なるイベントの一部であるか否か）を決定する。改行規則は信頼性レベルを有することができ、より信頼の高い規則で信頼の低い規則をオーバーライドすることができる。２つの行の共起データを分析し、それらの署名が隣接して発生する時間の割合を分析することで、改行規則を自動的に生成することができる。２つの行署名が極めて同時に発生する場合、新たな規則ではそれらの間の改行は提示されないであろう。あるいは、それらが稀にしか同時に発生しない場合、新たな規則ではそれらの間の改行が提示されるであろう。例えば、時間Ａの２０%を超えて行署名Ｂが行署名Ａに続く場合、それらの間の改行を提示しない改行規則を生成することができる。規則を、別の行署名に後続／先行する行署名の生の数に基づいて生成することもできる。例えば、行署名に大体１０個の異なる行署名が続く場合、それらの間の改行を提示する規則が生成される。改行規則テーブル内に改行規則がない場合、デフォルトの振舞いは、２つの行を改行してそれらが異なるイベントからのものであると仮定することである。各２行から成る組を処理し、行署名と共起の統計値とを更新し、対応する改行規則を適用および学習することで処理を進める。一定の間隔で、改行規則テーブルはハードディスクまたは永久記憶媒体に書き出される。
【００４１】
（Ｉ．Ｂ  タイムスタンプの識別）
入力時系列ストリーム２０５を集約して個々のイベント３１５を作成すると（３１０）、そのイベントおよびそれらのイベントデータがタイムスタンプ識別ステップ３２０に入力される。当該ステップは、時系列イベントデータが、既知のタイムスタンプ形式集合の１つと適合するトークンを含むか否かを判定する。適合するトークンを含む場合、イベントは既知の領域からのタイムスタンプを有すると考えられ、抽出３３０を実行する。そうでなければ、補間３４０を実行する。
【００４２】
（Ｉ．Ｃ  タイムスタンプの抽出）
イベントについて既知の領域が識別された場合、イベント３１５をタイムスタンプ抽出ステップ３３０への入力とみなす。当該ステップで、生のイベントデータからのタイムスタンプを抽出し、そのイベントとともにインデックス付与プロセス２２０に渡す。例示的な実施例では、このタイムスタンプ抽出３３０は、閏秒を含まないＵＮＩＸ（登録商標）エポック（協定世界時  １９７０年１月１日０時０分０秒）から経過してきた秒数として記録すべき時刻を抽出するために、動的に順序付けたリストから潜在的なタイムスタンプの形式パターンにわたって反復することで行われる。さらに、本実施例ではタイムゾーン情報を考慮しており、時刻を共通オフセットに正規化する。性能を上げるためには、本リストの順序を、先頭移動（move-to-front）アルゴリズムを用いて決定する。当該アルゴリズムでは、一致が見つかると常に、マッチングパターンをリストの先頭に移動する。このような実施例では、最も頻繁に出現するパターンを最も早く、および最も頻繁にチェックし、性能が向上する。先頭移動リストを、（単一情報源内の形式は類似する可能性が高いという事実を利用して）情報源毎に全ての時系列データソースに対して一緒に、または他の何らかの配列で、維持することができる。
【００４３】
（Ｉ．Ｄ  タイムスタンプの補間）
イベントが既知の領域からのタイムスタンプを含まなかった場合、タイムスタンプをそのコンテクストに基づいてイベントに割り当てる。一実施例では、タイムスタンプを、同一の時系列データストリーム内の直前および直後のイベント３１５のタイムスタンプから線形に補間する（３４０）。これらのイベントも既知の領域からのタイムスタンプを含まない場合、さらに前のおよび／または後のイベントを補間に使用することができる。タイムスタンプ抽出モジュール３３０は、それぞれの時系列データストリームから、１００番目のイベント毎（または何らかの他の設定可能な期間毎）のタイムスタンプを自動的に格納して、タイムスタンプの補間３４０を促進する。別の実施例では、取得時刻、生成時刻、または状況に依存した他のメタ時刻データを含む全体の時系列データストリーム２０５に関連する時刻に基づいて、タイムスタンプを補間する（３４０）。
【００４４】
（ＩＩ．インデックス付与プロセス）
図２に戻る。インデックス付与プロセス２２０において、インデックスを入力イベントデータ２１５に基づいて作成する。インデックス付与プロセス２２０はインデックスのセットを、それらが多数のイベントで拡張されているためオンラインで編成および最適化する。ＴＳＳＥのインデックス付与プロセス２２０の一例を図５に示す。一実施例では、当該インデックス付与プロセス２２０は、バケット化５１０、セグメント化５２０、アーカイブ化５３０、割当て５４０、挿入５５０、２次記憶装置へのコミット５６０、２次記憶装置内のバケットのマージ５７０、および２次記憶装置内のバケットの失効５８０を含む、いくつかのステップを含む。
【００４５】
（ＩＩ．Ａ  タイムバケット化）
ＴＳＳＥでインデックスを付したイベントを、多くの場合、時間ベースの演算子を用いて問合せ、更新、および失効する。時間で編成した一連のバケットにわたってインデックスの構成要素をハッシュすることで、これらの演算子の効率および性能を大幅に改善することができる。バケット化の最終的な効率は、もちろん、ハードウェア構成、イベントが到着する順序、およびそれらの問合せ方法に依存し、従って、単一の完全なバケット化ポリシーは存在しない。
【００４６】
一実施例では、均一な範囲を有するバケットを使用する。例えば、それぞれのタイムバケットは１時間のデータ量を処理することができる。代替的なポリシーは、バケットの範囲をある期間から別の期間に変更することができる。例えば、今日より前のイベントに対するバケットは３時間のバケットであるが、直前の２４時間の間に発生するイベントに対するバケットはその時間でハッシュされることを、バケットポリシーは指定することができる。情報処理の例では、バケットは２００５年１月１５日１２時０分０秒から２００５年１月１５日１４時５９分５９秒までの期間をカバーすることができる。効率性をさらに改善するため、主メモリー（即ち、ＲＡＭ）内で遅延割当てポリシー（即ち、可能な限り遅い）を用いてバケットをインスタンス化する。メモリー内のバケットは最大容量を有し、バケットがそれらの限界に達すると、バケットをディスクにコミットし、新たなバケットで置き換える。バケットの記憶容量はバケット化ポリシーの別の要素であり、時間範囲の大きさとともに変化する。最後に、バケットポリシーは、一般に、バケットが（ａ）重複しないこと、および（ｂ）全ての可能な入力タイムスタンプをカバーすることを強制する。
【００４７】
時間でイベントにインデックスを付与するステップ５１０は、イベントについて適切なバケットを、そのイベントのタイムスタンプおよびそのインデックスのバケット化ポリシーに基づいて識別する。それぞれの入力イベント２１５を、イベントからのタイムスタンプがバケットの時間的基準と適合するタイムバケットに割り当てる（５１０）。一実施例では、半開区間を用いる。当該半開区間は、開始時間と終了時間とで定義し、開始時間は閉じた境界であり、終了時刻は開いた境界である。バケットの境界で発生するイベントを一意にバケットに割り当てるために、これを行う。情報処理環境において本例に従うと、２００５年１月１５日１２時０分１秒のタイムスタンプを有するデータベースサーバーイベントを上述のバケットに割り当てることができる。
【００４８】
（ＩＩ．Ｂ  セグメント化）
イベントについて適切なバケットを識別した後（５１０）、生のイベントデータをセグメント化する（５２０）。セグメント（トークンとしても知られている）は入力イベントテキストの部分文字列であり、セグメント化５２０とは、入力イベントデータ上のセグメント化アルゴリズムにより示唆されるセグメントの集合である。セグメントの部分文字列は別の部分文字列と重複することができるが、重複する場合は、その重複部分はその部分文字列に完全に含まれなければならない。セグメント階層が入力テキスト上でツリーを形成するように、この特性を、包含する部分文字列に再帰的に適用可能としている。
【００４９】
一実施例では、副改行子（minor breaker）および正改行子（major breaker）と呼ぶ２つの相互排他的な文字セットを選ぶことでセグメント化５２０を行う。生データのセグメント化中に改行文字に遭遇するときは常に、正副に関わらず、少なくとも１つの正改行子をその一方の端に有する任意のバイトシーケンスに対応するセグメントを生成する。例えば、セグメント化中に副改行文字を発見すると、今遭遇した副改行子から直前に遭遇した正改行子に至る文字列に対応するセグメントを記録する。正改行子に遭遇した場合、直前の正改行子または直前の副改行子の何れかに戻る文字列が、どちらが直近に発生したかに関わらず、記録すべき次のセグメントを決める。
【００５０】
セグメント化５２０の規則には、イベントデータをセグメント５２５（トークンとしても知られる）に分割する方法が記載されている。一実施例では、セグメント化規則により、例えばカンマ、空白、またはセミコロンなどの、イベント内で可能なセパレータまたは句読点を検証する。セグメント化の重要な態様は、個々のセグメント５２５だけでなく、重複するセグメントも識別する能力である。例えば、電子メールアドレスのテキスト、「bob.smith@corp.com」を独立した重複セグメントに分解し、＜bob.smith＞、＜@＞および＜corp.com＞を独立したセグメントとして識別し、＜＜bob.smith＞＜@＞＜corp.com＞＞も重複セグメントとして識別することができる。上述のように、一実施例では、セグメント化５２０は正および副の改行の２段のシステムを使用する。正の改行は、大部分のセグメント５２５の外の境界を示すセパレータまたは句読点である。例としては、空白、タブ、および復帰改行がある。副の改行は、例えばピリオド、カンマ、および等号などの、大きなセグメントを部分セグメントに分割するセパレータまたは句読点である。一実施例では、より複雑なセパレータおよび句読点の組合せを使用して、例えば、アプリケーションサーバーログファイル内のＪａｖａ（登録商標）の例外処理など、複雑なセグメント化作業５２０を処理する。
【００５１】
本発明の情報処理の例におけるセグメント化の例で、ＩＰアドレスを、正改行子として空白を用い、および副改行子としてピリオドを用いて分解することができる。従って、生のテキスト「192.168.1.1」に対するセグメントは以下のようになる。  
「192」
「192.168」
「192.168.1」
「192.168.1.1」
【００５２】
別の実施例では、ある特定のセグメントにより既知のエンティティを表すことができる。そのエンティティにラベル付けして、エンティティをアルゴリズム的に、または人間が追加した意味により理解することができる。例えば、上の表現では、「192.168.1.1」をＩＰアドレスと理解することができる。名前付きエンティティ抽出を、いくつかの方法でアルゴリズム的に実施することができる。一実施例では、複数のイベントにわたる同一のセグメントからのセグメント値またはセグメント形式を、既知の値または既知の形式から成るエンティティ辞書と比較する。
【００５３】
別の実施例では、エンティティ抽出技術を使用してデータ中の意味エンティティを識別する。一実施例では、検索木または正規表現を適用して、例えばＩＰアドレスまたは電子メールアドレスを抽出し、検証することができる。抽出の目標は、セグメント化プロセス５２０を支援し、データに意味値を与えることである。
【００５４】
（ＩＩ．Ｃ  イベントのアーカイブ化とインデックス付与）
プロセスのこの時点で、入力イベントは、それらに関連するタイムスタンプ２１５、セグメント５２５およびタイムバケット５１５を有する。検索プロセスにおいて探索を行うために後で用いる永続的なデータ構造を生成するため、本発明ではセグメント化を伴うイベントの生データを格納し、セグメントおよびタイムスタンプをイベントデータストア内のオフセットにマッピングするインデックスを生成し、そのインデックスに関連するメタデータを計算および格納する。
【００５５】
ＴＳＳＥは新たなイベントの到着および新たな検索の到着の両方をほぼリアルタイムで許容するので、システムはディスクへのアクセス管理に注意することが望ましい。インデックスに対して、これはインデックス生成を２つの別々なフェーズ、即ちホットインデックス付与およびウォームインデックス付与に分割することで実現される。ホットインデックスは、全体としてＲＡＭで管理され、最小の挿入可能時間に対して最適化され、検索可能ではなく、および持続しない。「ウォーム」インデックスは、検索可能で永続的であるが、不変である。ホットインデックスを検索可能とする必要があるか、または永続的とする必要があるときは、それらをウォームインデックスに変換する。
【００５６】
図５に示す実施例では、ホットインデックス５５５は、セグメントのパック配列（packed array）、イベントアドレスとそれらの関連するタイムスタンプとのパック配列、およびセグメントをそれらのタイムスタンプ付きイベントアドレスに関連付けるポスティングリストを含む。性能上の理由から、パック配列は、重複の迅速な除去を提供するために、それらに関連付けられたハッシュテーブルを有することができる。入力イベントにインデックス付与しているとき、セグメント配列とその関連ハッシュとを用いて、イベントのそれぞれのセグメントを重複がないかどうかテストする。イベントアドレス配列およびその関連ハッシュと対照して、イベントアドレスも重複がないかどうかテストする。属性の何れかが複製である場合、パック配列に挿入済みであるその複製インスタンスを使用する。そうでなければ、新たなセグメントまたはイベントアドレスを適切なテーブル５５０にコピーし、関連ハッシュテーブルを更新する。イベントをホットインデックスに挿入すると、パック配列の各々に関連する空白が使用される。ホットスライス（hot slice）は、そのパック配列の１つが満杯であるとき、またはそのハッシュテーブルの１つが利用閾値を超過するとき（例えば、ハッシュテーブルの半分を超える部分が使用中の場合）、「フル稼働」であると考えられる。ホットインデックスが容量に達すると（５４０）、インデックス付与のセグメントをそれ以上受け入れることができない。その代わり、そのホットインデックスをウォームインデックスに変換し、ディスクにコミットし（５６０）、新たな空のホットインデックスで置き換える。
【００５７】
この特定のシステムの別の機能は、推測的インデックス付与である。前述のインデックス付与プロセスに基づいて、代表的で完全なバケットの全部または一部を例として用いて新たなタイムバケットを初期化することができる。換言すれば、タイムバケット内で発生すると合理的に期待できるデータのコピーを保持し続け、ホットインデックスの一部を推測的に初期化することで、インデックス付与の性能を改善することができる。一実施形態では、セグメントのパック配列およびその関連するハッシュテーブルを以前のホットインデックスからコピーすることで、推測的インデックス付与を行う。次に、セグメント配列が既に投入されていて重複がないかどうかテストする準備ができている場合を除いて、ホットスライスを通常通りに投入する。正規言語が高度であり、マシンの語彙が有限であるため、この推測に関するヒット率は非常に良いものになる可能性がある。
【００５８】
（次のセクションで説明するように）検索プロセスにより、ユーザーはセグメント、セグメントプレフィックス、およびセグメントサフィックスで検索することができる。これらの検索タイプに対応するため、一実施例では、セグメント配列をソートしてブロックフロント符号化辞書（blocked front coded lexicon）（以降、「前方辞書」と呼ぶ）として格納することができる。このデータ構造により、十分な量のセグメントテキスト圧縮をなお実現しつつ、セグメントおよびセグメントプレフィックスの検索を効率的に実施することができる。検索を特定のセグメント上で実施しているとき、前方辞書内のセグメントのオフセットを、他の関連テーブル内の問合せたセグメントに関連するメタデータを検索する効率的な方法として使用する。
【００５９】
サフィックス検索を扱うため、同一のセグメント集合上で、それらのセグメントを文字列反転した後にブロックフロント符号化辞書（以降、「反転辞書」と呼ぶ）を生成することができる。また、反転辞書内の反転セグメントのオフセットを前方辞書内の等価な非反転セグメントのオフセットに変換するマップ（以降、「反転前方マップ」と呼ぶ）を埋める。サフィックス検索を実施するとき、反転辞書内のオフセットを反転前方マップへのオフセットとして使用する。マップ内のその位置に格納した値は、ウォームインデックス内の他のメタデータ配列に使用するのに適したオフセットである。
【００６０】
効率的な方法において、ウォームインデックスは、インデックス付与したそれぞれのセグメントにイベントオフセットのリストを提供することが望ましい。一実施例では、これは、圧縮したポスティングリストの配列と、これらの圧縮したポスティングリストの各々の先頭に対するオフセットから成る関連配列とを維持することで行うことができる。ポスティングリストはセグメントのオフセットの順序で維持され、従って検索を実施するとき、セグメントＩＤを使用してポスティングリストオフセット配列の適切なエントリーを見つけることができる。ポスティングリストエントリー内の値は、イベントアドレスのパック配列内でイベントを検索するために使用すべきオフセットである。
【００６１】
最後に、統計メタデータ（例えば、セグメントの最初と最後の発生時刻、平均到着時間間隔、および到着時間間隔の標準偏差）をそれぞれのインデックス付与したセグメントに提供することができる。
【００６２】
インデックス付与プロセスの過程で、単一のタイムバケットを満杯にしてディスク５６０にコミットすることを数回行うことが可能である。この結果、単一の期間に対して、複数の、独立に検索可能なインデックスが２次記憶に生成される。例示的な実施例では、２つ以上のウォームインデックスを入力として取り、それらをそのタイムバケットに対する単一のウォームインデックスにマージするマージプロセス５７０がある。これは性能を最適化するものであり、厳密には検索に対して必要ではない。
【００６３】
（ＩＩ．Ｄ  イベントの失効）
さらに、長期間にわたって、インデックス付与プロセス２２０を時系列データに適用することで、大量の永続的なデータが蓄積する可能性がある。従って、削除すべきタイムバケットに対して、ユーザーが与えた設定（preference）に基づいてデータベースを監視する失効処理プロセス５８０をインデックス付与プロセスが含むことが望ましい。一実施例では、これらの設定は、後続の（trailing）時間窓（「３ヶ月より古いイベントは検索結果で返す必要はない」）、時間範囲（「今年の１月１日より前のイベントは検索結果で返す必要はない」）、イベントの最大数（「１００万個を超えないイベントを検索結果で返す必要がある」）、またはインデックスに対する最大合計サイズ（「ディスクの消費量が１００ＧＢを超えない間は可能な限り多くの有用な検索結果を返す」）を含むことができる。失効基準を満たす任意のスライスに対して、プロセスは定期的にウォームスライス集合を起動してテストする。失効すると、ウォームインデックスファイルと、その関連する生のイベントデータおよびセグメントとをアクティブなインデックスから移す。インデックスファイルを必ずしも削除する必要はない。一実施例では、インデックスファイルをより費用のかからないオフライン記憶装置に配信する（stream）ことができる。
【００６４】
（ＩＩＩ．検索プロセス）
例示的なＴＳＳＥの検索プロセスを図６に示す。本プロセスは、検索句を解析し（６１０）、入力の親検索を満たすために複数のサブ検索６２５を発行し、サブ検索結果６３５を用いて検索を削り、ユーザーに提示するための最終的な検索結果セットにサブ検索結果をマージする（６４０）ためのいくつかの方法を含む。
【００６５】
（ＩＩＩ．Ａ  時系列検索言語）
検索処理中に、入力の検索句２５５を時系列検索言語（ＴＳＳＬ）に従って解析して（６１０）、注釈付き解析木６１５を生成する。例示的なＴＳＳＬ言語構文は、名前：：値の形式を取る一連の修飾子またはコマンドを含む。いくつかの修飾子はデフォルトの値を有してもよく、いくつかの修飾子は一度だけ使用することができ、一方でいくつかの修飾子は異なる値での同一検索において数回出現することができる。構文の例としては、以下がある。  
average::value−値、時間フレームを用いてイベントの平均数を計算する。  
page::value−検索結果を値で提示する。値は秒、分、時間、日、週もしくは月、または、例えば情報源もしくはイベントタイプなど、他の任意のメタデータ要素とすることができる。  
count：：−イベントの全数を計算する。  
daysago：：value−直前の値、数日以内のイベントを検索する。  
Index::value−検索するためのインデックス−主要、デフォルト、履歴、または別のインデックスがあり、ＴＳＳＥにより定義される。  
hoursago::value−直前の値、数時間以内のイベントを検索する。  
eventtype::value−指定値に適合するイベントタイプまたはタグを有するイベントを検索する。  
host::value−ホスト名が指定値にセットされたイベントを検索する。これは、イベントを記録したホストであり、必ずしもイベントを生成したホストではない。  
maxresults::value−返すべき結果の最大数。  
minutesago::value−直前の値、数分以内のイベントを検索する。  
Related::value−現在のイベントにおいて１つまたは複数に適合するセグメント値（例えば、４０４またはユーザー名）を有するイベントを検索する。  
similar::value−現在のイベントに類似するイベントタイプを有するイベントを検索する。  
sourcetype::value−所与の情報源タイプの値を有するイベントを検索する。  
unexpected::value−０（想定内）から９（最も予測外）の規定値により、インデックス内で観測されたパターン以外のイベントを検索する。
【００６６】
修飾子をキーワード、ワイルドカード文字、リテラル文字列、引用句および、ＡＮＤ、ＯＲ、ＮＯＴなどのブール演算子と組み合わせることができる。括弧を用いて検索句およびサブ検索句をともに入れ子にすることができる。例示的な検索句として、「sourcetype::mysql*sock*NOT（started OR （host::foo OR host::BAR））maxresults::10（eventtype::baddb OR eventtype::?8152-3）daysago::30」があり得る。
【００６７】
一実施例では、カスタムパーサー６１０は、ブール演算子「ＮＯＴ」および「ＯＲ」ならびにデフォルトとして「ＡＮＤ」を扱う。本実施例では括弧も使用し、いくつかの演算子がある際の言語の曖昧さを解消する。括弧がない場合は、演算子は左から右に結合する。本実施例では、境界要素が続く領域識別子を用いて表した特殊な検索演算子もサポートする。例えば、「source::1234」の検索では、特定の情報源ＩＤから受信したイベントに結果を制限することを検索者（人間またはシステム）が望むことを示すことができる。
【００６８】
入力の検索句は、特殊なキーワードのマップに基づいてアドホック計算６１２のトリガーとなることもできる。例えば、特殊な検索文字列を用いて、検索が定期的に格納および再発行され、情報源リストを必要とすることを示すことができる。この場合は、検索の再発行すべきスケジュールを指定するスケジュールとともに、検索文字列がディスク上のテーブルに記憶されるであろう。実行時の検索結果に依存して、追加の動作のトリガーとなることもできる。例えば、電子メールによる警告の送信、ＲＳＳフィードの更新、またはユーザー提供のスクリプトの実行を行うことができる。アドホック計算６１２のトリガーとなる検索の別の例として、後の使用向けに保存するが定期的には再発行しないと指示されるものがある。
【００６９】
注釈付き構文木６１５を検索文字列に対して生成すべきことを検索パーサー６１０が判定すると仮定すると、次の構成要素である検索実行エンジン６２０は注釈付き構文木６１５を用いてサブ検索６２５をタイムバケット化インデックス５６５に発行する。それぞれのサブ検索６２５が、個々のタイムバケット５６５を対象とする。結果のソート順序が与えられると、プルーニング（pruning）に最も有利な順序でタイムバケットを問い合わせる。例えば、検索結果を逆年代順でソートする場合、直近のタイムバケットに対するサブ検索が最初に発行される。これにより、検索実行エンジン６２０は、追加の（コストが高い）サブ検索６２５へ進む前に、サブ検索の結果６３５を検査することができる。例えば、特定のサブ検索が十分な結果６３５を返す場合は、追加のサブ検索６２５へ進む必要はない。
【００７０】
親検索を満足する十分な結果セット６３７が蓄積されると、別のモジュールがその結果を取って、その検索を満足する単一の結果セット２３５、２３７にマージする（６４０）。一実施例では、このマージプロセスはマージソートをバケットの各々からの結果に対して実施して、それらを提示プロセスに必要な順序に保つ。
【００７１】
（ＩＶ．  提示プロセス）
ＴＳＳＥの例の例示的な実施例における最後のプロセスは、図７に示すように検索結果を提示２４０向けに準備することである。キーワード関連度の順位で整列した非対話的な結果を提示する現在の大規模な検索エンジンとは異なり、このＴＳＳＥの例は、時間、イベントの関係、およびキーワード関連度の順位で編成した結果を提示することができる。
【００７２】
（ＩＶ．Ａ  時間ベースの提示）
時系列データのインデックス付与および検索の課題に特有なものは、主要次元として時間を用いて結果を提示することである（７１０）。既存の大規模検索エンジンでは情報を時間で編成しないので、時間ベースで結果を提示することは考慮されていない。一方、ＴＳＳＥの主な利点は、時系列データを年代順にインデックス付与、検索および提示できることである。離散的な時間範囲に基づいて、または統計的な計算に基づいて検索結果を集約および要約することにより、結果を提示することができる。
【００７３】
例えば、ＴＳＳＬの例では、特定の時間フレームだけの結果を参照すること、および／または秒、分、時間、日、週もしくは月で提示した結果を参照することを指定できる。このように、検索窓を時間フレームに限定することができ、結果を、検索から返される期待結果セットの密度に基づいて、最適に表示するように構築することができる。「192.168.169.100 hoursago::24 page::seconds」という検索では、直前の２４時間以内に生じたキーワード「192.168.169.100」を含む時系列イベントが返され、表示結果が秒で要約されるであろう。ＴＳＳＥの例示的な実施例では、要約には、集約済みの表示行によりイベントを要約ウィンドウに対して要約すること、および／または要約ウィンドウにより結果をページングすることの両方を含めることができる。上述の例では、検索結果を表示するそれぞれのページは１秒間の結果を含むことができる。機能の例としては下記があるが、これらに限らない。  
・結果データ（ｎ個）を個数で一度にスクロール／ページングする機能
・データを時間、即ち次／前の秒、分、時間、日、年でスクロール／ページングする機能
・時間フレーム当りの最大個数を指定する機能
・ページ分割した時間フレーム内で次の結果（ｎ個）を取得する機能。例えば、（１秒以内で）次の１００個を取得する機能
【００７４】
（ＩＶ．Ｂ  メタデータの提示）
時間ベースの提示７１０に加えて、ＴＳＳＥの例は、データソース、データソースタイプ、イベントタイプ、または送信元のホストマシンのようなメタデータ特性で結果をさらに集約および要約したものを提示（７２０）できることが望ましい。このように、結果を時間で編成できるだけでなく、メタデータ集約および要約により絞り込むこともできる。「192.168.169.100 page::source」という検索により、「192.168.169.100」を有する結果の全てが提示され、結果を含む各データソースを別のページに表示する。結果の例としては下記があるが、これらに限らない。  
・データソースの発生した物理位置
・データを生成する元の物理マシン、センサー等
・インデックス付与プロセスにより動的に割り当てたデータソースのタイプ
・インデックス付与プロセスにより動的に割り当てたイベントのタイプ
【００７５】
（ＩＶ．Ｃ  ズーム制御）
時間およびある特定のメタデータパラメータ（例えば、マシンのＩＰアドレス）は連続的である可能性があるため、ＴＳＳＥの例のユーザー対話モデルに、ズーム制御７３０を用いて細かい時間増分（秒または分）またはメタデータパラメータ（異なる分類のＩＰアドレス）から移動する機能を含めることができる。このズーム制御を他のメタデータ検索パラメータと組み合わせて、大量のデータの中を高速に移動することができる。機能の例としては下記があるが、これらに限らない。  
・所与の時間周辺で任意の秒（複数可）から分（複数可）、時間（複数可）等へズームインおよびズームアウトする機能
・特定のデータソースタイプおよび物理マシン位置に関して、２００５年６月３日午前１２時１５分前後で第２の解像度にズームインする機能
【００７６】
（ＩＶ．Ｄ  表示密度制御）
様々な種類のユーザー（人間およびシステム）ならびに様々なタイプの時系列データおよびイベント（例えば、数バイトのサイズの単一行イベントから数メガバイトのサイズの複数行イベントまで）を考えると、結果の密度を指定できると好都合である。一実施例では、表示密度を制御して（７４０）、いずれのメタデータも伴わない生データのみを単純なアスキーテキスト形式で返す、および／または表示することができる。あるいは、リッチＸＭＬとして、全てのメタデータとともに上記と同じ結果を返す、および／または表示することができる。
【００７７】
（Ｖ．  実施例）
ＴＳＳＥを、多くの異なる方法で実施例することができる。１つの手法では、様々な図面で図示したそれぞれの箱は、別々のプロセスとしてソフトウェアで実施される。全てのプロセスを単一のマシン上で実行するか、または分割して別々の論理または物理マシン上で実行することができる。代替的な実施形態では、本発明はコンピューターハードウェア、ファームウェア、ソフトウェア、および／またはそれらの組合せで実施される。本発明の装置を、プログラム可能プロセッサーにより実行するための、機械読取可能な記憶装置で明白に具現化したコンピュータープログラム製品で実施することができる。本発明の方法ステップを、プログラム可能プロセッサーにより実施することができる。このプロセッサーは、諸命令から成るプログラムを実行し、その諸命令は、入力データに対して動作して出力を生成することで本発明の機能を実施する。データ記憶システムからデータおよび命令を受信し、データ記憶システムへデータおよび命令を送信するよう結合した少なくとも１つのプログラム可能プロセッサーと、少なくとも１つの入力装置と、少なくとも１つの出力装置とを含むプログラム可能システム上で実行可能な１つまたは複数のコンピュータープログラムで本発明を有利に実施例できる。それぞれのコンピュータープログラムを高レベルの手続き型もしくはオブジェクト指向型プログラミング言語で実施例することができ、または必要に応じてアセンブリもしくは機械語で実施例することができる。何れの場合も、言語はコンパイル型またはインタプリタ型の言語とすることができる。適切なプロセッサーとしては、例として、汎用目的マイクロプロセッサーおよび特殊目的マイクロプロセッサーの両方が含まれる。一般に、プロセッサーは読取専用メモリーおよび／またはランダムアクセスメモリーから命令およびデータを受信する。一般に、コンピューターは、データファイルを格納するための１つまたは複数の大容量記憶装置を含む。その装置としては、内蔵ハードディスクおよび取外し可能ディスクなどの磁気ディスク、光磁気ディスク、および光ディスクがある。コンピュータープログラム命令およびデータを明白に具現化するのに適した記憶装置には全ての形態の不揮発性メモリーが含まれ、例としてＥＰＲＯＭ、ＥＥＰＲＯＭなどの半導体メモリー装置、フラッシュメモリー装置、内蔵ハードディスクおよび取外し可能ディスクなどの磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスクが含まれる。上記のいずれも、特定用途向け集積回路（ＡＳＩＣ）および他の形態のハードウェアで補完するかまたはそれらに組み込むことができる。
【００７８】
従って、発明を実施するための形態には多数の詳細が含まれるが、これらは本発明の範囲を限定するものとして解釈すべきではなく、単に本発明の様々な例および態様の例示として解釈すべきである。上記では詳細に議論していない他の実施形態が本発明の範囲に含まれることは理解されるべきである。添付の特許請求の範囲で定義した本発明の趣旨および範囲から逸脱することなく、当業者に明らかと思われる様々な修正、変更および変形を、本明細書で開示した本発明の配置、動作ならびに方法および装置の詳細に加えることができる。従って、本発明の範囲は添付の特許請求の範囲とその法的な等価物とにより決定されるべきである。
【図１】
2010506311.tif 000003
【図２】
2010506311.tif 000004
【図３】
2010506311.tif 000005
【図４】
2010506311.tif 000006
【図５】
2010506311.tif 000007
【図６】
2010506311.tif 000008
【図７】
2010506311.tif 000009
【国際調査報告】
2010506311.tif 000010