(57)【特許請求の範囲】
【請求項１】
データと、そのデータの出現頻度ｆと、誤差見積もりΔとを組とした頻度情報を記憶するスケッチ記憶部と、時系列で得られるＮ個のデータを１サイクルとし、１サイクルの中から一定以上の出現率で出現するデータを前記スケッチ記憶部を検索することで得られるように、前記スケッチ記憶部内の頻度情報の追加・削除・変更を行うとともに、最初のＮ個のデータに基づく前記スケッチ記憶部内の頻度情報の追加・削除・変更後は、新たに所定個のデータが得られる度に、その所定個分ずらしたＮ個のデータを１サイクルとして一定以上の出現率で出現するデータを前記スケッチ記憶部を検索して得られるように、前記スケッチ記憶部内の頻度情報の追加・削除・変更を行う演算部とを備え、
該演算部は、
順次入力されるデータを取得し、取得した複数のデータを、予め設定された許容誤差により決定される区間データ数毎に区切り、最初から順に通し番号を区間番号ｂとして付与するデータ取得処理と、
前記取得したデータが前記スケッチ記憶部に記憶されていない場合、そのデータを、頻度ｆ＝１、Δ＝ｂ−１とを組とした頻度情報として前記スケッチ記憶部に新たに追加するデータ追加処理と、
前記取得されたデータが、前記スケッチ記憶部に記憶されている場合、該当の頻度情報のｆの値に１加算する頻度加算処理と、
前記データ追加処理又は前記頻度加算処理を、順次取得した区間データ数個分のデータに対して行って１区間の処理が終了し、区間の境界に達すると、その度に、ｆ＋Δが現在処理中の区間の番号ｂ以下であるデータを前記スケッチ記憶部から消去する低頻度データ削除処理とを実行し、最初のサイクルのＮ個のデータに対して、前記データ追加処理・前記頻度加算処理・前記低頻度データ削除処理が終了した場合、
上記スケッチ記憶部に記憶された各データそれぞれについて、Δが０か否かを判断し、Δが０でないデータに対しては、Δを１減算するΔ減算処理を行い、Δが０であるデータに対しては、そのデータの最初の区間における出現数の推定値をｆから減算し、減算結果が現在までの処理区間数より小さい場合は該データに関する頻度情報を前記スケッチ記憶部から削除する頻度近似処理を行い、その結果得られるスケッチ記憶部の頻度情報を近似して、前記所定数個分のデータだけずらした次のサイクルのＮ個のデータのうち最後の区間データ分を除いたデータを処理した場合のスケッチ記憶部の頻度情報を生成し、
その後入力されるデータが、前記次のサイクルの最後の区間の最初のデータから入力されているものとして前記データ取得処理、前記データ追加処理、前記頻度加算処理、前記低頻度データ削除処理、前記Δ減算処理、前記頻度近似処理を継続して行うことを特徴とする統計処理装置。
【請求項２】
前記推定値を、ｆを全区間数で除算した値と、１との、大きいほうの値とすることを特徴とする請求項１記載の統計処理装置。
【請求項３】
前記スケッチ記憶部は、更に、各データそれぞれについて最後に出現した区間の区間番号番号を、最終区間番号Ｌとして記憶しており、前記データ追加処理及び前記頻度加算処理では、それぞれ請求項１の動作に加えて更に、現在の区間番号を前記最終区間番号Ｌとして記憶又は更新し、
前記頻度近似処理では、前記スケッチ記憶部に記憶された各データそれぞれについてΔが０であるデータの場合は、その最初の区間における出現数の推定値を、少なくともそのデータについてのfの値と、最終区間番号Ｌの値とを用いて、そのデータが最初から区間Ｌまでの間に出現していたものとして算出し、
前記頻度近似処理はさらに、前記スケッチ記憶部に記憶された各データそれぞれについて、Ｌから１減算し、Ｌが０となった場合はそのデータを前記スケッチ記憶部から消去する最終区間番号減算処理を行うことを特徴とする請求項１記載の統計処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列データから一定頻度以上現われる値の出現頻度を計数する装置で、特に、継続的に得られる時系列データを保持し続けることが困難で、且つ、時間と共に出現頻度の傾向が変化する場合にも対応する手法に関するものである。
【背景技術】
【０００２】
継続的に得られる大規模な時系列データから、一定以上の頻度で現われる値を抽出する処理は、様々な場面で必要になる。例えば、ネットワーク環境のトラフィックを監視し、パケットロス等のエラーの発生を検出したＩＰアドレスをデータ出力するようなシステムにおいて、ＩＰアドレスをデータ列とし、ＩＰアドレスごとにエラー検出数を集計し、一定割合以上のエラーの要因となっているＩＰアドレスもしくは経路を得るような場合などがある。
【０００３】
このような場合、単純にはＩＰアドレスごとにカウンタを持ち、エラーの発生ごとにカウンタを増加させることが考えられる。しかし、ＩＰアドレス空間は広大であり、少なくともネットワークに繋がっている端末分程度のカウンタが必要となり、大きなメモリを必要とする。また、各カウンタの中から、一定頻度以上のカウンタを探索するために大きなメモリ空間をスキャンする必要があり、高い演算能力も要求される。
【０００４】
このため、従来、一定頻度以上のデータを得るに際し、予め設定された許容誤差範囲内に出現頻度が収まる程度の低頻度データを順次メモリから削除することにより、より少ないメモリ量で、一定以上の頻度で出現するデータと、その頻度を得る手法が論じられている（例えば、非特許文献１参照）。
【０００５】
ここで、上記文献における統計処理方法について、図８〜図１０を参照して説明する。図８は、従来の統計処理方法を示すフローチャートである。図９は、従来の統計処理方法におけるデータ列の概念図である。図１０は、図８のスケッチ記憶部の変化の様子を示す図である。
【０００６】
図９において、○が一つ一つのデータ（例えば、ＩＰアドレス）であり、左端のデータから右端のデータまでＮ個のデータが流れる（つまり、上述のエラー監視システムにおいて、エラー検出されたＩＰアドレスが順次出力されている状況を想定）ものとする。ここでは、Ｎ個のデータの中から、出現率がｓ％以上のデータを抽出する場合を例に説明する。また、図９において、εは頻度の誤差範囲を決める値である。具体例で説明すると、例えば、ｓ＝１％，ε＝０．１％の場合、出現率が１％以上のデータを抽出することが目的であるが、０．１％の誤差は認めるものとし、すなわち０．９％以上の出現頻度のものでもＯＫとしてデータ抽出を行うものである。また、図９に示したように、Ｎ個のデータが仮想的に１／εごとの区間に分けられているものとし、それぞれの区間に、区間番号ｂが１から順に付けられているものとする。ここでは、Ｎ＝１０００００であるとすると、区間数εＮは（０．１／１００）＊１０００００で１００であり、１０００００個のデータが、１０００個ずつ１００個の区間に分けられていることになる。
【０００７】
以下、図８のフローチャートを参照しながら上記文献における統計処理方法を説明する。なお、図８において、スケッチ記憶部３ａは、データと、そのデータの出現数（頻度）ｆと、出現数の誤差見積もりにあたるΔとを組として頻度情報として記憶する領域で、適宜、頻度情報の追加・削除・変更が行われる。また、区間内処理データ数記憶部３ｂは、区間内のデータ処理数を順次カウントし、区間境界に達すると０クリアし、再度カウントを開始するための記憶部である。
【０００８】
まず、データ取得処理としてデータを順に取得する（Ｓ１）。例えばＤ１というデータが得られたものとする。そして、このＤ１がスケッチ記憶部３ａに記憶されているか判定する（Ｓ２）。最初はスケッチ記憶部３ａは空なので、そのデータを含む頻度情報を作成してスケッチ記憶部３ａに記憶する、データ追加処理を行う（Ｓ３）。頻度情報には、データの他、上述したように、そのデータの出現数ｆと、Δとが記憶される。頻度ｆは、ここでは１、Δは、区間番号ｂから１減じた値であり、ここでは０となる。Δの詳細については後述する。
【０００９】
続いて、区間内データ数計数処理を行う（Ｓ４）。区間内データ数計数処理では、区間内処理データ数記憶部３ｂのカウンタを増やす。最初は０クリアされており、ここでは、また１つ目のデータであるため、１が記憶される。そして、区間境界か否かを判断し、ここではまだ区間境界（すなわち、１／εで、ここでは１０００個のデータ）ではないため、ステップＳ１に戻り、次のデータを取得する。
【００１０】
ここで、新たにデータＤ２が得られたものとすると、この場合も上記と同様の処理が行われ、スケッチ記憶部３ａの内容は、図１０（ａ）に例示したものとなる。
【００１１】
なお、時系列で順次取得されるデータの中で、既にスケッチ記憶部３ａに記憶されたデータが再度取得された場合には、頻度加算処理を行う（Ｓ４）。頻度加算処理では、スケッチ記憶部３ａの該当頻度情報の頻度ｆが１加算される。すなわち、例えばスケッチ記憶部３ａが図１０（ａ）のような内容の時にデータＤ１が得られた場合、すでにＤ１があるため、その頻度１を１増やして２とし、図１０（ｂ）のようになる。
【００１２】
以上の処理を繰り返し、区間内データ数計数処理（Ｓ５）で区間内処理データ数記憶部３ｂのカウンタが増え、その数が１／εになると、区間境界であると判断し、区間内処理データ数記憶部３ｂをリセットし（Ｓ７）、低頻度データ削除処理（Ｓ８）に入る。
【００１３】
低頻度データ削除処理（Ｓ８）は、処理開始から現在までの区間においてε％以下の出現率のデータをスケッチ記憶部３ａから削除する処理である。すなわち、誤差以下の出現率でしか出現しないデータについてはメモリ容量削減の観点から削除するものである。なお、１区間を１／εに設定していることから、各区間で１回のみしか登場しなかった場合の出現率はε％に相当する。よって、処理開始から現在までの区間における頻度が現在の区間番号ｂ以下のデータをスケッチ記憶部３ａから削除すればよい。
【００１４】
ただし、低頻度データ削除処理は、区間境界の度に行われる処理であるため、以前の区間で出現したにもかかわらず、低頻度データ削除処理で削除されたことがある可能性もあることから、その数も踏まえて処理する必要がある。その削除された可能性のある最大数は区間番号ｂ−１、すなわちΔに相当する。これは、Δに書き込まれている番号は、スケッチ記憶部３ａにそのデータＤが書き込まれたときの区間番号ｂから１減算した値であるため、例えば、ある区間番号の処理が終了した時点のスケッチ記憶部３ａのデータが、ｆが２０、Δが１０の場合、区間１１のときにデータＤがスケッチ記憶部３ａに書き込まれ、その書き込まれた時点から現在までのデータＤの出現回数が２０回あったことを意味している。ここで、Δが１０ということは、区間１−１０の間には、データＤが全く出現しなかった場合もあり得るが、一度出現したものの、低頻度データ削除処理で削除された可能性もある。その削除された可能性のある最大数が、Δに相当する。
【００１５】
以上のことから、この低頻度データ削除処理では、ｆ＋Δ≦ｂを満たすデータをスケッチ記憶部３ａから削除する。例えば、区間番号が１で、スケッチ記憶部３ａが図１０（ｂ）のようであれば、Ｄ１は２＋０≦１であるため残されるが、Ｄ２は１＋０≦１なために削除され、図１０（ｃ）のようになる。
【００１６】
以上の低頻度データ削除処理を、区間境界になる度に行い、スケッチ記憶部３ａ内のデータを整理する。
【００１７】
以上のステップＳ１〜Ｓ８の同様の処理を繰り返し、例えば次の区間ｂ＝２でデータＤ１が得られた場合はデータＤ１のｆが１加算され、新たにデータＤ３が得られた場合は新たにＤ３が加えられてｆ＝１、Δ＝ｂ−１＝１として、図１０（ｄ）のようになる。
【００１８】
そして、上記の統計処理の結果得られるスケッチ記憶部３ａから、出現率が１％以上（誤差ε％分を考慮し、実際には０．９％以上）のデータを抽出する。具体的には、ｆ≧（ｓ−ε）Ｎを満たすデータを得る。この操作によりＮ個のデータ中の出現率がｓ％以上のデータを得ることができる。
【００１９】
以上のような一連の処理により、全データ種類ごとにカウンタを持つことなく、小さいメモリ（スケッチ記憶部）での頻出値の抽出が従来より実現されている。
【非特許文献１】Gurmeet Singh Manku, Rajeev Motwani, 「Approximate Frequency Counts over Data Stream」, VLDB 2002 (28th VLDB), p 346-357, August 2002
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、上記の従来技術では、Ｎ個のデータが処理された時点で一区切りとなる。このため、頻度が高いデータを継続的に抽出したい場合、次のＮ個を処理することになる。すなわち、１サイクル処理後、次のサイクルの処理を開始するタイミングは、あくまでも１サイクル終了後であり、１サイクルの処理を終了する前に、そのサイクル内の一部のデータも含めたＮ個のデータ中における高頻度データを抽出する処理は行えない。例えば、時系列に得られる１０万個のデータから高頻度データを抽出する処理を、１００個の新たなデータが得られる度に行いたいというような処理を行うことができない。
【００２１】
もしそれを実現しようとすると、複数の処理を所望のデータ数だけずらして平行して行う必要があり、図１１に示したようなタイミングで平行してＮ／ｗ個の処理を行うことになり、Ｎ／ｗ倍のメモリと処理能力が必要となる。
【００２２】
このような処理は、例えばトラフィック観測の場合に必要となる。トラフィック観測のように、データが継続して終端なく流れる場合で、且つ、実際に通信を行っている端末すなわちＩＰアドレスが頻繁に入れ替わる可能性がある場合など、頻出する値が時間と共に変化することが多い。このため、上記のようなことが処理が必要となり、効果的な処理が望まれている。
【００２３】
本発明はこのような点に鑑みなされたもので、メモリ容量を大きくすることなく、また、演算処理能力の高いＣＰＵを設けることなく、一定頻度以上のデータを抽出することが可能な統計処理装置を提供することを目的とする。
【課題を解決するための手段】
【００２４】
本発明に係る統計処理装置は、データと、そのデータの出現頻度ｆと、誤差見積もりΔとを組とした頻度情報を記憶するスケッチ記憶部と、時系列で得られるＮ個のデータを１サイクルとし、１サイクルの中から一定以上の出現率で出現するデータをスケッチ記憶部を検索することで得られるように、スケッチ記憶部内の頻度情報の追加・削除・変更を行うとともに、最初のＮ個のデータに基づくスケッチ記憶部内の頻度情報の追加・削除・変更後は、新たに所定個のデータが得られる度に、その所定個分ずらしたＮ個のデータを１サイクルとして一定以上の出現率で出現するデータをスケッチ記憶部を検索して得られるように、スケッチ記憶部内の頻度情報の追加・削除・変更を行う演算部とを備え、演算部は、順次入力されるデータを取得し、取得した複数のデータを、予め設定された許容誤差により決定される区間データ数毎に区切り、最初から順に通し番号を区間番号ｂとして付与するデータ取得処理と、取得したデータがスケッチ記憶部に記憶されていない場合、そのデータを、頻度ｆ＝１、Δ＝ｂ−１とを組とした頻度情報としてスケッチ記憶部に新たに追加するデータ追加処理と、取得されたデータが、スケッチ記憶部に記憶されている場合、該当の頻度情報のｆの値に１加算する頻度加算処理と、データ追加処理又は頻度加算処理を、順次取得した区間データ数個分のデータに対して行って１区間の処理が終了し、区間の境界に達すると、その度に、ｆ＋Δが現在処理中の区間の番号ｂ以下であるデータをスケッチ記憶部から消去する低頻度データ削除処理とを実行し、最初のサイクルのＮ個のデータに対して、データ追加処理・頻度加算処理・低頻度データ削除処理が終了した場合、上記スケッチ記憶部に記憶された各データそれぞれについて、Δが０か否かを判断し、Δが０でないデータに対しては、Δを１減算するΔ減算処理を行い、Δが０であるデータに対しては、そのデータの最初の区間における出現数の推定値をｆから減算し、減算結果が現在までの処理区間数より小さい場合はデータに関する頻度情報をスケッチ記憶部から削除する頻度近似処理を行い、その結果得られるスケッチ記憶部の頻度情報を近似して、所定数個分のデータだけずらした次のサイクルのＮ個のデータのうち最後の区間データ分を除いたデータを処理した場合のスケッチ記憶部の頻度情報を生成し、その後入力されるデータが、次のサイクルの最後の区間の最初のデータから入力されているものとしてデータ取得処理、データ追加処理、頻度加算処理、低頻度データ削除処理、Δ減算処理、頻度近似処理を継続して行うものである。
【発明の効果】
【００２５】
以上に説明したように、本発明によれば、所定個のデータだけずらした場合のスケッチ記憶部の内容を、その前のサイクルの頻度情報を用いて近似して生成することができる。これにより、スケッチ記憶部をサイクル毎に重複して持ったり、同じ処理を平行して行うことなく、所定個ずつずらしたデータから処理を開始し、Ｎ個のデータを処理した結果を記憶したスケッチ記憶部を随時得ることができる。
【発明を実施するための最良の形態】
【００２６】
実施の形態１．
図１は、実施の形態１の統計処理装置の構成を示すブロック図である。
統計処理装置１は、具体的には例えばパソコンなどのコンピュータで構成され、ＣＰＵ等の演算部２と、ＲＯＭやＲＡＭで構成される記憶部３と、外部装置からデータを取得するためのインタフェース部４とを備えている。記憶部３は、スケッチ記憶部３ａと、区間内処理データ数記憶部３ｂと、処理データ数記憶部３ｃとを有している。統計処理装置１による統計処理の手順は、記憶部３に記憶されているプログラムに基づいてＣＰＵによって成されるものである。本発明の統計処理装置は、従来技術の統計処理方法を基本として更に改善した方法を実施するもので、具体的には、Ｎ個のデータ中において一定出現率ｓ％以上のデータを抽出する処理を、１／ε個の新たなデータが得られる度毎に行うものである。なお、実施の形態１中で登場するε、ｆ、Δのそれぞれの内容は、上記従来技術と同様である。
【００２７】
スケッチ記憶部３ａは、データと、そのデータの出現数ｆと、出現数の誤差見積もりにあたるΔとを組とした頻度情報を記憶する領域で、適宜、追加・削除・変更が行われる。
【００２８】
区間内処理データ数記憶部３ｂは、処理中の区間内におけるデータ処理数が記憶される記憶部である。
【００２９】
処理データ数記憶部３ｃは、処理開始からの「処理データ数」と、現在までに通過した「区間境界の数」とが記憶される記憶部で、従来と比較して新たに設けられた記憶部である。区間境界の数は、例えば、現在処理中の区間番号が例えば５の場合、区間番号から１減算した４となる。そして、現在処理中の区間番号内の全データの処理が終了した時点で区間番号５にカウントアップされる。
【００３０】
図２は、実施の形態１の統計処理方法を説明するためのデータ列の概念図である。データ列の概念は、図９に示した従来技術とほぼ同様であり、図２中の○は、一つ一つのデータを示しており、左端のデータから順に、時系列にデータが流れるものとする。また、実施の形態１の統計処理方法は、Ｎ個のデータ中において一定出現率以上現れるデータを抽出する処理を、１／ε個のデータが得られる度毎に行うものである。すなわち、サイクル１内のＮ個のデータ中において一定出現率以上現れるデータを抽出する処理を行った後、新たに１／ε個のデータが得られると、今度はサイクル２内のＮ個のデータ中において一定出現率以上現れるデータを抽出する処理を行うもので、新たに１／ε個のデータが得られる度に継続して行うものである。
【００３１】
図３及び図４は、実施の形態１の統計処理方法を示すフローチャートである。以下、図３及び図４を参照して実施の形態１の統計処理方法について説明する。なお、図３において、Ｓ１〜Ｓ８までの処理は図８に示した従来のＳ１〜Ｓ８までの処理と同様であるため、ここでの詳細説明は省略する。また、図５にスケッチ記憶部３ａを例示しながら、動作の説明をする。
【００３２】
ステップＳ８の低頻度データ削除処理終了後、処理サイズであるＮ個のデータの処理が終わったか（εＮ番目の区間の処理が終わったか）を、処理データ数記憶部３ｃの計数値に基づいて判定する（Ｓ９）。まだ終わっていない場合は処理データ数記憶部３ｃの「処理データ数」に１加算する（データ数計数処理）とともに、「区間境界の数」に１加算する。具体的には、サイクル１のｂ１＝１内の最後のデータの処理終了後の「処理データ数」は、１／ε、「区間境界の数」は０となる。そして、ステップＳ１に戻る。Ｎ個のデータの処理が終わるまでは、従来技術の説明と同じ動作を行う。
【００３３】
そして、Ｎ個のデータの処理が終了して図２のＰ１まで処理が進んだ結果、スケッチ記憶部３ａの内容が図５（ａ）のようになっていたものとする。この時、処理データ数記憶部３ｃには、「処理データ数」がＮで、「区間境界の数」がεＮ−１と記憶されている。このため、ステップＳ９では、Ｎ個のデータの処理が終わったと判定し、サイクル１の処理後のスケッチ記憶部３ａ内の頻度情報に基づいて、サイクル２の区間番号ｂ２＝１〜εＮ−１までの頻度情報を作成するための、近似データ作成処理を行う（Ｓ１１）。すなわち、サイクル１に対する近似データ作成処理の結果（すなわちスケッチ記憶部３ａ内の全ての頻度情報）を、サイクル２（サイクル１の最初のデータから１／ε個後のデータを処理開始点としたサイクル）の処理結果の近似値とみなす。そして、次に処理する区間の区間番号がεＮであるとして、サイクル２の処理を行う。これにより、以後、ステップＳ３のデータ追加処理でΔに入力される値は常にεＮ−１となる。
【００３４】
図４は、図３の近似データ作成処理を示すフローチャートである。
まず、フローチャートを説明するに先立ち、近似データ作成処理の概要について説明する。近似データ作成処理は、サイクルｎ（ｎは整数）で得られたスケッチ記憶部３ａ内の各頻度情報に基づいて、次のサイクルｎ＋１の区間番号１〜εＮ−１の頻度情報を作成するものである。
【００３５】
具体的に図２のサイクル１及びサイクル２の例で説明すると、近似データ作成処理で作成したいデータは、サイクル２のｂ２＝１〜εＮ−１までを処理した結果である。そこで、サイクル１のｂ１＝１における頻度ｆの推定値を作成し、その推定値を、サイクル１のｂ１＝１〜εＮまでを処理した結果から減算することで、ｂ２＝１〜εＮ−１までを処理した結果として見なすものである。すなわち、１区間ずらしたスケッチ記憶部３ａの近似を得るためには、その最初の区間でのデータの出現頻度を減ずる必要があるため、このような処理を行っている。なお、各区間毎の出現数は記憶されていない（記憶しておくとメモリの削減効果が無くなる）ため、その推定値を近似で求める必要がある。この推定値の算出方法については後述する。
【００３６】
近似データ作成処理の具体的な処理としては、スケッチ記憶部３ａ内の各頻度情報毎に、その頻度情報のΔの値が０の場合に頻度近似処理（Ｓ２３）を行い、０ではない場合にΔ減算処理を行う（Ｓ２４）。Δが０であるデータ（データＡとする）は、サイクル１の区間番号１で初めて出現し、その後、低頻度データ削除処理で削除されることなく、ε％以上の出現率で出現していることを意味している。このため、頻度近似処理として、Δが０であるデータＡについては、例えば、頻度情報の頻度ｆを区間数εＮで除算した値を、各区間毎のデータＡの平均出現数（上記の推定値に相当）と見なし、この値をｆから減じた値を、次のサイクル２でのデータＡの出現頻度の近似値と見なすものである。これは、全区間でそのデータが平均的に現れたとした場合の近似となる。なお、頻度ｆを区間数εＮで除算した値が１に満たない場合には、推定値は１とする。また、そのデータＡのΔの値は０のままとする。
【００３７】
一方、Δが０でないデータ（データＢとする）については、頻度ｆについてはそのままとし、Δの値を１減じるΔ減算処理を行う。すなわち、サイクル１のデータＢの頻度情報を、そっくりそのままサイクル２のデータＢの頻度情報と見なすものである。
【００３８】
ここで、図５（ａ）のスケッチ記憶部３ａに対して近似データ作成処理を行った場合には、その結果は、図５（ｂ）のようになる。すなわち、図４の近似データ作成処理のフローチャートに基づいて説明すると、まず、スケッチ記憶部３ａから、データＤ１の頻度情報を取得する（Ｓ２１）。データＤ１のΔは０であるため（Ｓ２２）、頻度近似処理を行い（Ｓ２３）、ｆ／εＮ＝４１０／１００≒４をｆから減じ、ｆの値を４０６とし、Δの値はそのままとする。そして、ｆの減算結果が全区間数より小さいか否かをチェック（ｆ≦εＮ−１を満たすか否かをチェック）し、満たさないため、Ｄ１の頻度情報はスケッチ記憶部３ａに残しておく。
【００３９】
そして、スケッチ記憶部３ａ内にはまだ頻度情報があるため（Ｓ２５）、ステップＳ２１に戻り、次のデータＤ２を取得する（Ｓ２１）。データＤ２のΔは１０であるため、Δ減算処理を行い（Ｓ２４）、Δの値を１０から１減じて９とする。
【００４０】
以上の近似データ作成処理によって得られた頻度情報を、図２のサイクル２のｂ２＝１〜εＮ−１の区間を処理した結果の近似値と見なす。
【００４１】
そして、この後、ステップＳ１に戻り、区間境界Ｐ１以降の１／ε個のデータ分の処理を継続すると、ｂ２＝１〜εＮのデータを処理したことに相当する頻度情報がスケッチ記憶部３ａに記憶された状態になる。そして、このように、一旦Ｎ個のデータの処理が終わり、近似データ作成処理を実行した後は、処理対象となる区間は、常に１サイクル内の最後の区間となるため、ステップＳ９では、必ずＹＥＳとなり、近似データ作成処理が行われる。よって、時系列でＮ個以上のデータが取得され続けた際に、１／ε個後から処理を開始したことに相当する近似頻度情報を作り続けることができる。
このようにして更新されつづけるスケッチ記憶部３ａから、必要に応じて頻度値検出処理により、ｆが（ｓ−ε）Ｎ以上となるデータを抽出すればよい。
【００４２】
以上説明したように、本実施の形態１によれば、１／ε個のデータだけずらした場合のスケッチ記憶部３ａの内容を、その前のサイクルの頻度情報を用いて近似して生成することができる。これにより、スケッチ記憶部３ａをサイクル毎に重複して持ったり、同じ処理を平行して行うことなく、１／εずつずらしたデータから処理を開始し、Ｎ個のデータを処理した結果を記憶したスケッチ記憶部３ａを随時得ることができる。すなわち、先に述べた課題を解決できる。
【００４３】
また、１／ε以下のステップｗでずらしたい場合も、処理とメモリの重複は１／（εｗ）個で済み、課題で取り上げたＮ／ｗと比較すると、１／（εＮ）のメモリ・処理時間消費で済む。すなわち、εＮが充分大きい場合、本発明は大きな効果を得ることができる。
【００４４】
実施の形態２．
実施の形態２は、頻度近似処理（Ｓ２３）で算出する、最初の区間での出現数の推定値の精度を上げるものである。実施の形態２の統計処理装置のブロック構成及びデータ列概念は、実施の形態１と同様である。ただし、フローチャートにおいて、頻度加算処理Ｓ４、データ追加処理Ｓ３の処理内容が多少異なり、スケッチ記憶部３ａの記憶内容も一部異なり、近似データ作成処理Ｓ１１の内容は図６に示したようになる。なお、図６中のＳ２１、Ｓ２２、Ｓ２４、Ｓ２５の各ステップは実施の形態１（図３）と同様の動作を行い、頻度近似処理Ｓ３３は処理内容が多少異なり、また、最終区間番号減算処理Ｓ３６が追加されている。
【００４５】
以下、実施の形態２が、実施の形態１と異なる部分を中心に説明する。
スケッチ記憶部３ａは、図７に例示するように、実施の形態１の構成に加えて、データ毎に、そのデータが最後に出現した最終区間番号Ｌを記憶する領域を持つ。この情報を用いて、頻度近似処理において最初の区間での出現数の推定値の精度を上げることが、本実施の形態２の目的である。
【００４６】
データ追加処理Ｓ３は、実施の形態１と同様にスケッチ記憶部３ａに記憶されていないデータを受け取った場合にそのデータをスケッチ記憶部３ａに追加する。そして、実施の形態２のデータ追加処理では更に、そのデータに対応した最終区間番号Ｌに現在の区間番号を入れる。一旦Ｎ個のデータの処理が終わり、近似データ作成処理（Ｓ１１）を実行した後は、処理対象となる区間は、常に最後の区間となるため、データ追加処理でＬに入力される値は常にεＮとなる。また、このとき、同様にΔは、常にεＮ−１となる。
【００４７】
頻度加算処理Ｓ４は、実施の形態１と同様に既にスケッチ記憶部３ａに記憶されたデータが得られた場合はｆに１加算する。そして、本実施の形態２では更に、そのデータに対応したＬに現在の区間番号を入れる。一旦Ｎ個のデータの処理が終わった後、Δ減算処理、頻度近似処理を実行した後は、処理対象となる区間は、常に最後の区間となるため、Ｌに入力される値は常にεＮとなる。
【００４８】
最終区間番号減算処理Ｓ３６では、Ｌから１減算し、Ｌ＝０となった場合、そのデータの頻度情報をスケッチ記憶部３ａから削除する。データが削除された場合、以下のΔ減算処理Ｓ２４、頻度近似処理Ｓ３３は行わない。Δ減算処理Ｓ２４は実施の形態１と同様に動作する。
【００４９】
また、実施の形態１の頻度近似処理（Ｓ２３）では、Δ＝０のデータに関し、全区間でそのデータが平均的に出現しているものとして、頻度ｆを区間数εＮで除算し、その除算結果を頻度ｆから減じるようにしているが、そのデータが全区間で出現しているとは限られず、ある区間範囲内で全く出現していない場合もあり得る。そこで、実施の形態２の頻度近似処理（Ｓ３３）では、最初の区間に出現し、ある区間を境にぱったりと出現しなくなったような場合を考慮し、頻度ｆを最終区間番号で除算した結果を、頻度ｆから減じるようにしたものである。ここで、Ｌは、最後の出現位置から最終区間番号減算処理で１減じられた値であるので、具体的な処理としては、ｆ／（Ｌ＋１）の結果を頻度ｆから減じるものである。
【００５０】
以下、実施の形態２の動作について説明する。図７にスケッチ記憶部３ａの実例をあげながら動作の説明をする。
ステップＳ９で処理データ数記憶部３ｃの計数値から、処理サイズであるＮ個のデータの処理が終わったか（εＮ番目の区間の処理が終わったか）を判定して、まだ終わっていない場合は「処理データ数」を１加算して最初の処理Ｓ１に戻る。Ｎ個のデータの処理が終わるまでは、従来技術の説明と同じ動作を行う。
【００５１】
そして、Ｎ個のデータの処理が終了して図２のＰ１まで処理が進んだ結果、スケッチ記憶部３ａの内容が図７（ａ）のようになっていたものとする。またこの時、処理データ数記憶部には、「処理データ数」がＮで、「区間境界の数」がεＮ−１と記憶されている。このため、ステップＳ９では、Ｎ個のデータの処理が終わったと判定し、近似データ作成処理を行う。これ以後、区間境界では必ず近似データ作成処理（Ｓ１１）へ分岐するようになる。
【００５２】
近似データ作成処理（Ｓ１１）では、まず、スケッチ取得処理（Ｓ２１）で、スケッチ記憶部３ａから頻度情報を一つ取得する。そして、最終区間番号減算処理を行い（Ｓ３６）、データが削除されなかった場合（Ｓ３７）、その頻度情報のΔが０か否かを判断し（Ｓ２２）、０の場合、頻度近似処理を行い（Ｓ３３）、０でない場合、Δ減算処理を行う（Ｓ２４）。この処理を、スケッチ記憶部３ａ内の最後の頻度情報が処理されるまで繰り返す。
【００５３】
以下、具体例で説明する。ここで処理対象となる区間数εＮが１００であったとする。
まず、Ｄ１に関する頻度情報を取得する（Ｓ２１）。最終区間番号減算処理(Ｓ３６)でＤ１のＬを１００から１減じて９９とする。Ｌが０とならなかったためＤ１は削除されず（Ｓ３７）、Ｄ１の場合、Δが０であるため（Ｓ２２）、頻度近似処理を行う(Ｓ３３)。頻度近似処理では、ｆ／（Ｌ＋１）＝４１０／（９９＋１）≒４をｆから減じ、ｆの値を４０６とする。そして、ｆ≦εＮ−１を満たすか否かをチェックし、満たさないため、Ｄ１の頻度情報はスケッチ記憶部３ａから削除せず残しておく。
【００５４】
Ｄ２については、最終区間番号減算処理（Ｓ３６）でＬを８７から１減じて８６とする。また、Δが０でないため、Δ減算処理（Ｓ２４）を行い、Δを１０から１減じて９とする。
【００５５】
続いてＤ３については、Ｌは１減じて１９となる（Ｓ３６）。そしてΔが０であるため、頻度近似処理を行う（Ｓ２３）。すなわち、ｆ／（Ｌ＋１）＝１０２／（１９＋１）≒５をｆから減じて９７とする。ここで得られたｆ＝９７はεＮ−１＝９９以下であり、上記式を満たすため、Ｄ３の頻度情報はスケッチ記憶部３ａから消去される。
【００５６】
結果として、スケッチ記憶部３ａ内の頻度情報は、図７（ｂ）に示すようになる。これを図２のｂ２＝１〜εＮ−１、すなわち今までの処理より１／ε後のデータから処理を開始した場合のスケッチ記憶部３ａの内容の近似値とみなす。そして、次に処理する区間番号がεＮであるとして、サイクル２の処理を行う。すなわち、以後、データ追加処理Ｓ３でΔに入力される値は常にεＮ−１となり、区間境界では必ず近似データ作成処理（Ｓ１１）へ分岐するようになる。
【００５７】
そして、この後、ステップＳ１に戻り、区間境界Ｐ１移行の１／ε個のデータ分の処理を継続すると、ｂ２＝１〜εＮのデータを処理したことに相当する頻度情報がスケッチ記憶部３ａに記憶された状態になる。よって、時系列でＮ個以上のデータが取得され続けた際に、１／ε個後から処理を開始したことに相当する近似頻度情報を作り続けることができる。
【００５８】
このようにして更新されつづけるスケッチ記憶部３ａから、必要に応じてｆが（ｓ−ε）Ｎ以上となるデータを抽出すればよい。
【００５９】
以上説明したように、本実施の形態２によれば、実施の形態１と同様の作用効果が得られるとともに、最後にそのデータが出現した区間番号を保持するようにし、最初の区間における頻度ｆの推定値を求める際に、その区間番号の数でスケッチ記憶部３ａ内の頻度ｆを除算し、その除算結果を最初の区間における頻度ｆの推定値としたので、実施の形態１に比べて近似頻度情報の精度向上を図ることができる。、
これにより、データを観測する個数Ｎより短い期間だけ高頻度で現われたようなデータにおいても、その出現期間を考慮した頻度推定が可能となり、より妥当な近似を行うことができ、精度向上を図ることができる。
【００６０】
以上、時系列データ列から一定以上の頻度で現われるデータを抽出する装置として説明を行ったが、実際は、データをオペレータが目視検査する場合に高頻度の物から提示する可視化装置の一部として、もしくは、処理コストが高い解析処理を行うにあたって処理対象を高頻度データに絞るための前処理として用いるなどが考えられる。
【図面の簡単な説明】
【００６１】
【図１】実施の形態１の統計処理装置の構成を示すブロック図である。
【図２】実施の形態１の統計処理方法を説明するためのデータ列の概念図である。
【図３】実施の形態１の統計処理方法を示すフローチャートである。
【図４】図３の近似データ作成処理を示すフローチャートである。
【図５】実施の形態１のスケッチ記憶部の変化の様子を示す図である。
【図６】実施の形態２の近似データ作成処理を示すフローチャートである。
【図７】実施の形態２のスケッチ記憶部の変化の様子を示す図である。
【図８】従来の統計処理方法を示すフローチャートである。
【図９】従来の統計処理方法におけるデータ列の概念図である。
【図１０】図８のスケッチ記憶部の変化の様子を示す図である。
【図１１】従来技術によるｗステップでの処理例を示す図である。
【符号の説明】
【００６２】
１  統計処理装置
２  演算部
３  記憶部
３ａ  スケッチ記憶部
３ｂ  区間内処理データ数記憶部
３ｃ  処理データ数記憶部
４  インタフェース部
【図１】
0004525720.tif 000002
【図２】
0004525720.tif 000003
【図３】
0004525720.tif 000004
【図４】
0004525720.tif 000005
【図５】
0004525720.tif 000006
【図６】
0004525720.tif 000007
【図７】
0004525720.tif 000008
【図８】
0004525720.tif 000009
【図９】
0004525720.tif 000010
【図１０】
0004525720.tif 000011
【図１１】
0004525720.tif 000012