(57)【特許請求の範囲】
【請求項１】
時系列で測定された複数のデータストリーム間の遅延相関を求めるデータストリーム処理方法であって、
コンピュータが、
入力された前記データストリームのランダム射影、時系列の和、および、時系列の２乗和に基づく要約情報を作成して記憶手段に格納し、前記データストリームの測定値の更新に基づき前記要約情報を更新する要約情報計算手順と、
前記記憶手段に格納された前記要約情報を読み取り、その前記要約情報をもとに前記データストリームの相互相関関数を計算し、前記相互相関関数から前記データストリーム間の遅延相関を求めて出力する遅延相関計算手順と、
を実行することを特徴とするデータストリーム処理方法。
【請求項２】
前記要約情報計算手順は、指数関数により計算された時間間隔で更新された前記データストリームをもとに、前記要約情報を更新することを特徴とする請求項１に記載のデータストリーム処理方法。
【請求項３】
コンピュータが、あらかじめ相関があると指定された前記データストリームのペアが、前記遅延相関計算手順により未検出のときには、故障として検出することを特徴とする請求項１または請求項２に記載のデータストリーム処理方法。
【請求項４】
複数のコンピュータが、担当する前記データストリームに関する前記要約情報を、他のコンピュータとは並列に計算することを特徴とする請求項１ないし請求項３のいずれか１項に記載のデータストリーム処理方法。
【請求項５】
請求項１ないし請求項４のいずれか１項に記載のデータストリーム処理方法を、コンピュータに実行させるためのデータストリーム処理プログラム。
【請求項６】
請求項５に記載のデータストリーム処理プログラムを格納した、コンピュータが読み取り可能な記憶媒体。
【請求項７】
時系列で測定された複数のデータストリーム間の遅延相関を求めるデータストリーム処理装置であって、
入力された前記データストリームのランダム射影、時系列の和、および、時系列の２乗和に基づく要約情報を作成して記憶手段に格納し、前記データストリームの測定値の更新に基づき前記要約情報を更新する要約情報計算部と、
前記記憶手段に格納された前記要約情報を読み取り、その前記要約情報をもとに前記データストリームの相互相関関数を計算し、前記相互相関関数から前記データストリーム間の遅延相関を求めて出力する遅延相関計算部と、
を有することを特徴とするデータストリーム処理装置。
【請求項８】
前記要約情報計算部は、指数関数により計算された時間間隔で更新された前記データストリームをもとに、前記要約情報を更新することを特徴とする請求項７に記載のデータストリーム処理装置。
【請求項９】
あらかじめ相関があると指定された前記データストリームのペアが、前記遅延相関計算部により未検出のときには、故障として検出することを特徴とする請求項７または請求項８に記載のデータストリーム処理装置。
【請求項１０】
複数の前記データストリーム処理装置が、担当する前記データストリームに関する前記要約情報を、他の前記データストリーム処理装置とは並列に計算することを特徴とする請求項７ないし請求項９のいずれか１項に記載のデータストリーム処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストリームマイニング技術におけるデータストリーム処理方法、データストリーム処理プログラム、記憶媒体、および、データストリーム処理装置に関する。
【背景技術】
【０００２】
データストリームとはネットワークから高速に流れてくる大量のデータのことである。ストリームマイニングとは、時系列として表現されるデータストリームから役に立つ情報を素早く見つけ出す技術である。これは、単にデータベースに蓄えられた大規模データを分析するのではなく、増え続けるデータの流れをリアルタイムに分析し、監視するための技術である。
【０００３】
例えば、ストリームマイニングの分野では、複数のストリームから相関のあるストリームのペアを検出する技術がある。非特許文献１の手法は、離散フーリエ変換を用いることによって、複数のストリームから相関のあるストリームのペアを高速に検出している。しかし、多くの相関のあるストリームには大抵いくらかの遅延があり、非特許文献１の手法では相関のあるストリームでも遅延があるもの（以下、遅延相関とする）は、検出できなかった。
【０００４】
遅延相関があるストリームのペアを検出するためには、相互相関関数を計算する必要がある。相互相関関数は統計学の分野でよく使われる関数である。なお、長さｎの２つの時系列Ｘ＝（ｘ１，ｘ２，…，ｘｎ）と、Ｙ＝（ｙ１，ｙ２，…，ｙｎ）が与えられているとき、以下に示す（式１）が相互相関関数である。
【数１】
0004452234.tif 000002
【０００５】
図７は、二つの時系列データの相互相関関数の一例を示す図である。図７（ａ）および図７（ｂ）の二つの時系列は温度センサデータである。３０秒毎に計測した温度を示している。二つの温度センサはよく似た傾向を示しているが、若干のずれがある。具体的には、温度センサＡの方が少々遅れている。図７（ｃ）は相互相関関数である。縦軸は相関値、つまり二つの時系列にどれほど相関があるのかを示している。横軸は遅延の大きさ（遅延時間）である。つまり、相互相関関数は片方の時系列をずらしたときに両者にどれほどの相関値があるのかを示したものである。
【０００６】
図７では、二つの温度センサに遅延がないものとして相関を調べると、あまり相関がないという結果になるが、温度センサＢを少し遅らせて両者の相関を調べると高い相関値が得られる。そして、遅延が１３００［秒］のところで相関値のピークがある。この場合は「温度センサＡは１３００［秒］の遅延で温度センサＢと相関している」と言える。
【０００７】
遅延相関があるストリームのペアを検出する手法において、効率化が求められている。効率化の要因として、例えば、増え続ける大規模なデータを分析するため、また利用者に情報をリアルタイムに提供するため、高速化と省メモリ化を図る必要があることが挙げられる。
【０００８】
効率化を達成するために有効となるのは、データストリームの要約情報（以下、要約情報と表記する）の計算方法と要約情報を用いた問合せ処理方法である。これは、オリジナルのデータストリームの長さは非常に長くなるため、データストリームをコンパクトに表現した要約情報が、高速化と省メモリ化には有効となるためである。要約情報を保持することにより、オリジナルのデータストリームを破棄しながら、遅延相関があるストリームのペアを求めるための問合せ処理を実行することができる。
【０００９】
データストリームの要約情報をもとに遅延相関のあるストリームのペアを効率的に計算する方法として、非特許文献２の方法が提案されている。遅延相関を求めるためにデータストリームの統計値（平均、分散、内積）を要約情報として持っており、そしてデータを受信する毎に、それらの要約情報を更新する。
【００１０】
遅延相関のあるストリームのペアを効率的に計算する方法として、非特許文献２の方法が提案されている。非特許文献２の方法は、利用者もしくはアプリケーションからの要求があると、要約情報から遅延相関を計算し、相関のあるストリームのペアとその遅延の値を出力する。遅延相関を計算するための時間とメモリ量は、データストリームの長さに線形に比例して大きくなる。そこで、高速化と省メモリ化を達成するために、平滑化とサンプリングを用いて相互相関関数を近似している。
【００１１】
非特許文献２の方法では、相互相関関数の近似によって遅延相関の計算時間を低減化させている。しかし、非特許文献２の方法では、ストリームの数が増えたとき、要約情報の更新コストはストリームの数の２乗に比例するという問題がある。
【非特許文献１】Yunyue Zhu,Dennis Shasha“StatStream:Statistical Monitoring of Thousands of Data Streams in RealTime.”In Proceedings of VLDB,pp.358-369,August2002.
【非特許文献２】Yasushi Sakurai,SpirosPapadimitriou、Christos Faloutsos“BRAID:Stream Mining through Group Lag Correlations”In Proceedings of ACM SIGMOD,pp.599-610,June 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかし、従来の手法は、遅延相関のあるストリームのペアを効率的に計算できていない。ここで、効率的ではないとは、計算における計算量およびメモリ使用量を過剰に浪費することを意味する。
【００１３】
遅延相関の計算のためのメモリ使用量は以下の通りである。データストリームの数をｍとする。このとき、（式１）をそのまま計算する手法（以下、ナイーブな手法とする）を用いた場合、Ｏ(ｍ２)のメモリを必要とする。なお、関数Ｏは、計算量のオーダーを示す。何故ならナイーブな手法では、全てのデータストリームの和と分散、さらに全てのデータストリームのペアの内積を計算し、要約情報としてメモリに保存するためである。つまり、各データストリームのペアに対して、内積を保存し、その内積を用いて相関値を計算するため、Ｏ(ｍ２)のメモリを必要とする。
【００１４】
非特許文献１の方法では、そもそも遅延相関のあるストリームのペアを計算できない。また、非特許文献２の方法では、要約情報の更新に関する計算量はＯ（ｍ２）になり、効率化が不十分である。
【００１５】
そこで、本発明は、前記した問題を解決し、遅延相関のあるストリームのペアを効率的に計算することを主な目的とする。
【課題を解決するための手段】
【００１６】
前記課題を解決するために、本発明は、時系列で測定された複数のデータストリーム間の遅延相関を求めるデータストリーム処理方法であって、コンピュータが、入力された前記データストリームのランダム射影、時系列の和、および、時系列の２乗和に基づく要約情報を作成して記憶手段に格納し、前記データストリームの測定値の更新に基づき前記要約情報を更新する要約情報計算手順と、前記記憶手段に格納された前記要約情報を読み取り、その前記要約情報をもとに前記データストリームの相互相関関数を計算し、前記相互相関関数から前記データストリーム間の遅延相関を求めて出力する遅延相関計算手順と、を実行することを特徴とする。
【００１７】
これにより、要約情報を更新する際の計算時間とメモリ使用量を、従来技術よりも低減化することができる。
【００１８】
本発明は、前記要約情報計算手順が、指数関数により計算された時間間隔で更新された前記データストリームをもとに、前記要約情報を更新することを特徴とする。
【００１９】
これにより、データストリームのサンプル数が減ることで、要約情報を更新する際の計算時間とメモリ使用量を、従来技術よりも低減化することができる。
【００２０】
本発明は、コンピュータが、あらかじめ相関があると指定された前記データストリームのペアが、前記遅延相関計算手順により未検出のときには、故障として検出することを特徴とする。
【００２１】
これにより、データストリームの測定装置の故障を迅速に検出することができる。
【００２２】
本発明は、複数のコンピュータが、担当する前記データストリームに関する前記要約情報を、他のコンピュータとは並列に計算することを特徴とする。
【００２３】
これにより、データストリームの計算が並列化されることで、要約情報を更新する際の計算時間を、従来技術よりも低減化することができる。
【００２４】
本発明は、前記データストリーム処理方法を、コンピュータに実行させるためのデータストリーム処理プログラムである。
【００２５】
これにより、要約情報を更新する際の計算時間とメモリ使用量を、従来技術よりも低減化することができる。
【００２６】
本発明は、前記データストリーム処理プログラムを格納した、コンピュータが読み取り可能な記憶媒体である。
【００２７】
これにより、要約情報を更新する際の計算時間とメモリ使用量を、従来技術よりも低減化することができる。
【００２８】
本発明は、時系列で測定された複数のデータストリーム間の遅延相関を求めるデータストリーム処理装置であって、入力された前記データストリームのランダム射影、時系列の和、および、時系列の２乗和に基づく要約情報を作成して記憶手段に格納し、前記データストリームの測定値の更新に基づき前記要約情報を更新する要約情報計算部と、前記記憶手段に格納された前記要約情報を読み取り、その前記要約情報をもとに前記データストリームの相互相関関数を計算し、前記相互相関関数から前記データストリーム間の遅延相関を求めて出力する遅延相関計算部と、を有することを特徴とする。
【００２９】
これにより、要約情報を更新する際の計算時間とメモリ使用量を、従来技術よりも低減化することができる。
【００３０】
本発明は、前記要約情報計算部が、指数関数により計算された時間間隔で更新された前記データストリームをもとに、前記要約情報を更新することを特徴とする。
【００３１】
これにより、データストリームのサンプル数が減ることで、要約情報を更新する際の計算時間とメモリ使用量を、従来技術よりも低減化することができる。
【００３２】
本発明は、あらかじめ相関があると指定された前記データストリームのペアが、前記遅延相関計算部により未検出のときには、故障として検出することを特徴とする。
【００３３】
これにより、データストリームの測定装置の故障を迅速に検出することができる。
【００３４】
本発明は、複数の前記データストリーム処理装置が、担当する前記データストリームに関する前記要約情報を、他の前記データストリーム処理装置とは並列に計算することを特徴とする。
【００３５】
これにより、データストリームの計算が並列化されることで、要約情報を更新する際の計算時間を、従来技術よりも低減化することができる。
【発明の効果】
【００３６】
本発明によれば、要約情報の更新コストをＯ（ｍ）に引き下げることにより、データストリームの遅延相関を高精度に検出しつつ、高速かつ省メモリに処理をすることができる。これは、本発明の手法では、要約情報として各データストリームの平均値、分散値、ランダム射影を保存し、相関値はそれらから計算するために、Ｏ(ｍ)のメモリしか必要としないためである。
【発明を実施するための最良の形態】
【００３７】
以下に、本発明が適用されるデータストリーム処理システムの一実施形態について、図面を参照して詳細に説明する。まず、本実施形態のデータストリーム処理システムの構成について、図１を参照して説明する。
【００３８】
図１は、データストリーム処理システムを示す構成図である。データストリーム処理システムは、データストリームを計測するセンサ２、および、データストリームを処理するデータストリーム処理装置１を含めて構成される。なお、データストリーム処理装置１は、演算処理を行う際に用いられる記憶手段としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータとして構成される。なお、メモリは、ＲＡＭ（Random Access Memory）などにより構成され、データストリームの要約情報などを格納する。演算処理は、ＣＰＵ（Central Processing Unit）によって構成される演算処理装置が、メモリ上のプログラムを実行することで、実現される。データストリーム処理装置１は、要約情報計算部１０、および、遅延相関計算部２０を有する。
【００３９】
要約情報計算部１０は、データストリームを受信するたびに、各データストリームの要約情報を計算し、オリジナルのデータストリームを破棄する。なお、本実施形態における要約情報とは、ランダム射影、時系列の和、および、時系列の２乗和をもとに算出される。
【００４０】
データストリームＸ＝（ｘ１，ｘ２，…，ｘｎ）が与えられているとき、Ｘの時系列の和Ｓｘ、２乗和Ｓｘｘは、それぞれ以下の（式２）のように計算される。要約情報計算部１０は、計算したＳｘおよびＳｘｘを遅延相関計算部２０に通知する。
【数２】
0004452234.tif 000003
【００４１】
また、要約情報計算部１０は、各データストリームのペアに対して、一つの相関値のみならず様々な遅延がある場合の相関値も計算する。したがって、要約情報計算部１０は、
データストリームＸについては以下の（式３）のように、データストリームＹについては以下の（式４）のように、それぞれ複数個の和と分散を計算する。ここで、ｌは、遅延の大きさである。
【数３】
0004452234.tif 000004
【００４２】
なお、要約情報のランダム射影とは、コンピュータ科学において使われている次元縮退のための一手法であり、時系列から空間ベクトルへの射影（マッピング）にはランダム関数が用いられる。ランダム射影は、例えば、文献（Dimitris Achlioptas“Database-friendly random projections.”In Proceedings of PODS,pp.274-281,May 2001.）に記載されている。Ｘのランダム射影のベクトルをＰｘ=（ｐ１，ｐ２，…，ｐｄ）、Ｐｘの次元数をｄ、ランダム関数をＵ＝（ｕｔｉ）とすると、Ｐｘにおけるｉ次元の値は、以下の（式５）となる。
【数４】
0004452234.tif 000005
【００４３】
ここで、要約情報計算部１０は、遅延ｌを考慮した場合、和と分散と同様に、複数のランダム射影Ｐｘ（ｌ＋１，ｎ）を計算する。これはデータストリームＹについても同様であり、要約情報計算部１０は、Ｐｙ（１，ｎ−ｌ）を計算する。
【００４４】
遅延相関計算部２０は、アプリケーションもしくは利用者からの問合せ要求を受け付けると、要約情報計算部１０が計算したデータストリームの要約情報を用いて、遅延相関の計算を行う。要約情報計算部１０は、１回の問合せ要求を受け付けると、データストリーム処理装置１に入力されたデータストリームのペアを総当たりで調査し、遅延相関を有するペアおよびその遅延値をリストとして出力する。
【００４５】
遅延相関計算部２０は、要約情報を用いて、データストリームのペアの相互相関関数を計算する。まず、ランダム射影と時系列の２乗和を用いて内積を計算する（式６）。そして、遅延相関計算部２０は、計算した内積を用いて相互相関関数Ｒ（ｌ）を計算する（式７）。
【数５】
0004452234.tif 000006
【００４６】
図２は、データストリーム処理の概要を示すフローチャートである。
【００４７】
まず、データストリーム処理装置１は、データストリームの更新があるか否かを判定する（Ｓ１０１）。データストリームの更新は、要約情報計算部１０に過去に入力されていないデータストリームの新たなデータが、新たに要約情報計算部１０に入力されたことを示す。データストリームの更新がないときには（Ｓ１０１，Ｎｏ）、処理をＳ１０３に進める。データストリームの更新があるときには（Ｓ１０１，Ｙｅｓ）、サブルーチン処理「要約情報の更新処理」を呼び出して（Ｓ１０２）、処理をＳ１０３に進める。
【００４８】
次に、データストリーム処理装置１は、問い合わせ要求があるか否かを判定する（Ｓ１０３）。問い合わせ要求がないときには（Ｓ１０３，Ｎｏ）、処理をＳ１０１に戻す。以下、問い合わせ要求があるとき（Ｓ１０３，Ｙｅｓ）の処理を説明する。
【００４９】
データストリーム処理装置１は、サブルーチン処理「遅延情報の計算処理」を呼び出し（Ｓ１０４）、その結果である遅延相関を有するペアおよびその遅延値をリストとして出力する。
【００５０】
さらに、データストリーム処理装置１は、Ｓ１０４で算出した結果を入力として、遅延情報の応用処理を実行してもよい（Ｓ１０５）。遅延情報の応用処理は、例えば、センサネットワークにおける故障検出である。具体的には、データストリーム処理装置１は、連動（すなわち相関）するべきセンサ２のペアをあらかじめ登録しておき、Ｓ１０４で算出した遅延相関のあるセンサ２のペアとして検出されなければ、故障の可能性を示唆することができる。
【００５１】
遅延情報の応用処理（Ｓ１０５）の他の一例として、センサ２が測定するネットワークトラヒックの異常検出が挙げられる。ネットワークトラヒックは、例えば、毎週同じ曜日には、ほぼ同じ測定値が期待されるとする。そして、同じセンサ２において先週測定した測定値と、今週測定した測定値との相関を調べ、相関がないときには、ネットワークトラヒックの異常検出を通知する。
【００５２】
図３は、「要約情報の更新処理」（Ｓ１０２）を示すフローチャートである。
【００５３】
まず、要約情報計算部１０は、ループ変数ｋを１からｍまで１つずつ加算するループ（Ｓ２０１〜Ｓ２０９）を実行する。要約情報計算部１０は、変数Ｘにｋ番目のデータストリームを代入する（Ｓ２０２）。そして、要約情報計算部１０は、時刻ｔにおいて、ｘｔを受信する（Ｓ２０３）。要約情報計算部１０は、ＳｘにＳｘ＋ｘｔを、および、ＳｘｘにＳｘｘ＋ｘｔ２を、それぞれ代入する（Ｓ２０４）。なお、Ｓ２０４における各パラメータは、（式２，３，６，７）に記載されている。
【００５４】
そして、要約情報計算部１０は、ループ変数ｉを１からｄまで１つずつ加算するループ（Ｓ２０５〜Ｓ２０８）を実行する。要約情報計算部１０は、ランダム関数からｕｔｉを生成し（Ｓ２０６）、ｐｉにｐｉ＋ｘｔｕｔｉを代入する（Ｓ２０７）。なお、Ｓ２０７における各パラメータは、（式５）に記載されている。以上、図３の処理について、説明した。
【００５５】
以上説明した要約情報計算部１０は、Ｏ（ｍ）の計算コストとメモリ使用量で済むので、計算コストとメモリ使用量の低減化が可能となる。なお、非特許文献２の方式では、ｍ個のデータストリームを扱う場合、非特許文献２が全てのデータストリームのペアの内積を計算しなければならないため、要約情報の更新にＯ（ｍ２）の計算コストとメモリ使用量が必要であり、非効率であった。
【００５６】
ここで、要約情報計算部１０の計算コストがＯ（ｍ）であることを説明する。図３において、ループは、２つ存在する。１つめのループ（Ｓ２０１〜Ｓ２０９）は、ループ変数ｋの上限値がｍであるため、計算コストは、Ｏ（ｍ）である。そして、２つめのループ（Ｓ２０５〜Ｓ２０８）は、ループ変数ｉの上限値がｄである。ここで、ｄは、ランダム射影のベクトルＶｘの次元数である。この次元数ｄは、１つのデータストリームの属性であるので、要約情報計算部１０に入力された他のデータストリームの個数ｍには依存しないパラメータである。よって、１からｄまでのループは、計算量のオーダーに影響しないので、図３のトータルの計算コストは、Ｏ（ｍ）である。
【００５７】
図４は、「遅延情報の計算処理」（Ｓ１０４）を示すフローチャートである。
【００５８】
まず、遅延相関計算部２０は、ループ変数ｋを１からｍまで１つずつ加算するループ（Ｓ３０１〜Ｓ３０８）を実行する。遅延相関計算部２０は、変数Ｘにｋ番目のデータストリームを代入する（Ｓ３０２）。そして、遅延相関計算部２０は、ループ変数ｊをｋからｍまで１つずつ加算するループ（Ｓ３０３〜Ｓ３０７）を実行する。
【００５９】
遅延相関計算部２０は、変数Ｙにｊ番目のデータストリームを代入する（Ｓ３０４）。遅延相関計算部２０は、Ｘの要約情報（Ｓｘ，Ｓｘｘ，Ｐｘ）とＹの要約情報（Ｓｙ，Ｓｙｙ，Ｐｙ）から相互相関関数を計算する（Ｓ３０５）。遅延相関計算部２０は、Ｓ３０５で計算した相互相関関数から遅延情報を検出する（Ｓ３０６）。
【００６０】
なお、遅延情報の検出（Ｓ３０６）は、具体的には以下の通りである。時系列ＸとＹが与えられたとき、以下の条件を満たすとき、ＸとＹはｌの遅延相関を持つと定義される。よって、以下の条件を満たすか否かによって、遅延情報の検出が可能か否かを判定する。
（１）相関値の絶対値｜Ｒ（ｌ）｜をスコアとすると、ｘｔとｙｔ−ｌのスコアが閾値γを超える極大値である。
（２）複数の極大値がある場合は、最初の極大値を指す。
【００６１】
ここで、図４において、遅延相関計算部２０の計算コストは、Ｏ（ｍ２）である。しかし、図４の処理を起動させる契機が、問い合わせ要求であるので、図３の処理を起動させる契機（データストリームの更新）よりも極めて頻度が少ない。よって、図４の処理の計算コストは、図３の処理に比べて大きく影響しない。
【００６２】
以上説明したデータストリーム処理装置１は、インクリメンタルに要約情報を更新することを特徴とする。インクリメンタルとは、繰り返し動作の状態において、あるデータ項目に対してある一定の規則で量または値を加算することを意味する。要約情報計算部１０は、要約情報にランダム射影を用いているため、インクリメンタルに要約情報を更新することができる。それにより、オリジナルのデータストリームを破棄してもよいので、メモリ使用量を節約できる。そして、遅延相関計算部２０では、オリジナルのデータストリームを使わず、インクリメンタルに更新されている各要約情報のみを用いて、相関のあるデータストリームのペアおよびその遅延値を見つける。
【００６３】
なお、データストリーム処理装置１は、１台の計算機により構成されてもよいし、複数の計算機により構成されてもよい。例えば、センサ２ごとにデータストリームは生成されるので、センサ２ごとにデータストリーム処理装置１を設けて、並列に図３および図４の処理を実行させてもよい。そのときには、図３のループ（Ｓ２０１〜Ｓ２０９）および図４のループ（Ｓ３０１〜Ｓ３０８）は、センサ２を担当するデータストリーム処理装置１に分配される。また、センサ２とデータストリーム処理装置１とを、同一の筐体に収容してもよい。
【００６４】
以上説明したデータストリーム処理装置１を、以下で評価する。評価は、出力結果の精度と計算時間という２つの尺度でそれぞれ行っている。以下に示すように、本実施形態のデータストリーム処理装置１は、出力結果の精度を落とすことなく、計算時間の短縮化を実現している。
【００６５】
図５は、出力結果の精度を示すための実験結果を示す。図５（ａ）の光センサＣ、および、図５（ｂ）の光センサＤは、それぞれ照明のセンサデータである。図５（ｃ）の相互相関関数では、点線は相互相関関数をそのまま計算した結果であり、「ナイーブな手法」と表記している。図５（ｃ）の実線は本実施形態によって近似的に計算した結果である。これら２本の線は、ほぼ同じ結果をなぞっているので、本実施形態は、非常に高精度に近似していることが分かる。なお、非特許文献２の手法で求まる解は、本実施形態と同じように近似解である。よって、本実施形態の結果は、非特許文献２の結果と比較する代わりに、ナイーブな手法と比較することにより、充分な精度を実証できた。
【００６６】
なお、図５（ｃ）の実線上の「＊」マークは、計算値を示す。そして、図５（ｃ）における実線は、計算値をなめらかにつなぐことにより生成される。ここで、図５（ｃ）では、計算値が横軸の左にいくほど密になり、右にいくほど粗になる。これは、データストリームのサンプリング間隔が、一定ではなく、指数関数に基づいているためである。例えば、時刻ｔ＝１，２，４，８，１６，…においてサンプリングする。これにより、計算値の精度を大きく落とすことなく、計算値の個数を少なくすることができるので、計算量を適切に削減することができる。
【００６７】
図６は、ナイーブな手法と本実施形態の手法の計算時間を比較したものである。横軸で示すデータストリームの数の増加に対して、縦軸の計算時間に着目する。ナイーブな手法は、計算時間が指数関数的に増加してしまうのに対し、本実施形態の手法は、データストリームの数の増加に影響されず、ほぼ一定の計算時間で済む。これにより、本実施形態の手法が、大幅な計算コストの低減化を達成していることが分かる。
【図面の簡単な説明】
【００６８】
【図１】本発明の一実施形態に関するデータストリーム処理装置を示す構成図である。
【図２】本発明の一実施形態に関するデータストリーム処理の概要を示すフローチャートである。
【図３】本発明の一実施形態に関する要約情報の計算手順を示すフローチャートである。
【図４】本発明の一実施形態に関する遅延相関の計算手順を示すフローチャートである。
【図５】本発明の一実施形態に関する遅延相関の精度の実験結果を示すグラフである。
【図６】本発明の一実施形態に関する遅延相関を計算するための計算時間の実験結果を示すグラフである。
【図７】本発明の一実施形態に関する従来の技術の中で、遅延相関の例を示すグラフである。
【符号の説明】
【００６９】
１      データストリーム処理装置
２      センサ
１０    要約情報計算部
２０    遅延相関計算部
【図１】
0004452234.tif 000007
【図２】
0004452234.tif 000008
【図３】
0004452234.tif 000009
【図４】
0004452234.tif 000010
【図５】
0004452234.tif 000011
【図６】
0004452234.tif 000012
【図７】
0004452234.tif 000013