(57)【特許請求の範囲】
【請求項１】
逐次流入してくる複数系列の時系列データを受信する受信部と、
前記受信部が受信した前記時系列データを記憶する第１メモリと、
前記第１メモリから時系列データを読み出し、所定時間の部分時系列データに分割する区間分割部と、
前記区間分割部が分割した前記部分時系列データについて互いの類似度を求める類似判定部と、
前記類似判定部が求めた前記類似度に基づき、前記区間分割部で生成された部分時系列データの類似検索索引を作成する索引部と、
前記索引部で作成された前記類似検索索引を受信時刻毎にキュー構造で記憶する第２メモリと、
前記区間分割部で生成された前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて前記第２メモリから読み出す類似ペア検索部と、
を備えるデータ検索装置。
【請求項２】
逐次流入してくる複数系列の時系列データを受信する受信部と、
前記受信部が受信した前記時系列データを記憶する第１メモリと、
前記第１メモリから時系列データを読み出し、所定時間の部分時系列データに分割する区間分割部と、
前記区間分割部が分割した前記部分時系列データについて互いの類似度を求める類似判定部と、
前記部分時系列データを受信時刻で区別可能な構造を有し、前記類似判定部が求めた前記類似度に基づく、前記区間分割部で生成された部分時系列データの類似検索索引を作成する索引部と、
前記索引部で作成された前記類似検索索引を記憶するとともに、前記類似検索索引の構造を維持したまま後続の前記部分時系列データを前記類似検索索引にキューとして追記する第２メモリと、
前記区間分割部で生成された前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて前記第２メモリから読み出す類似ペア検索部と、
を備えるデータ検索装置。
【請求項３】
逐次入力される複数系列の時系列データを所定時間の部分時系列データに分割し、前記部分時系列データについて互いの類似度を求め、前記類似度に基づく類似検索索引を作成して受信時刻毎にキュー構造で記憶しておき、
検索時に前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて読み出すデータ検索方法。
【請求項４】
逐次入力される複数系列の時系列データを所定時間の部分時系列データに分割し、前記部分時系列データについて互いの類似度を求め、前記部分時系列データを受信時刻で区別可能な構造を有し、前記類似度に基づく１つの類似検索索引を作成して記憶しておき、
前記類似検索索引の構造を維持したまま後続の前記部分時系列データを前記類似検索索引にキューとして追記し、
検索時に前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて読み出すデータ検索方法。
【請求項５】
請求項３又は４に記載のデータ検索方法をコンピュータに実行させるデータ検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、類似した部分時系列データのペアを検索するデータ検索装置、データ検索方法、及びデータ検索プログラムに関する。
【背景技術】
【０００２】
時系列データは、時間的に連続して観測されたデータ系列である。時系列データは環境観測や設備監視、株価、統計情報、メディア処理などで利用されている。
【０００３】
時系列データの検索には、事前に蓄積されたデータに対して検索するものと、逐次流入してくるデータに対して検索するものとがある。前者の例としては、過去に定時観測した降水量のデータで類似したパターンを探す処理などがある。後者の例としては、リアルタイムに株価の変動を観測して目的のパターンと一致した瞬間に通知する処理などがある。本発明は後者のリアルタイムな処理を扱う。
【０００４】
リアルタイムな時系列データ検索の先行技術としては、以下のものが挙げられる。複数系列の同一時刻の時系列データのうち、類似した時系列データのペアを求める検索処理があった（例えば、特許文献１や非特許文献１参照）。特許文献１では閾値よりも類似度の高いペアを、非特許文献１では相関係数が閾値以上のものを探す課題を扱っている。これらの先行技術では、系列数が多いほど類似判定の計算コストが大きくなるため、類似度計算の削減のための次元圧縮や類似度計算回数削減のための索引技術を技術課題としていた。しかしながら、これらの先行技術は時系列データの終点が現在時刻のもののみを扱うという制限をもつ。つまり、時間的なずれのある類似した部分時系列データを対象とした検索には適用できない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−２４４３８９号公報
【非特許文献】
【０００６】
【非特許文献１】Ａｂｄｕｌｌａｈ  Ｍｕｅｅｎ，  Ｓｕｍａｎ  Ｎａｔｈ  ａｎｄ  Ｊｉｅ  Ｌｉｕ，“Ｆａｓｔ  Ａｐｐｒｏｘｉｍａｔｅ  Ｃｏｒｒｅｌａｔｉｏｎ  ｆｏｒ  Ｍａｓｓｉｖｅ  Ｔｉｍｅ−ｓｅｒｉｅｓ  Ｄａｔａ”，  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０１０  ＡＣＭ  ＳＩＧＭＯＤ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  ｄａｔａ，  ２０１０．
【非特許文献２】Ｙｉａｎｉｌｏｓ，  Ｐｅｔｅｒ  Ｎ，“Ｄａｔａ  ｓｔｒｕｃｔｕｒｅｓ  ａｎｄ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｎｅａｒｅｓｔ  ｎｅｉｇｈｂｏｒ  ｓｅａｒｃｈ  ｉｎ  ｇｅｎｅｒａｌ  ｍｅｔｒｉｃ  ｓｐａｃｅｓ”，  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｆｏｕｒｔｈ  ａｎｎｕａｌ  ＡＣＭ−ＳＩＡＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｄｉｓｃｒｅｔｅ  ａｌｇｏｒｉｔｈｍｓ．  Ｓｏｃｉｅｔｙ  ｆｏｒ  Ｉｎｄｕｓｔｒｉａｌ  ａｎｄ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ  Ｐｈｉｌａｄｅｌｐｈｉａ，  ｐｐ．３１１−３２１，  １９９３．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述のように、従来技術は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、類似した部分時系列データのペアを求める検索処理を扱うことができない、つまり、時間的なずれのある類似した部分時系列データを複数系列の時系列データの中から検索することができない。このような検索例としては、１ヶ月間の複数銘柄の株価の時系列データから類似した部分時系列データを検索して、時間的なずれのある特徴的な株価の変動を見つけ出す処理がある。また、複数のセンサ値の時系列データから類似した部分時系列データを検索して、日射から地熱、気温といった時間的なずれの生じる現象を見つけ出す処理も検索例として挙げられる。上述のとおり、複数系列の時系列データを対象とした先行技術や、時間的なずれのある類似した部分時系列データを対象とした先行技術はあるが、この２つを同時に満たす時系列データ検索処理技術は発明されていない。
【０００８】
上記２つを同時に満たす時系列データ検索処理では、現在から過去の一定期間内に流入した複数系列の時系列データの中から、閾値よりも類似した部分時系列データのペアを求める検索処理を扱うことになる。この検索処理は、距離計算コストを抑えることが求められており、類似度計算回数削減が解決すべき技術課題となっている。
【０００９】
つまり、時系列データの系列数が大きい、検索対象とする時系列データの時間が長い、もしくは時系列データの長さに対して部分時系列データが短いほど、類似度計算回数は大きくなる。類似度計算回数を削減するため、類似度の高い時系列データのペアに絞り込む検索索引が必要である。従来技術の検索索引は時系列データの終点が現在時刻のものを検索対象としていたが、上記２つを同時に満たす時系列データ検索処理では受信時刻の異なる部分時系列データも検索対象となり、類似判定の計算コストが大きくなるという課題がある。
【００１０】
本発明は、上記課題を解消するためになされたものであり、その目的は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、類似した部分時系列データのペアを検索するに際し、必要とする距離計算コストを抑えることができるデータ検索装置、データ検索方法、及びデータ検索プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明は、新しい受信時刻の部分時系列データの挿入と古い受信時刻の部分時系列データの削除が容易なデータ構造で、かつ、部分時系列データを受信時刻ごとに区別して枝刈るアルゴリズム採用することとした。ここで、「枝刈り」とは、検索対象とならないデータを予め除去しておくという意味である。
【００１２】
本発明に係る一のデータ検索装置は、逐次流入してくる複数系列の時系列データを受信する受信部と、
前記受信部が受信した前記時系列データを記憶する第１メモリと、
前記第１メモリから時系列データを読み出し、所定時間の部分時系列データに分割する区間分割部と、
前記区間分割部が分割した前記部分時系列データについて互いの類似度を求める類似判定部と、
前記類似判定部が求めた前記類似度に基づき、前記区間分割部で生成された部分時系列データの類似検索索引を作成する索引部と、
前記索引部で作成された前記類似検索索引を受信時刻毎にキュー構造で記憶する第２メモリと、
前記区間分割部で生成された前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて前記第２メモリから読み出す類似ペア検索部と、
を備える。
【００１３】
本発明に係る一のデータ検索方法は、逐次入力される複数系列の時系列データを所定時間の部分時系列データに分割し、前記部分時系列データについて互いの類似度を求め、前記類似度に基づく類似検索索引を作成して受信時刻毎にキュー構造で記憶しておき、検索時に前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて読み出す。
【００１４】
本発明は、類似検索索引を受信時刻別につくることで、指定された時間範囲外の受信時刻の部分時系列データの索引からの削除と新しい部分時系列データの索引への追加の高速化、および、部分時系列データを受信時刻ごとに区別した枝刈りができるようになる。このため、本発明は、時系列データの系列数が大きいときに、部分時系列データの更新の高速化と類似度計算回数の削減を実現することができる。
【００１５】
従って、本発明は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、類似した部分時系列データのペアを検索するに際し、必要とする距離計算コストを抑えることができるデータ検索装置及びデータ検索方法を提供することができる。
【００１６】
本発明に係る他のデータ検索装置は、逐次流入してくる複数系列の時系列データを受信する受信部と、
前記受信部が受信した前記時系列データを記憶する第１メモリと、
前記第１メモリから時系列データを読み出し、所定時間の部分時系列データに分割する区間分割部と、
前記区間分割部が分割した前記部分時系列データについて互いの類似度を求める類似判定部と、
前記部分時系列データを受信時刻で区別可能な構造を有し、前記類似判定部が求めた前記類似度に基づく、前記区間分割部で生成された部分時系列データの類似検索索引を作成する索引部と、
前記索引部で作成された前記類似検索索引を記憶するとともに、前記類似検索索引の構造を維持したまま後続の前記部分時系列データを前記類似検索索引にキューとして追記する第２メモリと、
前記区間分割部で生成された前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて前記第２メモリから読み出す類似ペア検索部と、
を備える。
【００１７】
本発明に係る他のデータ検索方法は、逐次入力される複数系列の時系列データを所定時間の部分時系列データに分割し、前記部分時系列データについて互いの類似度を求め、前記部分時系列データを受信時刻で区別可能な構造を有し、前記類似度に基づく１つの類似検索索引を作成して記憶しておき、前記類似検索索引の構造を維持したまま後続の前記部分時系列データを前記類似検索索引にキューとして追記し、検索時に前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて読み出す。
【００１８】
本発明は、類似検索索引を各時系列データを受信時刻で区別可能な構造にしたうえで１つに集約することで、指定された時間範囲内の受信時刻つくられた複数の類似検索索引を検索のたびに探索する手間を削減できるようになる。このため、本発明は、検索対象とする時系列データの時間が長い、もしくは時系列データの長さに対して部分時系列データが短いときに、類似度計算回数の削減を実現することができる。
【００１９】
従って、本発明は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、類似した部分時系列データのペアを検索するに際し、必要とする距離計算コストを抑えることができるデータ検索装置及びデータ検索方法を提供することができる。
【００２０】
本発明に係るデータ検索プログラムは、前記データ検索方法をコンピュータに実行させる。
【発明の効果】
【００２１】
本発明は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、類似した部分時系列データのペアを検索するに際し、必要とする距離計算コストを抑えることができるデータ検索装置及びデータ検索方法を提供することができる。
【図面の簡単な説明】
【００２２】
【図１】類似部分時系列ペアを説明するイメージの図である。
【図２】本発明に係るデータ検索装置を説明する図である。
【図３】本発明に係るデータ検索方法を説明する図である。
【図４】本発明に係るデータ検索装置が時系列データを部分時系列データに分割するときのイメージの図である。
【図５】本発明に係るデータ検索方法における類似検索索引のキューを説明する図である。
【図６】本発明に係るデータ検索方法における類似検索索引構造を説明する図である。
【図７】本発明に係るデータ検索方法における類似検索索引を使った枝刈りのイメージの図である。
【図８】本発明に係るデータ検索装置を説明する図である。
【図９】本発明に係るデータ検索方法を説明する図である。
【図１０】本発明に係るデータ検索方法における類似検索索引のキューを説明する図である。
【発明を実施するための形態】
【００２３】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２４】
図１は、類似部分時系列ペアのイメージの図である。実施形態１および実施形態２の装置では閾値よりも類似した部分時系列データペアを検索する。
【００２５】
（実施形態１）
図２は、本実施形態のデータ検索装置３０１を説明する図である。データ検索装置３０１は、逐次流入してくる複数系列の時系列データを受信する受信部１１と、
受信部１１が受信した前記時系列データを記憶する第１メモリ１２と、
第１メモリ１２から時系列データを読み出し、所定時間の部分時系列データに分割する区間分割部１３と、
区間分割部１３が分割した前記部分時系列データについて互いの類似度を求める類似判定部１４と、
類似判定部１４が求めた前記類似度に基づき、区間分割部１３で生成された部分時系列データの類似検索索引を作成する索引部１５と、
索引部１５で作成された前記類似検索索引を受信時刻毎にキュー構造で記憶する第２メモリ１６と、
区間分割部１３で生成された前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて第２メモリ１６から読み出す類似ペア検索部１７と、
を備える。
【００２６】
図３は、データ検索装置３０１が行うデータ検索方法を説明する図である。本データ検索方法は、逐次入力される複数系列の時系列データを所定時間の部分時系列データに分割し（ステップＳ１０１、Ｓ１０２）、前記部分時系列データについて互いの類似度を求め、前記類似度に基づく類似検索索引を作成して受信時刻毎にキュー構造で記憶しておき（ステップＳ１０３）、検索時に前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて読み出す（ステップＳ１０４）。
【００２７】
ステップＳ１０１において、受信部１１は、逐次流入してくる複数系列の時系列データを受信して第１メモリ１２に記憶させる。第１メモリ１２の容量に制限がある場合は、指定された時間範囲外の受信時刻の時系列データを第１メモリ１２から削除する。第１メモリ１２の最低限必要な記憶容量は、検索対象とする部分時系列データ長をｍ、検索対象とする時間長をｗ、系列数をｎとすると、ｎ（ｍ＋ｗ−１）の要素数を蓄積できる容量となる。
【００２８】
ステップＳ１０２において、区間分割部１３は、第１メモリ１２から時系列データを読みだして、指定された区間時間の部分時系列データに分割する。本実施形態における部分時系列データとは、逐次流入してくる時間的に連続したデータ系列のうち、指定された区間時間の連続したデータ系列をいう。区間分割部１３は新しい時系列データを受信するたびに、各時系列データの直近の長さｍの部分時系列データを分割して、索引部１５と類似ペア検索部１７に部分時系列データを入力する。また、類似ペア検索部１７から指定された時間の長さｍの部分時系列データを分割して返す。図４は、区間分割部１３が時系列データを部分時系列データに分割するときのイメージの図である。図中の
【数１】
0005632862.tif 000002
は受信時刻ｔｘにおける系列のＩＤがｉの部分時系列データを表している。
【００２９】
ステップＳ１０３において、類似判定部１４は部分時系列データ間の類似度を計算する。本実施形態における類似度とは、２つの部分時系列データがどの程度類似しているかを数値で表す指標である。特に、本実施形態においては、２つの部分時系列データ
【数２】
0005632862.tif 000003
の類似度Ｄｉｓｔにユークリッド距離を採用し、以下の通り定義する。
【数３】
0005632862.tif 000004
【００３０】
なお、本発明のいう類似度は、上記特徴を満たす様々な距離がその対象となるものであって、ユークリッド距離に限られない。具体的に一例を挙げると、Ｄｙｎａｍｉｃ  ｔｉｍｅ  ｗａｒｐｉｎｇやＥａｒｔｈ  Ｍｏｖｅｒ’ｓ  Ｄｉｓｔａｎｃｅ、編集距離、ハミング距離、Ｊａｃｃａｒｄ係数距離、コサイン類似度、マンハッタン距離、マハラノビス距離などを含む時系列データ間の類似度を表す距離であってよい。さらに、これらの距離に加えて、部分時系列のオフセットや振幅を調整したものに対する距離であってもよい。
【００３１】
ステップＳ１０３において、索引部１５は第２メモリ１６に指定された時間範囲内の受信時刻に生成された複数の類似検索索引をキュー構造で管理する。本実施形態における類似検索索引とは、クエリとして与えた部分時系列データと蓄積した部分時系列データ間の類似度すべてを判別することなく、クエリとの類似度が閾値以内の蓄積した部分時系列データを探すためのデータ構造である。索引部１５は、区間分割部１３で分割した最新の受信時刻の部分時系列データを基準とした類似検索索引を１つ新たにつくり、第２メモリ１６の索引を蓄積するキューに追加する。同時に、指定された時間範囲外の受信時刻の類似検索索引を第２メモリ１６の索引を蓄積するキューから削除する。図５は、類似検索索引のキューを説明する図である。
【００３２】
［類似検索索引の作成方法］
本実施形態における類似検索索引は、距離空間の類似検索索引Ｖａｎｔａｇｅ  Ｐｏｉｎｔ  Ｔｒｅｅ（ＶＰＴ）（非特許文献２参照）を採用し、以下の手順で作成する。この索引は、基準となる部分時系列データ（基準部分時系列データ）１つと分割距離１つを定めて、基準部分時系列データからの距離と分割距離に基づいて索引対象の複数の部分時系列データを２つに分類することを繰り返して作成する。ここで、受信時刻ｔの部分時系列データ集合Ｓｔを２分類する例を説明する。基準となる系列ｐの部分時系列データＳｐｔをＳｔから一つ選び、Ｓｔを均等２分割できる距離をｒｐｔとしたとき、Ｓｔは、
【数４】
0005632862.tif 000005
の２つの部分時系列データ集合ＳｉｎとＳｏｕｔに分類される。ＳｉｎとＳｏｕｔも同様にそれぞれで基準となる部分時系列データと分割距離を決めてさらに空間を２分類することを繰り返すことで、木構造の類似検索索引をつくる。この類似検索索引は、葉ノードと内部ノードという２種類のノードで構成される。葉ノードは木構造の末端のノードであり、内部ノードは末端以外に位置するノードをいう。分類のたびに必要となるＳｐｔとｒｐｔは、内部ノードを生成して管理する。十分に小さい数の部分時系列データ集合まで繰り返し分類して必要な数の内部ノードを生成した後は、葉ノードを生成してＳｔを管理する。つまり、内部ノードは分類に必要な情報（Ｓｐｔ、ｒｐｔ）を管理し、葉ノードでは部分時系列データ集合を管理する。図６は、本実施形態の類似検索索引構造を説明する図である。
【００３３】
なお、本発明のいう類似検索索引は上記特徴を満たす様々なデータ構造がその対象となるものであって、ＶＰＴに限られない。具体的な一例を挙げると、他の距離空間の類似検索索引Ｍ−ｔｒｅｅやＰＭ−ｔｒｅｅ、ＭＶＰ−ｔｒｅｅ、ｓａ−ｔｒｅｅ、ｉＤｉｓｔａｎｃｅ、Ｌｉｓｔ  ｏｆ  Ｃｌｕｓｔｅｒｓ、ＡＥＳＡ、ＬＡＥＳＡ、ＧＮＡＴ、Ｄ−ｉｎｄｅｘなどを含む。さらに、これらの距離空間の類似検索索引に加えて、多次元空間を対象とする類似検索索引のＲ−ｔｒｅｅやＰｒｉｏｒｉｔｙ  Ｒ−ｔｒｅｅ、文字列データの類似検索索引、集合データの類似検索索引であってもよい。さらに、本発明の範囲はこれに限るものでなく、これらの索引に次元圧縮技術を組み合わせることも可能である。具体的な一例を挙げると、ＤＦＴ、ＳＶＤ、ＰＡＡ、ＳＡＸなどを含む。部分時系列データが長くなり、次元数の増加によるデータ量の増大（『次元の呪い』）で枝刈りが不十分である場合は、これら次元圧縮技術を採用することで距離の上限値と下限値を索引付けに利用できる。
【００３４】
［類似データ検索方法］
ステップＳ１０４において、類似ペア検索部１７は、区間分割部１３で分割した最新の受信時刻の部分時系列データをクエリとして、第２メモリ１６にキュー構造で管理されている受信時刻ごとの類似検索索引を使って、閾値よりもクエリと類似した部分時系列データを検索する。そして、類似ペア検索部１７は、類似部分時系列データペアを出力する。ここでのデータペアとは、最新時刻の部分時系列データとこれに類似する部分時系列データのペアを意味する。類似ペア検索部１７は、以下の手順を行い、類似部分時系列データペアを出力する。
【００３５】
ここでは、上述のＳｔがＳｐｔとｒｐｔによってＳｉｎとＳｏｕｔの２つの部分時系列データ集合に分類されている構造を使った検索例を述べる。クエリとする時系列データ
【数５】
0005632862.tif 000006
からｒｑの距離の範囲にある時系列データを探したい場合を想定する。数５のクエリと空間分割の基準とした部分時系列データ
【数６】
0005632862.tif 000007
との間の距離
【数７】
0005632862.tif 000008
が、
１）
【数８】
0005632862.tif 000009
のとき、Ｓｉｎに含まれる部分時系列データを検索すれば十分で、Ｓｏｕｔに含まれる時系列データ、つまりＳｏｕｔを管理する内部ノードもしくは葉ノードは枝刈りできる。
２）
【数９】
0005632862.tif 000010
のとき、Ｓｏｕｔに含まれる時系列データを検索すれば十分で、Ｓｉｎに含まれる時系列データ、つまりＳｉｎを管理する内部ノードもしくは葉ノードは枝刈りできる。
３）  上記１），２）のどちらの不等式も満たさない場合、ＳｉｎとＳｏｕｔの両方の時系列データを検索する必要がある。
【００３６】
このような枝刈りを再帰的に実行する。つまり、図６の内部ノードをある程度たどって、枝刈りできない内部ノードや葉ノードにおいて検索を行う。図７は、類似検索索引を使った枝刈りのイメージの図である。上述の１）の条件に該当して、Ｓｏｕｔに含まれる時系列データを枝刈りできる様子を表している。
【００３７】
以上の手順で、データ検索装置３０１は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、閾値よりも類似した部分時系列データペアを検索する。
【００３８】
（実施形態２）
図８は、本実施形態のデータ検索装置３０２を説明する図である。データ検索装置３０２は、逐次流入してくる複数系列の時系列データを受信する受信部１１と、
受信部１１が受信した前記時系列データを記憶する第１メモリ１２と、
第１メモリ１２から時系列データを読み出し、所定時間の部分時系列データに分割する区間分割部１３と、
区間分割部１３が分割した前記部分時系列データについて互いの類似度を求める類似判定部１４と、
前記部分時系列データを受信時刻で区別可能な構造を有し、類似判定部１４が求めた前記類似度に基づく、区間分割部１３で生成された部分時系列データの類似検索索引を作成する索引部１５と、
索引部１５で作成された前記類似検索索引を記憶するとともに、前記類似検索索引の構造を維持したまま後続の前記部分時系列データを前記類似検索索引にキューとして追記する第２メモリ１６と、
区間分割部１３で生成された前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて第２メモリ１６から読み出す類似ペア検索部１７と、
を備える。
【００３９】
図９は、データ検索装置３０２が行うデータ検索方法を説明する図である。本データ検索方法は、逐次入力される複数系列の時系列データを所定時間の部分時系列データに分割し、前記部分時系列データについて互いの類似度を求め、前記部分時系列データを受信時刻で区別可能な構造を有し、前記類似度に基づく１つの類似検索索引を作成して記憶しておき（ステップＳ２０１、Ｓ２０２）、
前記類似検索索引の構造を維持したまま後続の前記部分時系列データを前記類似検索索引にキューとして追記し（ステップＳ２０３〜ステップＳ２０５）、
検索時に前記部分時系列データをクエリとして、指定された閾値よりも類似した部分時系列データを前記類似検索索引を用いて読み出す（ステップＳ２０６）。
【００４０】
データ検索装置３０２において、受信部１１、区間分割部１３、類似判定部１４、類似ペア検索部１７及び第１メモリ１２は図２のデータ検索装置３０１と同じ動作を行う。
【００４１】
索引部１５は、ステップＳ２０２で一度類似検索索引を構築し、その後は内部ノードを変更せずに葉ノードのみを更新する（ステップＳ２０３〜Ｓ２０５）。本実施形態における類似検索索引も実施形態１と同様、距離空間の類似検索索引ＶＰＴのデータ構造を採用する。
【００４２】
ステップ（Ｓ２０１〜Ｓ２０２）では、受信部１１にてｎ（ｍ＋ｗ−１）の要素数を蓄積した後に、１つの類似検索索引を構築する。区間分割部１３で切り出せる部分時系列データ集合を“Ｓ”とする。基準となる系列ＩＤがｐで受信時刻がｔｘの部分時系列データ
【数１０】
0005632862.tif 000011
を“Ｓ”から一つ選び、“Ｓ”を均等２分割できる距離を
【数１１】
0005632862.tif 000012
とおく。“Ｓ”は、
【数１２】
0005632862.tif 000013
の２つの部分時系列データ集合ＳｉｎとＳｏｕｔに分類される。
【００４３】
ＳｉｎとＳｏｕｔも同様にそれぞれで基準となる部分時系列データと分割距離を決めてさらに空間を２分類することを繰り返すことで、木構造の索引をつくる。十分に小さい数の部分時系列データ集合まで分類した後は、葉ノードとして“Ｓ”を管理する。このとき、葉ノードでは部分時系列データを受信時刻別にアクセスしやすいキュー構造で管理する。
【００４４】
このようにして、木構造の内部ノードでは
【数１３】
0005632862.tif 000014
を管理し、葉ノードでは部分時系列データ集合を管理する。図１０は、類似検索索引の葉ノードにおけるキューを説明する図である。
【００４５】
なお、本発明のいう類似検索索引は上記特徴を満たす様々なデータ構造がその対象となるものであって、ＶＰＴに限られず、実施形態１で示した類似検索索引であってもよい。さらに、これらの索引に実施形態１で示した次元圧縮技術を組み合わせることも可能である。
【００４６】
索引構築後、ステップＳ２０３〜Ｓ２０５でデータ検索装置３０２は、新しく追加する部分時系列Ｓｉｔを、該当する葉ノードに追加する。つまり、数１３を管理する内部ノードがあった場合は、
【数１４】
0005632862.tif 000015
ならばＳｉｎを担当するノードを、
【数１５】
0005632862.tif 000016
ならばＳｏｕｔを担当するノードを探索することを繰り返して、該当する葉ノードを探索する。そして、葉ノードが見つかったら、部分時系列データを蓄積するキューにＳｉｔを追加する。なお、所定時間が経過した部分時系列データは葉ノードにおけるキューから削除される。
【００４７】
ステップＳ２０６は図３で説明したステップＳ１０４と同様である。類似ペア検索部１７は、区間分割部１３で分割した最新の受信時刻の部分時系列データをクエリとして、第２メモリ１６に管理されている類似検索索引を使い、図６の内部ノードをある程度たどって、枝刈りできない内部ノードや葉ノードにおいて、閾値よりもクエリと類似した部分時系列データを検索する。そして、類似ペア検索部１７は、類似部分時系列データペアを出力する。
【００４８】
以上の手順で、データ検索装置３０２は、現在から過去の一定期間内に流入した複数系列の時系列データの中から、閾値よりも類似した部分時系列データペアを検索する。
【符号の説明】
【００４９】
１１：受信部
１２：第１メモリ
１３：区間分割部
１４：類似判定部
１５：索引部
１６：第２メモリ
１７：類似ペア判定部
１８：第３メモリ
３０１、３０２：データ検索装置
【図１】
0005632862.tif 000017
【図２】
0005632862.tif 000018
【図３】
0005632862.tif 000019
【図４】
0005632862.tif 000020
【図５】
0005632862.tif 000021
【図６】
0005632862.tif 000022
【図７】
0005632862.tif 000023
【図８】
0005632862.tif 000024
【図９】
0005632862.tif 000025
【図１０】
0005632862.tif 000026