(57)【要約】【課題】ＤＴＷを使用したデータストリーム監視において、計算コストの低減を図ること。【解決手段】本発明は、データストリームから問合せシーケンスと類似する部分シーケンスをダイナミックタイムワーピング距離に基づいて検出するデータストリーム監視装置１である。その記憶部４は、問合せシーケンス４１、単一のタイムワーピング行列、および、ダイナミックタイムワーピング距離に関する所定の閾値を記憶している。また、その処理部７は、ある時刻にデータストリーム中の１つのデータを受信した場合、問合せシーケンス４１の先頭にそのデータと同じデータを付加してから、タイムワーピング行列を使ってダイナミックタイムワーピング距離を算出し、そのダイナミックタイムワーピング距離が所定の閾値以下のときに、類似する部分シーケンスがあったと判断する。【選択図】図１
2008134706.tif 000002
【特許請求の範囲】
【請求項１】
継続的に受信するデータであるデータストリームから、所定のデータ列である問合せシーケンスと類似する部分シーケンスを、ダイナミックタイムワーピング距離に基づいて検出するデータストリーム監視装置であって、
前記問合せシーケンス、その問合せシーケンスに関する単一のタイムワーピング行列、および、前記ダイナミックタイムワーピング距離に関する所定の閾値を記憶する記憶部と、
ある時刻に前記データストリーム中の１つのデータを受信した場合、前記問合せシーケンスの先頭にその１つのデータと同じデータを付加してから、前記タイムワーピング行列を使って前記ダイナミックタイムワーピング距離を算出し、そのダイナミックタイムワーピング距離が前記所定の閾値以下のときに、そのダイナミックタイムワーピング距離に対応する部分シーケンスを前記類似する部分シーケンスとして検出する処理部と、
を有することを特徴とするデータストリーム監視装置。
【請求項２】
前記処理部は、前記タイムワーピング行列の各行列要素の値を算出する場合、当該値とともに、その値を算出するために使用した前記データストリーム中のデータの受信時刻のうち最初の時刻を開始時刻として前記記憶部に記憶させ、前記類似する部分シーケンスを検出したときに、該当する前記開始時刻も特定する
ことを特徴とする請求項１に記載のデータストリーム監視装置。
【請求項３】
前記処理部は、前記類似する部分シーケンスを検出した場合、その後、さらに、前記タイムワーピング行列の各行列要素の値の算出を行い、その類似する部分シーケンスと時間帯が一部でも重複する部分シーケンスの中で、前記ダイナミックタイムワーピング距離がより小さいものがないと判断したときに、その類似する部分シーケンスをより適切な部分シーケンスとして検出する
ことを特徴とする請求項２に記載のデータストリーム監視装置。
【請求項４】
前記処理部は、前記類似する部分シーケンスを検出した場合、その類似する部分シーケンスの最後のデータの受信時刻を終了時刻とすると、その終了時刻後における前記タイムワーピング行列のある列において、各行列要素のうち、その開始時刻が前記終了時刻以前であって、かつ、その値が前記類似する部分シーケンスのダイナミックタイムワーピング距離よりも小さいものがないときに、その類似する部分シーケンスをより適切なものとして検出する
ことを特徴とする請求項３に記載のデータストリーム監視装置。
【請求項５】
継続的に受信するデータであるデータストリームから、所定のデータ列である問合せシーケンスと類似する部分シーケンスを、ダイナミックタイムワーピング距離に基づいて検出するデータストリーム監視装置によるデータストリーム監視方法であって、
前記データストリーム監視装置は、記憶部と処理部を備え、
前記記憶部は、
前記問合せシーケンス、その問合せシーケンスに関する単一のタイムワーピング行列、および、前記ダイナミックタイムワーピング距離に関する所定の閾値を記憶し、
前記処理部は、
ある時刻に前記データストリーム中の１つのデータを受信した場合、前記問合せシーケンスの先頭にその１つのデータと同じデータを付加してから、前記タイムワーピング行列を使って前記ダイナミックタイムワーピング距離を算出し、そのダイナミックタイムワーピング距離が前記所定の閾値以下のときに、そのダイナミックタイムワーピング距離に対応する部分シーケンスを前記類似する部分シーケンスとして検出する
ことを特徴とするデータストリーム監視方法。
【請求項６】
前記処理部は、前記タイムワーピング行列の各行列要素の値を算出する場合、当該値とともに、その値を算出するために使用した前記データストリーム中のデータの受信時刻のうち最初の時刻を開始時刻として前記記憶部に記憶させ、前記類似する部分シーケンスを検出したときに、該当する前記開始時刻も特定する
ことを特徴とする請求項５に記載のデータストリーム監視方法。
【請求項７】
前記処理部は、前記類似する部分シーケンスを検出した場合、その後、さらに、前記タイムワーピング行列の各行列要素の値の算出を行い、その類似する部分シーケンスと時間帯が一部でも重複する部分シーケンスの中で、前記ダイナミックタイムワーピング距離がより小さいものがないと判断したときに、その類似する部分シーケンスをより適切な部分シーケンスとして検出する
ことを特徴とする請求項６に記載のデータストリーム監視方法。
【請求項８】
前記処理部は、前記類似する部分シーケンスを検出した場合、その類似する部分シーケンスの最後のデータの受信時刻を終了時刻とすると、その終了時刻後における前記タイムワーピング行列のある列において、各行列要素のうち、その開始時刻が前記終了時刻以前であって、かつ、その値が前記類似する部分シーケンスのダイナミックタイムワーピング距離よりも小さいものがないときに、その類似する部分シーケンスをより適切なものとして検出する
ことを特徴とする請求項７に記載のデータストリーム監視方法。
【請求項９】
請求項５から請求項８のいずれか１項に記載のデータストリーム監視方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１０】
請求項９のプログラムを記録することを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、継続して大量に流入してくるデータをリアルタイムに分析する技術（ストリームマイニング技術）に関する。
【背景技術】
【０００２】
近年、コンピュータ装置やネットワークに関する技術が発達し、ネットワーク上を大量のデータが継続的に流通することも少なくない。ネットワーク上で継続して大量に流通するデータのことをデータストリームと呼ぶが、データストリームの例としては、たとえば、インターネットにおける株価などの金融データや、ＬＡＮ（Local Area Network）などのセンサネットワークにおけるセンサデータ（温度センサや照度センサの計測データなど）などが挙げられる。
【０００３】
そして、ストリームマイニング技術は、データベースに蓄えられた大容量のデータを分析するのではなく、継続的に受信する大量のデータをリアルタイムで分析しなくてはならないため、計算の高速化と省メモリ化を図る必要がある。また、そうすれば、利用者に対して必要な情報を迅速に提供することもできる。
【０００４】
データストリームの分析としては、たとえば、ある問合せシーケンス（所定のデータ列）とある程度類似するシーケンスがデータストリーム中にあるか否かを、部分的なシーケンスマッチングによって見つける手法がある。この場合、データストリームのサンプリングレートなどによって、データストリームと問合せシーケンスでは相対的な経時速度が異なることもあるので、データの時間軸方向の伸縮も考慮に入れたマッチングを行うことが望ましい。
【０００５】
そこで、動的計画法として、シーケンス間の時間軸方向の伸縮も考慮に入れ、シーケンス間の距離を最小化するように時間軸方向の調整を行いながらシーケンスマッチングを行う技術であるダイナミックタイムワーピング（ＤＴＷ：Dynamic Time Warping）が、広く使用されている。
このＤＴＷに基づいて作成および保存される行列をタイムワーピング行列と呼び、そのタイムワーピング行列によって２つのシーケンス間の距離であるＤＴＷ距離を算出することができる。ＤＴＷ距離が小さいほど、２つのシーケンスは類似していることになる。
【０００６】
たとえば、非特許文献１と非特許文献２には、ＤＴＷに基づく類似部分シーケンスの検出の高速化に関する技術が記載されている。
また、非特許文献３には、データストリームのリアルタイム分析手法として、データストリーム中のデータ同士の相関係数も考慮することで精度を上げたStatStreamに関する技術が記載されている。
さらに、非特許文献４には、データストリームのリアルタイム分析手法において使用する、データ間の遅延相関を検出するアルゴリズムであるＢＲＡＩＤに関する技術が記載されている。
【非特許文献１】Emonn Keogh,Exact Indexing of Dynamic Time Warping,Proceedings of the Twenty-eighth International Conference on VLDB(Very Large Data Bases),China,August 2002,pp.406-417
【非特許文献２】Yasushi Sakurai,MasatoshiYoshikawa,Christos Faloutsos,FTW:FastSimilarity Search under the Time Warping Distance, Proceedings of Symposium on PODS(Principles of Database Systems),USA,June 2005,pp.326-337
【非特許文献３】Yunyue Zhu,Dennis Shasha,StatStream:StatisticalMonitoring of Thousands of Data Streams in Real Time,Proceedingsof the Twenty-eighth International Conference on VLDB(Very Large Data Bases),China,August 2002,pp.358-369
【非特許文献４】Yasushi Sakurai,Spiros Papadimitriou, Christos Faloutsos,BRAID:StreamMining through Group Lag Correlations, Proceedings of ACM SIGMOD(Association For Computing Machinery Special Interest Group On Management Of Data),USA,June 2005,pp.599-610
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１および非特許文献２は、蓄積されたデータ集合に適用する技術であり、データストリームのリアルタイム分析のための技術ではない。
また、非特許文献３および非特許文献４は、時間軸方向に調整を行うことなくシーケンスマッチングを行うものであり、ＤＴＷを使用したデータストリーム監視に関する技術ではない。
【０００８】
そして、ＤＴＷを使用したデータストリーム監視を行おうとすると、データストリームの長さに比例して計算量やメモリの使用量が増大してしまい、実用的ではなかった（詳細は、発明を実施するための最良の形態の比較例の説明を参照）。
そこで、本発明は、前記問題点に鑑みてなされたものであり、ＤＴＷを使用したデータストリーム監視において、計算コスト（計算量やメモリの使用量）の低減を図ることを目的とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、請求項１および請求項５に係る発明は、継続的に受信するデータであるデータストリームから、所定のデータ列である問合せシーケンスと類似する部分シーケンスを、ダイナミックタイムワーピング距離に基づいて検出するデータストリーム監視装置において、記憶部が、問合せシーケンス、その問合せシーケンスに関する単一のタイムワーピング行列、および、ダイナミックタイムワーピング距離に関する所定の閾値を記憶する。
そして、処理部は、ある時刻にデータストリーム中の１つのデータを受信した場合、問合せシーケンスの先頭にその１つのデータと同じデータを付加してから、タイムワーピング行列を使ってダイナミックタイムワーピング距離を算出し、そのダイナミックタイムワーピング距離が所定の閾値以下のときに、そのダイナミックタイムワーピング距離に対応する部分シーケンスを類似する部分シーケンスとして検出する。
【００１０】
かかる発明によれば、タイムワーピング行列が単一であることで、計算コストの低減を図ることができる。
【００１１】
請求項２および請求項６に係る発明は、処理部が、タイムワーピング行列の各行列要素の値を算出する場合、当該値とともに、その値を算出するために使用したデータストリーム中のデータの受信時刻のうち最初の時刻を開始時刻として記憶部に記憶させ、類似する部分シーケンスを検出したときに、該当する開始時刻も特定することを特徴とする。
【００１２】
かかる発明によれば、類似する部分シーケンスの開始時刻も特定することができる。
【００１３】
請求項３および請求項７に係る発明は、処理部が、類似する部分シーケンスを検出した場合、その後、さらに、タイムワーピング行列の各行列要素の値の算出を行い、その類似する部分シーケンスと時間帯が一部でも重複する部分シーケンスの中で、ダイナミックタイムワーピング距離がより小さいものがないと判断したときに、その類似する部分シーケンスをより適切な部分シーケンスとして検出することを特徴とする。
【００１４】
かかる発明によれば、類似する部分シーケンスと時間帯が重複する部分シーケンスを、その後、さらに調べることで、その類似する部分シーケンスがより適切な部分シーケンスであると判断することができる。
【００１５】
請求項４および請求項８に係る発明は、処理部が、類似する部分シーケンスを検出した場合、その類似する部分シーケンスの最後のデータの受信時刻を終了時刻とすると、その終了時刻後におけるタイムワーピング行列のある列において、各行列要素のうち、その開始時刻が終了時刻以前であって、かつ、その値が類似する部分シーケンスのダイナミックタイムワーピング距離よりも小さいものがないときに、その類似する部分シーケンスをより適切なものとして検出することを特徴とする。
【００１６】
かかる発明によれば、類似する部分シーケンスの終了時刻後におけるタイムワーピング行列のある列における各行列要素について上記のように調べることで、その部分シーケンスをより適切なものとして判断することができる。
【００１７】
請求項９に係る発明は、請求項５から請求項８のいずれか１項に記載のデータストリーム監視方法をコンピュータに実行させることを特徴とするプログラムである。
【００１８】
かかる発明によれば、データストリーム監視方法をコンピュータに実行させることができる。
【００１９】
請求項１０に係る発明は、請求項９のプログラムを記録することを特徴とする記録媒体である。
【００２０】
かかる発明によれば、データストリーム監視方法のプログラムを記録することができる。
【発明の効果】
【００２１】
本発明によれば、ＤＴＷを使用したデータストリーム監視において、計算コストの低減を図ることができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明に係るデータストリーム監視装置を実施するための最良の形態（以下、実施形態という。）について、適宜図面を参照しながら説明する。なお、参照図以外の図も適宜参照する。
その前に、理解を容易にするため、図８および図９を参照しながら、ＤＴＷを使用したデータストリーム監視の比較例（従来技術）について説明する。
【００２３】
図８は、ＤＴＷを使用したデータストリーム監視の比較例における、問合せ処理のイメージを示した図である。
図８において、シーケンスＹは、固定長ｍのデータであり、シーケンスの類似判断の元となるデータである。
【００２４】
データストリームであるシーケンスＸは、時々刻々と伸張している（データ量が増えている）シーケンスであり、その長さをｎとし、また、シーケンスの類似判断の対象となるデータである。
ＴＷＭ（タイムワーピング行列）１〜Ｓは、それぞれ時刻ｔ＝１〜ｔ＝Ｓから始まるタイムワーピング行列である。また、ＴＷＭＳに示した黒いマスのつながりは、ワーピングパス（後記するＤＴＷ距離を算出するためにたどるルート）である。
【００２５】
ここで、目的は、ＤＴＷ距離に基づき、シーケンスＸにおいて、シーケンスＹと類似する部分シーケンスを検出することである。以下、図８を参照しながらその概要を説明し、その後、図９を参照しながら具体例について説明する。なお、類似する部分シーケンスの検出方法は２つあり、それらを第１の方法、第２の方法と呼ぶ。まず、第１の方法について説明する。
【００２６】
（第１の方法）
２つのシーケンス間のＤＴＷ距離とは、２つのシーケンスを、全体的あるいは部分的に時間軸方向に伸縮の調整を行った後の距離のことである。ＤＴＷ距離は、タイムワーピング行列に基づいて算出することができる。
長さｍのシーケンスＹ＝（ｙ１，ｙ２，・・・，ｙｍ）と長さｎのシーケンスＸ＝（ｘ１，ｘ２，・・・，ｘｎ）の間のＤＴＷ距離Ｄ（Ｘ，Ｙ）は、以下の式（１）〜（４）のようにして求めることができる。なお、ｔ＝（１，２，・・・，ｎ）、ｉ＝（１，２，・・・，ｍ）とする。
【００２７】
Ｄ（Ｘ，Ｙ）＝ｆ（ｎ，ｍ）・・・（１）
ｆ（ｔ，ｉ）＝||ｘｔ−ｙｉ||＋ｍｉｎ｛ｆ（ｔ，ｉ−１），ｆ（ｔ−１，ｉ），
ｆ（ｔ−１，ｉ−１）｝・・・（２）
ｆ（０，０）＝０・・・（３）
ｆ（ｔ，０）＝ｆ（０，ｉ）＝∞・・・（４）
【００２８】
式（１）は、ＤＴＷ距離の定義である。式（２）は、具体的な計算式である。
式（２）において、||ｘｔ−ｙｉ||は、２つの数値（ｘｔとｙｉ）の距離を表す。２つの数値の距離としては、たとえば、ユークリッド距離やマンハッタン距離が考えられる。ｎ次元空間において、ａ、ｂという２つの点の座標をａ（ａ１，ａ２，・・・，ａｎ）、ｂ（ｂ１，ｂ２，・・・，ｂｎ）とし、また、（１≦ｊ≦ｎ）とすると、ユークリッド距離とは√（Σ（ａｊ−ｂｊ）２）、マンハッタン距離とはΣ｜ａｊ−ｂｊ｜で表される距離のことである。
以下の具体例では、計算を容易にするために、||ｘｔ−ｙｉ||として、ユークリッド距離の二乗の値を算出し、使用する。
【００２９】
また、式（２）において、ｍｉｎ｛ｆ（ｔ，ｉ−１），ｆ（ｔ−１，ｉ），ｆ（ｔ−１，ｉ−１）｝は、｛｝内の３つの値のうち、最小のものを採用する、という意味である。なお、最小のものが２つあるいは３つある場合については、検出される部分シーケンスが長くなるような（あるいは短くなるような）値を選択する、あるいは、検出される部分シーケンスが問合せシーケンスＹに近くなるような値を選択する、など、予めその選択基準を設定しておいてもよい。
式（３）および式（４）は、この３つの値を計算する際に使用する、タイムワーピング行列における境界条件である。
【００３０】
タイムワーピング行列は、ＤＴＷの関数の値、すなわち、上記式（２）におけるｆ（ｔ，ｉ）の値を保持するものである。比較例では、長さｎのシーケンスＸと長さｍのシーケンスＹの距離を求めるときに、ｎ個のタイムワーピング行列を使用するため、計算にＯ（ｎｍ）（ｎとｍの積に比例）の時間がかかってしまう。つまり、この方法では、ｎの値が大きくなると、計算時間が長くなりすぎて、実用に耐えない。
【００３１】
なお、メモリの使用量はＯ（ｍ）である。これは、タイムワーピング行列の情報として、現在時刻の列（タイムワーピング行列におけるその時刻の各行列要素の集合）の情報とその直前時刻の列の情報の計２列の情報だけを記憶しておけばよく、それ以前の情報は逐次消去可能だからである。
【００３２】
また、Ｘ［ｔｓ：ｔｅ］を、時刻ｔｓから時刻ｔｅまでの部分シーケンスとする。すなわち、Ｘ＝（ｘ１，ｘ２，・・・，ｘｓ，・・・，ｘｅ，・・・，ｘｎ）において、Ｘ［ｔｓ：ｔｅ］＝（ｘｓ，・・・，ｘｅ）である。ここでの目的は、固定長ｍの問合せシーケンスＹと高い類似性を有するＸ［ｔｓ：ｔｅ］を発見（検出）することである。
【００３３】
第１の方法では、所定の閾値εを設定しておき、次の式（５）を満たすＸ［ｔｓ：ｔｅ］を検出する。
Ｄ（Ｘ［ｔｓ：ｔｅ］，Ｙ）≦ε・・・（５）
【００３４】
第１の方法の具体例を、図９を参照しながら説明する。図９は、比較例におけるタイムワーピング行列の例を示した図である。
ここでは、時間経過とともに伸張するシーケンスＸにおいて、シーケンスＹ＝（１１，６，９，４）と高い類似性を有する部分シーケンスを検出することを目的とする。図９（１）〜（７）では、シーケンスＸの長さが「７」（Ｘ＝（５，１２，６，１０，６，５，１））のときのタイムワーピング行列（ＴＷＭ）１〜７（それぞれ太線の内部）の状態を示している。なお、閾値ε＝２０とする。
【００３５】
また、上記式（１）〜（４）を、実際に各ＴＷＭ１〜７の各要素（各行列要素）の値を算出するための式に変形すると、以下の式（６）〜（９）のようになる。
つまり、ｔ番目のタイムワーピング行列（時刻ｔから始まるタイムワーピング行列）において、要素（ｋ，ｉ）のＤＴＷ距離をｆｔ（ｋ，ｉ）とする。なお、ｔ＝（１，２，・・・，ｎ）、ｉ＝（１，２，・・・，ｍ）、ｋ＝（１，２，・・・，ｎ−ｔ＋１）とする。また、式（１）〜（４）と重複する事項に関しては、説明を適宜省略する。
【００３６】
Ｄ（Ｘ［ｔｓ：ｔｅ］，Ｙ）＝ｆｔｓ（ｔｅ−ｔｓ＋１，ｍ）＝ｍｉｎ（ｆｔ（ｋ，ｍ））・・・（６）
ｆｔ（ｋ，ｉ）＝||ｘｔ＋ｋ−１−ｙｉ||＋ｍｉｎ｛ｆｔ（ｋ，ｉ−１），ｆｔ（ｋ−１，ｉ），ｆｔ（ｋ−１，ｉ−１）｝・・・（７）
ｆｔ（０，０）＝０・・・（８）
ｆｔ（ｋ，０）＝ｆｔ（０，ｉ）＝∞・・・（９）
【００３７】
式（６）は、ＤＴＷ距離の定義である。式（７）は、具体的な計算式である。式（８）および式（９）は、タイムワーピング行列における境界条件である。
【００３８】
次に、図９を参照しながら、具体的な計算について説明する。
ＴＷＭ１〜７の各要素には、上記式（６）〜（９）にしたがって算出された値が格納されている。
ＴＷＭ２を例にとって説明すると、上記式（６）〜（９）から、まず、時刻ｔ＝２のとき、ｆ２（１，１）＝（１２−１１）２＋ｍｉｎ｛ｆ２（１，０）＝∞，ｆ２（０，１）＝∞，ｆ２（０，０）＝０｝＝１＋０＝１である。
また、ｆ２（２，１）＝（６−１１）２＋ｍｉｎ｛ｆ２（２，０）＝∞，ｆ２（１，１）＝１，ｆ２（１，０）＝∞｝＝２５＋１＝２６である。
【００３９】
さらに、ｆ２（１，２）＝（１２−６）２＋ｍｉｎ｛ｆ２（１，１）＝１，ｆ２（０，２）＝∞，ｆ２（０，１）＝∞｝＝３６＋１＝３７である。
また、ｆ２（２，２）＝（６−６）２＋ｍｉｎ｛ｆ２（２，１）＝２６，ｆ２（１，２）＝３７，ｆ２（１，１）＝１｝＝０＋１＝１である。
以下、同様にして、各ＴＷＭ１〜７における各要素の値を算出することができる。
【００４０】
そして、各ＴＷＭ１〜７のそれぞれの時刻において、それ以前のｙ４のときの要素の値のうち最小の値がＤＴＷ距離となる。また、各ＴＷＭ１〜７における各ＤＴＷ距離の開始時刻（計算に使用したシーケンスＸの値のうち最初の値の時刻）は、各ＴＷＭ１〜７の番号（ＴＷＭ１なら「１」、ＴＷＭ３なら「３」）と一致している。
【００４１】
このような状況で、シーケンスＸにおいて、シーケンスＹと類似性の高い部分シーケンスを検出する、すなわち、ＤＴＷ距離が「２０」以下になっているものを検出する。
まず、時刻ｔ＝１においては、タイムワーピング行列がＴＷＭ１しか存在せず、ＤＴＷ距離が「５４」なので、該当しない。
【００４２】
次に、時刻ｔ＝２において、ＴＷＭ１のＤＴＷ距離は「５４」、ＴＷＭ２のＤＴＷ距離は「１１０」なので、該当しない。
そして、時刻ｔ＝３において、ＴＷＭ１のＤＴＷ距離は「５０」、ＴＷＭ２のＤＴＷ距離は「１４」、ＴＷＭ３のＤＴＷ距離は「３８」であり、ＴＷＭ２が該当（「ＤＴＷ距離が「２０」以下」の条件を充足）するので、部分シーケンスＸ［２：３］を発見できたことになる。
【００４３】
このようにして、比較例によれば、シーケンスＸの長さがｎのときには、ｎ個のタイムワーピング行列を使用することで、目的の類似する部分シーケンスを発見することができる。
ただし、上記式（６）〜（９）と図９による具体例からもわかるように、各ＴＷＭ１〜７は、現在時刻およびその直前の時刻の２列分の情報のみをメモリに記憶させておけばよく、それよりも前の情報は逐次消去することができる。
【００４４】
そして、第１の方法によれば、ＤＴＷ距離が閾値ε以下になった場合に、該当する部分シーケンスを検出したことになる。しかし、利用者の都合などによっては、その直後に、より類似性の高い部分シーケンスが存在する場合には、最初の部分シーケンスは検出したことにせず、後のより類似性の高い部分シーケンスのみを検出したことにしたい場合も多い。
【００４５】
（第２の方法）
そこで、第２の方法では、最初に類似する部分シーケンスを検出した後、その類似する部分シーケンスと時間帯が少しでも重複する部分シーケンスの中で、より類似性の高い（ＤＴＷ距離が小さい）ものがあるか否かを調べる。つまり、類似する部分シーケンスを検出した後、時間帯が少しでも重複する部分シーケンスの中で、より類似性の高いものがないことが確定して初めて、それを該当する部分シーケンス（以下、「最適な部分シーケンス」という。）と判断するのである。
【００４６】
図９の例では、時刻ｔ＝３において、ＴＷＭ２のＤＴＷ距離が「１４」となり、まず、閾値ε以下という条件をクリアする部分シーケンスＸ［２：３］を発見できたことになる。この部分シーケンスは終了時刻がｔ＝３なので、開始時刻がそれよりも後であるＴＷＭ４〜７は考慮する必要がない。
【００４７】
そこで、ＴＷＭ１〜３において、時刻ｔ＝３よりも後に、ＤＴＷ距離が「１４」よりも小さくなる可能性があるか否かが問題になる。まず、ＴＷＭ１では、時刻ｔ＝３のときの各要素の値（下から、「６２」，「３７」，「４６」，「５０」）がすでにいずれも「１４」よりも大きいので、その後、ＤＴＷ距離が「１４」よりも小さくなる可能性はない。同様に、ＴＷＭ３についても、時刻ｔ＝３よりも後に、ＤＴＷ距離が「１４」よりも小さくなる可能性はない。
【００４８】
ただし、ＴＷＭ２では、時刻ｔ＝３のとき、ｆ２（２，２）＝１、ｆ２（２，３）＝１０であり、その後、ＤＴＷ距離が「１４」よりも小さくなる可能性がある。実際に、時刻ｔ＝５において、ＤＴＷ距離が「６」になっている。そして、その時刻ｔ＝５において、「６」以外の各要素の値（下から、「５２」，「１７」，「１１」）がいずれも「６」よりも大きいので、その後、ＤＴＷ距離が「６」よりも小さくなる可能性はない。
【００４９】
しかし、ＤＴＷ距離が「６」になるのは部分シーケンスＸ［２：５］なので、今度はＴＷＭ４とＴＷＭ５も関係してくる。そこで、ＴＷＭ４を見ると、時刻ｔ＝５およびｔ＝６に「６」以下の要素、すなわち、それぞれｆ４（２，２）＝１およびｆ４（３，２）＝２の値が存在するが、時刻ｔ＝７には、「６」以下の値が存在しない。また、ＴＷＭ５においては、時刻ｔ＝５のときすでに、「６」以下の要素は存在しない。
【００５０】
したがって、時刻ｔ＝７の時点で、ＤＴＷ距離「６」を与えるＴＷＭ２の時刻ｔ＝５における部分シーケンスＸ［２：５］が最適なシーケンスであることがわかる。
また、ＴＷＭにおいて、このＤＴＷ距離「６」を算出するためにたどってきたルート「ｆ２（１，１）→ｆ２（２，２）→ｆ２（３，３）→ｆ２（４，４）」がワーピングパスの一例である。
【００５１】
このように、比較例の第１の方法および第２の方法によれば、シーケンスＸの長さがｎのとき、ｎ個のタイムワーピング行列を使用する必要があり、計算にＯ（ｎｍ）の時間がかかってしまい、ｎの値が大きくなると計算時間が長くなりすぎて、実用的ではない。
そこで、以下、図１〜７を参照しながら、タイムワーピング行列が単一でよく、計算がＯ（ｍ）の時間で済み、計算の高速化と省メモリ化を実現することのできる本実施形態のデータストリーム監視装置について説明する。
【００５２】
図１は、本実施形態のデータストリーム監視装置の構成図である。データストリーム監視装置１は、コンピュータ装置であり、入力部２、通信部３、記憶部４、出力部５、メモリ６および処理部７を備えている。
【００５３】
入力部２は、データ入力を行うものであり、たとえば、キーボードやマウスである。データストリーム監視装置１の使用者は、入力部２を使って、問合せシーケンスを入力することができる。
通信部３は、外部装置（不図示）やセンサ（不図示）からインターネットやＬＡＮなどを介してデータを受信するものであり、たとえば通信インターフェースである。通信部３は、外部装置（不図示）などからデータストリームを受信する。
【００５４】
記憶部４は、データを記憶するものであり、たとえば、ハードディスクである。記憶部４は、問合せシーケンス４１とタイムワーピングデータ４２を記憶している。また、記憶部４は、図示を省略しているが、データストリーム監視方法が記述されたプログラムを記憶している。
問合せシーケンス４１は、入力部２から入力された問合せシーケンスである。
タイムワーピングデータ４２は、タイムワーピング行列などのタイムワーピングの演算に必要なデータである。
【００５５】
出力部５は、データを出力するものであり、たとえば、ディスプレイやスピーカである。出力部５は、所定の条件を充足する部分シーケンスなどの検出データを出力する。
メモリ６は、処理部７の作業領域であり、たとえば、ＲＡＭ（Random Access Memory）である。
【００５６】
処理部７は、各種演算処理を行うものであり、たとえば、CPU（Central Processing Unit）である。処理部７は、入力部２が受け付けた問合せシーケンスを記憶部４に問合せシーケンス４１として記憶したり、通信部３が受信したデータストリームに関して記憶部４のタイムワーピングデータ４２を使用して問合せシーケンス４１と類似性の高い部分シーケンスを検出したり、その部分シーケンスを出力部５から出力したりする。
【００５７】
次に、図２を参照しながら、本実施形態のデータストリーム監視装置による問合せ処理のイメージについて説明する。図２は、本実施形態のデータストリーム監視装置による問合せ処理のイメージを示した図である。
【００５８】
図２に示すように、データストリーム監視装置１による問合せ処理では、比較例の場合（図８参照）と異なり、単一のＴＷＭを使用して、シーケンスＸから、問合せシーケンスＹ’（問合せシーケンスＹを少し変形したもの。詳細は後記）と類似する部分シーケンスを検出することができる。
図２では、該当する部分シーケンスとして、Ｘ［ｔｓ：ｔｅ］（Ｘ１）がまず検出され、その後に、Ｘ２が検出されている。
【００５９】
なお、以下、長さｍのシーケンスＹ＝（ｙ１，ｙ２，・・・，ｙｍ）に対して、先頭にｙ０を付加し、Ｙ’＝（ｙ０，ｙ１，ｙ２，・・・，ｙｍ）とする。このとき、ｙ０は、（−∞：∞）の値をとることができ、また、シーケンスＸに関して時刻ｔのときに受信してこれからタイムワーピング行列の演算に使用するデータをｘｔとすると、ｙ０＝ｘｔである。
そして、そのＹ’と、長さｎのシーケンスＸ＝（ｘ１，ｘ２，・・・，ｘｎ）の間でシーケンスマッチングを行うことになり、そのシーケンスマッチングは次の式（１０）〜（１４）により実現することができる。なお、ｔ＝（１，２，・・・，ｎ）、ｉ＝（１，２，・・・，ｍ）とする。また、式（６）〜（９）と重複する事項に関しては、説明を適宜省略する。
【００６０】
Ｄ（Ｘ［ｔｓ：ｔｅ］，Ｙ）＝ｄ（ｔｅ，ｍ）＝ｍｉｎ（ｄ（ｔ，ｍ））・・・（１０）
ｄ（ｔ，ｉ）＝||ｘｔ−ｙｉ||＋ｄｂｅｓｔ・・・（１１）
ｄｂｅｓｔ＝ｍｉｎ｛ｄ（ｔ，ｉ−１），ｄ（ｔ−１，ｉ），ｄ（ｔ−１，ｉ−１）｝・・・（１２）
ｄ（ｔ，０）＝ｄ（０，０）＝０・・・（１３）
ｄ（０，ｉ）＝∞・・・（１４）
【００６１】
上記の式（１０）〜（１４）のうち、式（１３）が本実施形態のポイントの１つである。この式（１３）によって、シーケンスＹをシーケンスＹ’に変更したことと同じ効果が得られる。
すなわち、データストリーム監視装置１の処理部７は、ある時刻にデータストリーム中の１つのデータを受信した場合、問合せシーケンスYの先頭にその１つのデータと同じデータを付加してシーケンスY’としてから、そのシーケンスY’に関してタイムワーピング行列を使ってダイナミックタイムワーピング距離を算出し、そのダイナミックタイムワーピング距離が閾値以下のときに、そのダイナミックタイムワーピング距離に対応する部分シーケンスを類似する部分シーケンスとして検出することができるが、式（１３）によって、シーケンスＹをシーケンスＹ’に変更したことと同じ効果が得られるのである。
【００６２】
また、本実施形態のタイムワーピング行列の各要素は、距離ｄ（ｔ，ｉ）だけでなく、次の式（１５）で求める、各距離ｄ（ｔ，ｉ）の開始時刻に関する情報ｓ（ｔ，ｉ）（開始時刻がｔ＝１なら「１」、開始時刻がｔ＝３なら「３」）も保持する。
【００６３】
＜ｉ≧２の場合＞
ｓ（ｔ，ｉ）＝ｓ（ｔ，ｉ−１）      （ｄｂｅｓｔ＝ｄ（ｔ，ｉ−１）のとき）
ｓ（ｔ−１，ｉ）      （ｄｂｅｓｔ＝ｄ（ｔ−１，ｉ）のとき）
ｓ（ｔ−１，ｉ−１）  （ｄｂｅｓｔ＝ｄ（ｔ−１，ｉ−１）のとき）
＜ｉ＝１の場合＞
ｓ（ｔ，ｉ）＝ｓ（ｔ，１）＝ｔ                                ・・・（１５）
【００６４】
また、Ｄ（Ｘ［ｔｓ：ｔｅ］，Ｙ）の開始時刻ｔｓは、次の式（１６）により得られる。
ｔｓ＝ｓ（ｔｅ，ｍ）・・・（１６）
最適なワーピングパスはこのタイムワーピング行列による距離計算から求めることができ、検出された類似する部分シーケンスの開始時刻は、そのワーピングパス上で引き継がれていくことで、特定することができる。
【００６５】
次に、図３を参照しながら、本実施形態のタイムワーピング行列の具体例について説明する。図３は、本実施形態のタイムワーピング行列の具体例を示した図である。なお、図１に示したハードウェアであるデータストリーム監視装置１の動作に関する説明は、図４および図５とともに後記する。
【００６６】
図３に示すように、タイムワーピング行列ＴＷＭは、図９の場合と同様、時間経過とともに伸張するシーケンスＸにおいて、シーケンスＹ＝（１１，６，９，４）と高い類似性を有する部分シーケンスを検出することを目的とし、ここでは、シーケンスＸ＝（５，１２，６，１０，６，５，１）である。なお、閾値ε＝２０とする。
【００６７】
具体的な計算について説明すると、上記式（１０）〜（１４）から、ｄ（１，１）＝（５−１１）２＋ｍｉｎ｛ｄ（１，０）＝０，ｄ（０，１）＝∞，ｄ（０，０）＝０｝＝３６＋０＝３６である。また、このとき、式（１５）から、開始時刻はｓ（１，１）＝１であり、図３のＴＷＭにおいては、「３６」の下に「（１）」と記載している。
【００６８】
また、ｄ（２，１）＝（１２−１１）２＋ｍｉｎ｛ｄ（２，０）＝０，ｄ（１，１）＝３６，ｄ（１，０）＝０｝＝１＋０＝１である。また、このとき、開始時刻はｓ（２，１）＝２である。
比較例のＴＷＭ１（図９（１）参照）の場合と異なり、このＴＷＭではｄ（２，１）＝１となっているのが、本実施形態のポイントの１つである（図９のＴＷＭ１における該当箇所は「３７」）。詳細は後記するが、このように、図３のＴＷＭの最下行の各要素がそのすぐ左の要素の値と関係なく独立に算出されている、すなわち、前記したシーケンスＹ＝（ｙ１，ｙ２，・・・，ｙｍ）に対し先頭にｙ０を付加してＹ’＝（ｙ０，ｙ１，ｙ２，・・・，ｙｍ）としたことと同様の効果を式（１３）によって実現したことにより、タイムワーピング行列が単一で済むのである。
【００６９】
同様にして、式（１０）〜（１５）を使用することで、ＴＷＭの各要素の値と各開始時刻の値を算出することができる。
以下、第１の方法と同様、閾値ε以下のＤＴＷ距離が求まったときにそれを類似する部分シーケンスとして検出する方法を第３の方法という。また、第２の方法と同様、最初に類似する部分シーケンスを検出した後、時間帯が少しでもその類似する部分シーケンスと重複するそれ以降の部分シーケンスの中で、より類似性の高いものがないことが確定してから、それを最適な部分シーケンスと判断する方法を第４の方法という。
【００７０】
第３の方法では、時刻ｔ＝３のとき、ＤＴＷ距離が「１４」であることにより、類似する部分シーケンスとしてＸ［２：３］を検出する。なお、開始時刻ｔ＝２はｄ（３，４）＝１４の下の「（２）」からわかり、また、終了時刻ｔ＝３はそのときの時刻からわかる。
【００７１】
この検出結果は、比較例による検出結果（図９（２）参照）と同じである。つまり、本実施形態のデータストリーム監視装置１によれば、単一のタイムワーピング行列により、比較例の場合よりも少ない計算量および少ないメモリ使用量で、比較例と同等の検出結果を得ることができる。
【００７２】
また、第４の方法では、類似する部分シーケンスＸ［２：３］を検出した後、さらに、その類似する部分シーケンスと少しでも時間帯が重複するそれ以降の部分シーケンスの中で、より類似性の高いものがあるか否かを判断する。
まず、左から３列目のｄ（３，１）、ｄ（３，２）およびｄ（３，３）の値がいずれも「１４」より大きければ、開始時刻がｔ＝３以前でＤＴＷ距離が「１４」以下になるものが存在する可能性がなくなるので、部分シーケンスＸ［２：３］が最適な部分シーケンスと判断できる。
【００７３】
しかし、ここでは、ｄ（３，２）＝１、ｄ（３，３）＝１０なので、時刻ｔ＝３の時点で部分シーケンスＸ［２：３］が最適とは判断できない。
次に、時刻ｔ＝４に移り、その列の各要素の全てについて、「値が『１４』よりも大きい」あるいは「開始時刻がｔ＝４以降である」、という条件を満たすか否かを判断する。この条件を満たせば、部分シーケンスＸ［２：３］が最適であると判断できる。
ここでは、ｄ（４，３）＝２（開始時刻ｔ＝２）がこの条件を満たさないため、部分シーケンスＸ［２：３］が最適であると判断できない。
【００７４】
続いて、時刻ｔ＝５に移り、ＤＴＷ距離が「６」なので、最適な部分シーケンスの候補をＸ［２：５］に変更する。
次に、時刻ｔ＝６に移り、その列の各要素の全てについて、「値が『６』よりも大きい」あるいは「開始時刻がｔ＝６以降である」、という条件を満たすか否かを判断する。
ここでは、ｄ（６，２）＝２（開始時刻ｔ＝４）がこの条件を満たさないため、部分シーケンスＸ［２：５］が最適であると判断できない。
【００７５】
次に、時刻ｔ＝７に移り、その列の各要素の全てについて、「値が『６』よりも大きい」あるいは「開始時刻がｔ＝６以降である」、という条件を満たすか否かを判断する。
ここでは、その条件を満たすので、部分シーケンスＸ［２：５］が最適であると判断できる。
【００７６】
この検出結果は、比較例による検出結果（図９（２）参照）と同じである。つまり、本実施形態のデータストリーム監視装置１によれば、単一のタイムワーピング行列により、比較例の場合よりも少ない計算量および少ないメモリ使用量で、比較例と同等の検出結果を得ることができる。
【００７７】
（第３の方法）
次に、図４を参照しながら、第３の方法を実行する場合のデータストリーム監視装置の動作について説明する。図４は、第３の方法を実行する場合のデータストリーム監視装置の動作を示したフローチャートである。なお、ｄ（ｔ，ｉ）（式（１１）参照）をｄｉ、ｄ（ｔ−１，ｉ）をｄｉ’と表記する。また、ｓ（ｔ，ｉ）（式（１５）参照）をｓｉ、ｓ（ｔ−１，ｉ）をｓｉ’と表記する。
【００７８】
まず、利用者は、データストリーム監視装置１において、入力部２から問合せシーケンスを入力し、入力された問合せシーケンスは記憶部４に問合せシーケンス４１として記憶される。また、記憶部４には、単一のタイムワーピング行列（図３参照）や、所定の閾値εなどのタイムワーピングデータ４２が記憶されている。
そして、通信部３は、外部装置（不図示）からデータストリームの受信を開始する。なお、以下、処理部７は、通信部３や記憶部４から受け取ったデータをメモリ６に展開して処理するが、メモリ６に展開する旨の記載は省略する。
【００７９】
処理部７は、まず、時刻ｔ＝１として処理を開始し（ステップＳ４０１）、次に、そのときの時刻ｔ（ここでは「１」）において、ｘｔを受信する（ステップＳ４０２）。
続いて、処理部７は、式（１０）〜（１５）に基づいて、全てのｄｉとｓｉを計算し（ステップＳ４０３）、タイムワーピング行列を更新する。このとき、タイムワーピング行列における時刻「ｔ−２」以降のデータは、削除してもよい（ｔ≧３の場合）。
【００８０】
次に、処理部７は、ｄｍ、つまり、時刻ｔにおけるＤＴＷ距離が閾値ε以下であるか否かを判断する（ステップＳ４０４）。
時刻ｔにおけるＤＴＷ距離が閾値ε以下でなかった場合（ステップＳ４０４でＮｏ）、処理部７は、ステップＳ４０８に進む。
【００８１】
時刻ｔにおけるＤＴＷ距離が閾値ε以下であった場合（ステップＳ４０４でＹｅｓ）、処理部７は、そのＤＴＷ距離の開始時刻ｓｍを開始時刻の変数ｔｓに代入し、そのときの時刻ｔを終了時刻の変数ｔｅに代入する（ステップＳ４０５）。
続いて、処理部７は、ＤＴＷ距離ｄｍ、その開始時刻ｔｓ、および、その終了時刻ｔｅを出力部５に出力する（ステップＳ４０６）。
【００８２】
利用者は、出力部５から出力されたそれらのデータを見て、データストリーム中に、問合せシーケンスと類似する部分シーケンスがあったことを知ることができる。
次に、処理部７は、以降の処理のために、全てのｄｉの値を初期化する、つまり、ｄｉに∞（プログラムを作成する際はεなどと比較して充分大きな値を使用。以下同様）を代入する（ステップＳ４０７）。
続いて、処理部７は、次の時刻の処理に移るために、全てのｄｉとｓｉの値を、それぞれ、１つ前の時刻の値の変数であるｄｉ’とｓｉ’に代入し（ステップＳ４０８）、「ｔ＝ｔ＋１」として（ステップＳ４０９）、ステップＳ４０２に戻り、処理を繰り返す。
【００８３】
このようにして、本実施形態のデータストリーム監視装置１によれば、単一のタイムワーピング行列を使用することで、データストリームが長くなっても、計算量やメモリの使用量を一定に保つことができ、それでいて比較例と同様の結果を得ることができる。
つまり、本実施形態のデータストリーム監視装置１によれば、たとえば、図３の例において、時刻ｔ＝３の時点で、ＤＴＷ距離「１４」、その開始時刻「２」、および、その終了時刻「３」を出力部５から出力することができる。
【００８４】
（第４の方法）
次に、図５を参照しながら、第４の方法を実行する場合のデータストリーム監視装置の動作について説明する。図５は、第４の方法を実行する場合のデータストリーム監視装置の動作を示したフローチャートである。なお、図４の場合と重複する説明は、適宜省略する。また、図４の場合と同様、データストリーム監視装置１において、記憶部４には、問合せシーケンス４１と、単一のタイムワーピング行列（図３参照）や、所定の閾値εなどのタイムワーピングデータ４２が記憶されている。さらに、最適な部分シーケンスの候補を入力する変数としてｄｍｉｎを使用する。
そして、通信部３は、外部装置（不図示）からデータストリームの受信を開始する。
【００８５】
処理部７は、まず、時刻ｔ＝１として処理を開始し（ステップＳ５０１）、次に、そのときの時刻ｔ（ここでは「１」）において、ｘｔを受信する（ステップＳ５０２）。
続いて、処理部７は、式（１０）〜（１５）に基づいて、全てのｄｉとｓｉを計算し（ステップＳ５０３）、タイムワーピング行列を更新する。このとき、タイムワーピング行列における時刻「ｔ−２」以降のデータは、削除してもよい（ｔ≧３の場合）。
【００８６】
次に、処理部７は、ｄｍｉｎ、つまり、時刻ｔにおけるＤＴＷ距離が閾値ε以下であるか否かを判断する（ステップＳ５０４）。
時刻ｔにおけるＤＴＷ距離が閾値ε以下でなかった場合（ステップＳ５０４でＮｏ）、処理部７は、ステップＳ５１４で、「ｄｍｉｎ≦ε」かつ「ｄｍ＜ｄｍｉｎ」、を満たすか否かを判断するが、ステップＳ５１４では「ｄｍｉｎ≦ε」を満たさないので（Ｎｏ）、さらに、ステップＳ５１６に進む。
【００８７】
時刻ｔにおけるＤＴＷ距離ｄｍｉｎが閾値ε以下であった場合（ステップＳ５０４でＹｅｓ）、処理部７は、そのＤＴＷ距離ｄｍｉｎを与える部分シーケンスが最適か否か、つまり、その部分シーケンスよりも後のある時刻における全ての要素（「ｄｉ」と「ｓｉ」）について、「値ｄｉがｄｍｉｎよりも大きい」あるいは「開始時刻ｓｉがｔｅよりも後である」、という条件を満たすか否かを判断する（ステップＳ５０５）。この条件を満たせば、そのＤＴＷ距離ｄｍｉｎを与える部分シーケンスが最適であると判断できるからである。
【００８８】
すなわち、処理部７は、ＤＴＷ距離ｄｍｉｎが閾値ε以下の部分シーケンスを検出した場合、その後、さらに、タイムワーピング行列の各行列要素の値の算出を行い、その部分シーケンスと時間帯が一部でも重複する部分シーケンスの中で、ＤＴＷ距離がより小さくなるものが存在しえないと判断したときに、その部分シーケンスを最適な（より適切な）部分シーケンスとして検出することができる。
【００８９】
ステップＳ５０５の条件を満たさない場合（Ｎｏ）、処理部７は、ステップＳ５１４で、「ｄｍｉｎ≦ε」かつ「ｄｍ＜ｄｍｉｎ」、を満たすか否かを判断する。
ここで、さらなる最適な部分シーケンスの候補があればステップＳ５１４の条件を満たし（Ｙｅｓ）、処理部７は、ＤＴＷ距離ｄｍを変数ｄｍｉｎに、その開始時刻ｓｍを変数ｔｓに、その終了時刻ｔを変数ｔｅに、それぞれ代入する（ステップＳ５１５）。
【００９０】
ステップＳ５０５の条件を満たす場合（Ｙｅｓ）、そのＤＴＷ距離ｄｍｉｎを与える部分シーケンスが最適であると判断できるので、処理部７は、そのＤＴＷ距離の開始時刻ｓｍを開始時刻の変数ｔｓに代入し、そのときの時刻ｔを終了時刻の変数ｔｅに代入してから、そのＤＴＷ距離ｄｍｉｎ、その開始時刻ｔｓ、および、その終了時刻ｔｅを出力部５に出力する（ステップＳ５０６）。
利用者は、出力部５から出力されたそれらのデータを見て、データストリーム中に存在する、問合せシーケンスと類似する部分シーケンスのうち、最適な部分シーケンスを知ることができる。
【００９１】
次に、処理部７は、以降の処理のために、ｄｍｉｎに∞を代入し（ステップＳ５０７）、ｉに「０」を代入し（ステップＳ５０８）、さらに、ステップＳ５０９〜Ｓ５１３の処理を行う。
ステップＳ５０９〜Ｓ５１３の処理では、処理部７は、「１」から「ｍ」までの「ｉ」の値に関して（ステップＳ５１０とステップＳ５１３参照）、「ｓｉ≦ｔｅ」を満たせば（ステップＳ５１１でＹｅｓ）、「ｄｉ」に「∞」を代入する（ステップＳ５１２）。ここでは、ステップＳ５０６で出力した最適な部分シーケンスと少しでも時間帯が重複する部分シーケンスがこれ以降にステップＳ５０６で出力されてしまう可能性をなくすために、その時刻における各要素のうちステップＳ５０６で出力した最適な部分シーケンスの終了時刻ｔｅ以前のものの値を無限大にしている。
【００９２】
続いて、処理部７は、次の時刻の処理に移るために、全てのｄｉとｓｉの値を、それぞれ、１つ前の時刻の値の変数であるｄｉ’とｓｉ’に代入し（ステップＳ５１６）、「ｔ＝ｔ＋１」として（ステップＳ５１７）、ステップＳ５０２に戻り、処理を繰り返す。
【００９３】
このようにして、本実施形態のデータストリーム監視装置１によれば、使用するタイムワーピング行列が単一であっても、最適な部分シーケンスを出力することができる。
つまり、本実施形態のデータストリーム監視装置１によれば、たとえば、図３の例において、時刻ｔ＝３の時点のＤＴＷ距離「１４」ではなく、時刻ｔ＝５の時点のＤＴＷ距離「６」（および、その開始時刻と終了時刻）を、最適な部分シーケンスのＤＴＷ距離として、出力部５から出力することができる。
この第４の方法によれば、そのアルゴリズムの特性上、比較例による方法と同様、最適な部分シーケンスを必ず検出することができる。
【００９４】
また、この第３の方法および第４の方法は、図４および図５のフローチャートを実行するプログラムを作成することで、データストリーム監視装置１などのコンピュータ装置において実現することができる。さらに、それらのプログラムは、ハードディスク、フラッシュメモリ、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、ＤＶＤ（Digital Versatile Disk）などの記録媒体に保存することが可能である。
【００９５】
（第１実施例）
次に、図６を参照しながら、本実施形態のデータストリーム監視装置に関する第１実施例について説明する。図６は、本実施形態のデータストリーム監視装置に関する第１実施例を説明するための図であり、（ａ）は問合せシーケンス、（ｂ）は部分シーケンス検出の様子を、それぞれ表している。
【００９６】
第１実施例は、本実施形態のデータストリーム監視装置１を、１ＧＢのメモリ、Ｉｎｔｅｌ（登録商標）のＸｅｏｎ２．８ＧＨｚのＣＰＵを搭載したＬｉｎｕｘ（登録商標）のマシンで実施したものである。ここでは、温度センサによって気温を計測した場合に関して、実験を行っている。
図６（ａ）は、問合せシーケンスの波形であり、縦軸が温度（摂氏）を表し、横軸が時間の経過を表している。この問合せシーケンスは、天候の変化によって、気温が約２０度から約３１度まで大きく変動しているパターンが２回存在していることを特徴としている。
【００９７】
図６（ｂ）は、データストリームの波形であり、（ａ）と同じく、縦軸が温度（摂氏）を表し、横軸が時間の経過を表している。このデータストリームは、温度センサによる約１分ごとの計測データを、上記マシンで受信したものである。
本実施形態の第４の方法を上記マシンで実行することで、図６（ｂ）に示すように、データストリームにおいて、（ａ）の問合せシーケンスと類似している部分シーケンス（Ｓｕｂｓｅｑ）としてＳｕｂ１とＳｕｂ２の２つを、逃さずに検出している。
【００９８】
（第２実施例）
続いて、図７を参照しながら、本実施形態のデータストリーム監視装置に関する第２実施例について説明する。図７は、本実施形態のデータストリーム監視装置に関する第２実施例について、データストリームのシーケンスの長さと計算時間との関係を表した図である。
【００９９】
第２実施例において、問合せシーケンスは人工データであり、長さは「２５６」である。データストリームは人工データであり、長さ（シーケンス長）を「１０の３乗」から「１０の６乗」まで可変とした。
図７において、縦軸は計算時間（ｍｓ）、横軸はデータストリームの長さ（シーケンス長）である。比較例による方法、および、本実施例による方法ともに、タイムワーピング行列の更新と類似する部分シーケンスの検出の合計時間を平均し、計算時間とした。
【０１００】
図７に示すように、比較例による方法（Ｌ２）では、データストリームが長くなるにつれ、計算時間が増加している。一方、本実施例による方法（Ｌ１）では、データストリームが長くなっても、計算時間は一定に保たれている。これは、データストリームが長くなるにつれて、比較例による方法ではタイムワーピング行列の数が増えるのに対し、本実施例による方法ではタイムワーピング行列が常に単一であるからである。
【０１０１】
このように、第１実施例および第２実施例からもわかるように、本実施形態のデータストリーム監視装置１によれば、比較例の場合と比べて、計算コストの低減、つまり、計算の高速化と省メモリ化を実現できる。
【０１０２】
以上で実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。
たとえば、本実施形態では、問合せシーケンスおよびデータストリームに関して、一次元データの場合について説明したが、ｎ次元データ（ｎは２以上の自然数）の場合でも同様に適用することができる。
また、本発明は、温度センサ以外に、映像や音楽の配信、バイオインフォマティックス、各種ロボットなど、多くの分野に適用可能である。
その他、具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図面の簡単な説明】
【０１０３】
【図１】本実施形態のデータストリーム監視装置の構成図である。
【図２】本実施形態のデータストリーム監視装置による問合せ処理のイメージを示した図である。
【図３】本実施形態のタイムワーピング行列の具体例を示した図である。
【図４】第３の方法を実行する場合のデータストリーム監視装置の動作を示したフローチャートである。
【図５】第４の方法を実行する場合のデータストリーム監視装置の動作を示したフローチャートである。
【図６】本実施形態のデータストリーム監視装置に関する第１実施例を説明するための図であり、（ａ）は問合せシーケンス、（ｂ）は部分シーケンス検出の様子を、それぞれ表している。
【図７】本実施形態のデータストリーム監視装置に関する第２実施例について、シーケンスの長さと計算時間との関係図である。
【図８】ＤＴＷを使用したデータストリーム監視の比較例における、問合せ処理のイメージを示した図である。
【図９】比較例におけるタイムワーピング行列の例を示した図である。
【符号の説明】
【０１０４】
１      データストリーム監視装置
４      記憶部
５      出力部
７      処理部
ＴＷＭ  タイムワーピング行列
【図１】
2008134706.tif 000003
【図２】
2008134706.tif 000004
【図３】
2008134706.tif 000005
【図４】
2008134706.tif 000006
【図５】
2008134706.tif 000007
【図６】
2008134706.tif 000008
【図７】
2008134706.tif 000009
【図８】
2008134706.tif 000010
【図９】
2008134706.tif 000011