(57)【要約】【課題】ダイナミックタイムワーピングを用いた時系列データの検索を高速化することのできる時系列データ検索方法、時系列データ検索装置、時系列データ検索プログラム、およびプログラム記録媒体を提供する。【解決手段】複数のシーケンスを格納して記憶するデータベースを備えたコンピュータシステムが、検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する近似ステップと、この近似ステップで近似した近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記データベースから読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出ステップとを実行する。【選択図】      図１
2004348594.tif 000002
【特許請求の範囲】
【請求項１】
時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索方法であって、
複数のシーケンスを格納して記憶するデータベースを備えたコンピュータシステムが、
（Ａ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する近似ステップと、
（Ｂ）前記（Ａ）の近似ステップで近似した近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記データベースから読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出ステップと
を実行することを特徴とする時系列データ検索方法。
【請求項２】
前記（Ａ）の近似ステップと、前記（Ｂ）の距離算出ステップを、前記データベースに記憶した全てのシーケンスに対して繰り返し実行し、
（Ｃ）この繰り返しの結果に基づいて、前記検索対象となるシーケンスの近傍に位置するシーケンスを検索結果として出力する検索結果出力ステップ
をさらに実行することを特徴とする請求項１記載の時系列データ検索方法。
【請求項３】
時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索方法であって、
複数のシーケンスを格納して記憶するデータベースを備えたコンピュータシステムが、
（Ａ）近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成ステップと、
（Ｂ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、前記（Ａ）の作成ステップで作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する近似ステップと、
（Ｃ）この近似ステップで求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記データベースから読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出ステップと
を実行することを特徴とする時系列データ検索方法。
【請求項４】
前記（Ａ）の作成ステップから前記（Ｃ）の距離算出ステップに至る処理を、前記データベースに記憶した全てのシーケンスに対して繰り返し実行し、
（Ｄ）この繰り返しの結果に基づいて、前記検索対象となるシーケンスの近傍に位置するシーケンスを検索結果として出力する検索結果出力ステップ
をさらに実行することを特徴とする請求項３記載の時系列データ検索方法。
【請求項５】
時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索方法であって、
複数のシーケンスを格納して記憶するデータベースを備えたコンピュータシステムが、
（Ａ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する第１の近似ステップと、
（Ｂ）前記（Ａ）の第１の近似ステップで近似した近似距離が所定の範囲内にある場合には、近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成ステップと、
（Ｃ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、前記（Ｂ）の作成ステップで作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する第２の近似ステップと、
（Ｄ）前記（Ｃ）の第２の近似ステップで求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記データベースから読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出ステップと
を実行することを特徴とする時系列データ検索方法。
【請求項６】
前記（Ａ）の第１の近似ステップから前記（Ｄ）の距離算出ステップに至る処理を、前記データベースに記憶した全てのシーケンスに対して繰り返し実行し、
（Ｅ）この繰り返しの結果に基づいて、前記検索対象となるシーケンスの近傍に位置するシーケンスを検索結果として出力する検索結果出力ステップ
をさらに実行することを特徴とする請求項５記載の時系列データ検索方法。
【請求項７】
時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
検索対象となるシーケンスと前記記憶手段で記憶したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する近似手段と、
この近似手段で近似した近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記記憶手段から読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段と
を備えたことを特徴とする時系列データ検索装置。
【請求項８】
時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを各々のシーケンスに対して作成する作成手段と、
検索対象となるシーケンスと前記記憶手段で記憶したシーケンスの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する近似手段と、
この近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記記憶手段から読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段と
を備えたことを特徴とする時系列データ検索装置。
【請求項９】
時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
検索対象となるシーケンスと前記記憶手段で記憶したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する第１の近似手段と、
この第１の近似手段で近似した近似距離が所定の範囲内にある場合には、近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段と、
検索対象となるシーケンスと前記記憶手段から読み出したシーケンスの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する第２の近似手段と、
この第２の近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記記憶手段で記憶したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段と
を備えたことを特徴とする時系列データ検索装置。
【請求項１０】
請求項１乃至６のいずれか１項に記載した時系列データ検索方法をコンピュータに実行させることを特徴とする時系列データ検索プログラム。
【請求項１１】
請求項１乃至６のいずれか１項に記載した時系列データ検索方法をコンピュータに実行させるための時系列データ検索プログラムを記録したことを特徴とするプログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベース検索技術に関し、より詳しくは、ダイナミックタイムワーピングに基づいて時系列データを検索する時系列データ検索方法、時系列データ検索装置、時系列データ検索プログラム、およびプログラム記録媒体に関する。
【０００２】
【従来の技術】
時系列データは、時間軸に沿って要素値が定められているシーケンスとして表現される。
【０００３】
このような時系列データを扱う手法として、ダイナミックタイムワーピング（ＤＴＷ：Ｄｙｎａｍｉｃ  Ｔｉｍｅ  Ｗａｒｐｉｎｇ、時間軸正規化）と呼ばれる手法が知られている。ダイナミックタイムワーピングとは、時間軸に沿ってシーケンスを伸長させ、二つのシーケンスの距離を最小化する変換のことである。
【０００４】
一般に、ユークリッド距離においては、長さやサンプリングレートの異なる時系列データを扱うことが難しいが、ダイナミックタイムワーピングの手法を用いれば、そのような時系列データを比較的容易に扱うことができ、二つのシーケンス間の距離、すなわち類似度をより的確に求めることができる。
【０００５】
ダイナミックタイムワーピング距離について、さらに具体的に説明する。
長さｎのシーケンスＰ＝｛ｐ０，  ｐ１，・・・，  ｐｎ−１｝と長さｍのシーケンスＱ＝｛ｑ０，  ｑ１，・・・，  ｑｍ−１｝が与えられているとき、ダイナミックタイムワーピング距離ＤＤＴＷ（Ｐ，Ｑ）は、次式で定義される：
【数１】
2004348594.tif 000003
ここで、ｇｓｅｇ（−１，  −１）＝０であり、さらに、任意の整数ｉ，  ｊに対してｇｓｅｇ（ｉ，−１）＝ｇｓｅｇ（−１，ｊ）＝∞である。また、式（２）の右辺第２項は、ｇｓｅｇ（ｉ−１，  ｊ）、ｇｓｅｇ（ｉ，  ｊ−１）、ｇｓｅｇ（ｉ−１，  ｊ−１）のうちの最小値を意味する。さらに、式（３）の右辺のαの値は任意であるが、以後の説明においては、便宜上α＝２であるとする。
【０００６】
二つのシーケンスＰとＱの距離は、各シーケンスの要素を昇順にマッチングすることによって得られる。すなわち、ダイナミックタイムワーピングでは、二つのシーケンスの長さが異なっていても、シーケンス間の距離を定義することができる。このようなダイナミックタイムワーピングは、ダイナミックプログラミングと呼ばれるアルゴリズムにしたがって計算され、その計算コストは、およそＯ（ｎｍ）のオーダーであることが知られている。したがって、シーケンス長が長くなると、非常に多くの計算コストが必要となる。
【０００７】
従来、この計算コストを低減するためのさまざまな技術が開示されている。
【０００８】
このうち、非特許文献１に開示されている技術（以後、この技術を従来技術１と呼ぶ）は、ダイナミックタイムワーピングに基づく二つのシーケンス間の距離であるダイナミックタイムワーピング距離を近似し、時系列データの検索を高速化するための手法である。この手法では、シーケンスをなす要素から、（時間的に最初の要素値、時間的に最後の要素値、要素の最小値、要素の最大値）を抽出し、これら４つの要素から成る４次元ベクトルを作成し、この４次元ベクトル間のユークリッド距離をシーケンス間の距離の近似値として採用する。この近似値は、ダイナミックタイムワーピングの下限距離（厳密な距離と等しいか、または下回る値をとる）を示しており、このような近似値を用いることによって、探索漏れを発生させずに、ダイナミックタイムワーピングによる厳密な距離計算回数の削減を図っている。
【０００９】
また、非特許文献２に開示されている技術（以後、この技術を従来技術２と呼ぶ）では、シーケンスを等間隔に分割してサブシーケンスを作成し、このサブシーケンスのうちの最大値と最小値を計算し、そのユークリッド距離を、ダイナミックタイムワーピングの近似値としている。ちなみにこの手法は、ＰＣＡ（Ｐｉｅｃｅｗｉｓｅ  Ｃｏｎｓｔａｎｔ  Ａｐｐｒｏｘｉｍａｔｉｏｎ）と呼ばれている。
【００１０】
【非特許文献１】
Ｓａｎｇ−Ｗｏｏｋ  Ｋｉｍ，  Ｓａｎｇｈｙａｕｎ  Ｐａｒｋ，  ａｎｄ  Ｗｅｓｌｅｙ  Ｗ．  Ｃｈｕ，  ”Ａｎ  Ｉｎｄｅｘ−ｂａｓｅｄ  Ａｐｐｒｏａｃｈ  ｆｏｒ  Ｓｉｍｉｌａｒｉｔｙ  Ｓｅａｒｃｈ  Ｓｕｐｐｏｒｔｉｎｇ  Ｔｉｍｅ  Ｗａｒｐｉｎｇ  ｉｎ  Ｌａｒｇｅ  Ｓｅｑｕｅｎｃｅ  Ｄａｔａｂａｓｅｓ”，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＣＤＥ，  ｐｐ．  ６０７−６１４  （Ａｐｒｉｌ  ２００１）．
【００１１】
【非特許文献２】
Ｅａｍｏｎｎ  Ｊ．  Ｋｅｏｇｈ，  ”Ｅｘａｃｔ  Ｉｎｄｅｘｉｎｇ  ｏｆ  Ｄｙｎａｍｉｃ  Ｔｉｍｅ  Ｗａｒｐｉｎｇ”，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＶＬＤＢ，  ｐｐ．  ４０６−４１７  （Ａｕｇｕｓｔ  ２００２）．
【００１２】
【発明が解決しようとする課題】
しかしながら、上述した従来技術１の場合、近似値を求めるために採用する４次元ベクトルは、時系列データ全体に対して要素数が少ないため、近似値の精度が低く、ダイナミックタイムワーピング距離の計算回数を十分に削減することができないという問題があった。
【００１３】
また、従来技術２の場合にも、従来技術１と同様の問題、すなわち、近似値の精度が低く、ダイナミックタイムワーピング距離の計算回数を十分に削減できないという問題があった。
【００１４】
本発明はこのような事情に鑑みてなされたものであり、その目的は、ダイナミックタイムワーピングを用いた時系列データの検索を高速化することのできる時系列データ検索方法、時系列データ検索装置、時系列データ検索プログラム、およびプログラム記録媒体を提供することにある。
【００１５】
【課題を解決するための手段】
上記目的を達成するために、請求項１記載の発明は、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索方法であって、複数のシーケンスを格納して記憶するデータベースを備えたコンピュータシステムが、（Ａ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する近似ステップと、（Ｂ）前記（Ａ）の近似ステップで近似した近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記データベースから読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出ステップとを実行することを要旨とする。
【００１６】
請求項２記載の発明は、請求項１記載の発明において、前記（Ａ）の近似ステップと、前記（Ｂ）の距離算出ステップを、前記データベースに記憶した全てのシーケンスに対して繰り返し実行し、（Ｃ）この繰り返しの結果に基づいて、前記検索対象となるシーケンスの近傍に位置するシーケンスを検索結果として出力する検索結果出力ステップをさらに実行することを要旨とする。
【００１７】
請求項３記載の発明は、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索方法であって、複数のシーケンスを格納して記憶するデータベースを備えたコンピュータシステムが、（Ａ）近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成ステップと、（Ｂ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、前記（Ａ）の作成ステップで作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する近似ステップと、（Ｃ）この近似ステップで求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記データベースから読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出ステップとを実行することを要旨とする。
【００１８】
請求項４記載の発明は、請求項３記載の発明において、前記（Ａ）の作成ステップから前記（Ｃ）の距離算出ステップに至る処理を、前記データベースに記憶した全てのシーケンスに対して繰り返し実行し、（Ｄ）この繰り返しの結果に基づいて、前記検索対象となるシーケンスの近傍に位置するシーケンスを検索結果として出力する検索結果出力ステップをさらに実行することを要旨とする。
【００１９】
請求項５記載の発明は、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索方法であって、複数のシーケンスを格納して記憶するデータベースを備えたコンピュータシステムが、（Ａ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する第１の近似ステップと、（Ｂ）前記（Ａ）の第１の近似ステップで近似した近似距離が所定の範囲内にある場合には、近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成ステップと、（Ｃ）検索対象となるシーケンスと前記データベースから読み出したシーケンスの距離を、前記（Ｂ）の作成ステップで作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する第２の近似ステップと、（Ｄ）前記（Ｃ）の第２の近似ステップで求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記データベースから読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出ステップとを実行することを要旨とする。
【００２０】
請求項６記載の発明は、請求項５記載の発明において、前記（Ａ）の第１の近似ステップから前記（Ｄ）の距離算出ステップに至る処理を、前記データベースに記憶した全てのシーケンスに対して繰り返し実行し、（Ｅ）この繰り返しの結果に基づいて、前記検索対象となるシーケンスの近傍に位置するシーケンスを検索結果として出力する検索結果出力ステップをさらに実行することを要旨とする。
【００２１】
請求項７記載の発明は、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索装置であって、複数のシーケンスを格納して記憶する記憶手段と、検索対象となるシーケンスと前記記憶手段で記憶したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する近似手段と、この近似手段で近似した近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記記憶手段から読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段とを備えたことを要旨とする。
【００２２】
請求項８記載の発明は、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索装置であって、複数のシーケンスを格納して記憶する記憶手段と、近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを各々のシーケンスに対して作成する作成手段と、検索対象となるシーケンスと前記記憶手段で記憶したシーケンスの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する近似手段と、この近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記記憶手段から読み出したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段とを備えたことを要旨とする。
【００２３】
請求項９記載の発明は、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データをダイナミックタイムワーピングに基づいて検索する時系列データ検索装置であって、複数のシーケンスを格納して記憶する記憶手段と、検索対象となるシーケンスと前記記憶手段で記憶したシーケンスの距離を、離散フーリエ変換の係数値を用いて近似する第１の近似手段と、この第１の近似手段で近似した近似距離が所定の範囲内にある場合には、近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段と、検索対象となるシーケンスと前記記憶手段から読み出したシーケンスの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する第２の近似手段と、この第２の近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスと前記記憶手段で記憶したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段とを備えたことを要旨とする。
【００２４】
請求項１０記載の発明は、請求項１乃至６のいずれか１項に記載した時系列データ検索方法をコンピュータに実行させることを要旨とする。
【００２５】
請求項１１記載の発明は、請求項１乃至６のいずれか１項に記載した時系列データ検索方法をコンピュータに実行させるための時系列データ検索プログラムを記録したことをを要旨とする。
【００２６】
【発明の実施の形態】
以下、添付図面を参照して本発明の実施の形態を説明する。
【００２７】
（第１の実施形態）
図１は、本発明の第１の実施形態に係る時系列データ検索方法を実行するコンピュータシステムである時系列データ検索装置の概略構成を示す機能ブロック図である。同図に示す時系列データ検索装置１は、各種データを入力するためのキーボード、マウス等の入力装置から成る入力部１１、中央処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備え、後述する各種処理の制御および演算を行う制御演算部１２、入力部１１からの入力情報や制御演算部１２からの演算結果等を格納して記憶する記憶部１３、この記憶部１３で記憶した情報を出力するための（液晶）ディスプレイ画面等の出力装置から成る出力部１４を少なくとも有している。
【００２８】
記憶手段の少なくとも一部をなす記憶部１３は、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等から構成される主記憶装置と、ハードディスクドライブ、フレキシブルディスクドライブ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）ドライブ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）ドライブ、光磁気ディスクドライブ、ＰＣカードドライブ等から構成される補助記憶装置とを具備しており、データ検索に必要なシーケンス情報を管理、記憶するデータベースとしての機能を有する。また、後述する計算結果を随時格納するために必要なメモリ領域が確保されている。
【００２９】
なお、本実施形態の各種処理は、一つの電子的な装置が実行する場合だけでなく、各ステップの実行を適宜分割して二つ以上の電子的な装置から構築されたシステムが全体で実行する場合も含まれる。この意味で、本実施形態に係る「時系列データ検索装置」は、一つまたは複数のコンピュータ（システム）によって構成されることはいうまでもない。この点は、本発明の全ての実施の形態に共通する事項である。
【００３０】
次に、以上の構成を有する時系列データ検索装置１が実行する時系列データ検索処理の詳細を説明する。
【００３１】
最初に、ダイナミックタイムワーピング距離の近似方法（距離近似方法）について説明した後、この距離近似方法を用いた時系列データ検索方法について説明する。
【００３２】
＜距離近似方法＞
本実施形態に係る時系列データ検索方法では、ダイナミックタイムワーピング距離ＤＤＴＷの計算回数をできるだけ削減するために、離散フーリエ変換（ＤＦＴ：Ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）を用いて近似距離の計算を行う。
【００３３】
長さｎのシーケンスＰ＝｛ｐ０，  ｐ１，・・・，  ｐｎ−１｝が与えられているとき、このシーケンスＰの離散フーリエ変換Ｆ（Ｐ）＝｛ｆ０（Ｐ），  ｆ１（Ｐ），・・・，  ｆｎ−１（Ｐ）｝の各成分（ＤＦＴ係数）は、次式で定義される：
【数２】
2004348594.tif 000004
ここで、ｋ≠０に対して、ｆｎ−ｋ（Ｐ）はｆｋ（Ｐ）の複素共役となる。本実施形態では、シーケンスＰの各要素が実数であることを仮定する。このため、ｆ０（Ｐ）は式（４）により実数となる。
【００３４】
逆に、離散フーリエ変換Ｆ（Ｐ）が与えられているとき、シーケンスＰの要素は、Ｆ（Ｐ）に対して逆離散フーリエ変換（ＩＤＦＴ：Ｉｎｖｅｒｓｅ  Ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）
【数３】
2004348594.tif 000005
を施すことによって求めることができる。
【００３５】
以上のように定義される離散フーリエ変換を用いて、検索対象となるシーケンス（問い合わせシーケンスと呼ぶ）Ｑ＝｛ｑ０，  ｑ１，・・・，  ｑｎ−１｝から任意のシーケンスＰまでの距離近似方法を説明する。ここでは、両シーケンスの位置関係に応じて近似距離を求める。なお、以後の説明においては、ｍｉｎ（Ｐ）およびｍｉｎ（Ｑ）を、それぞれシーケンスＰおよびＱの最小値とする一方、ｍａｘ（Ｐ）およびｍａｘ（Ｑ）を、それぞれシーケンスＰおよびＱの最大値とする。
【００３６】
二つのシーケンスＰとＱの位置関係は、図２の概念図に示すように、次の３つの場合がある：
（１）ｍｉｎ（Ｐ）≧ｍａｘ（Ｑ）  （図２（ａ）：この配置をｄｉｓｊｏｉｎｔ呼ぶ）
（２）ｍｉｎ（Ｐ）＜ｍａｘ（Ｑ）かつｍａｘ（Ｐ）＞ｍｉｎ（Ｑ）  （図２（ｂ）：この配置をｏｖｅｒｌａｐと呼ぶ）
（３）ｍａｘ（Ｐ）≦ｍｉｎ（Ｑ）  （図２（ｃ）：この配置をｄｉｓｊｏｉｎｔ（−）と呼ぶ）
以下、これら３つの位置関係の場合について、それぞれ近似距離を計算する。
【００３７】
（１）ｄｉｓｊｏｉｎｔ
問合せシーケンスＱの下限シーケンスＱｌｏｗｅｒ＝｛ｑｌ０，  ｑｌ１，・・・，  ｑｌｎ−１｝と上限シーケンスＱｕｐｐｅｒ＝｛ｑｕ０，  ｑｕ１，・・・，  ｑｕｎ−１｝を求める。二つのシーケンスの要素は、ｉ＝０，  １，  ・・・  ，  ｎ−１として、それぞれ次のように定義される。
【数４】
2004348594.tif 000006
ここで、ｍｉｎ（ｑｕｉ：ｑｕｉ＋ｊ）とｍａｘ（ｑｕｉ：ｑｕｉ＋ｊ）は、部分シーケンス｛ｑｉ，  ｑｉ＋１，・・・，  ｑｉ＋ｊ｝の最小値と最大値をそれぞれ表す。
【００３８】
式（６）および（７）の右辺に出てくるｌｅｘｔは、ダイナミックタイムワーピングによってシーケンスが伸長する場合の最大伸長の値を表す。換言すれば、ダイナミックタイムワーピングによるシーケンスの伸長は、たかだかｌｅｘｔに制限される。このｌｅｘｔは、ｍｉｎ（Ｐ）≧０かつｍｉｎ（Ｑ）≧０のとき、
【数５】
2004348594.tif 000007
である。ここで、右辺に用いられている記号［ｘ］は、ｘの値を超えない最大の整数を意味している。
【００３９】
式（８）の右辺において、
【数６】
2004348594.tif 000008
はシーケンスＰとＱの２乗ユークリッド距離である。ｗはダイナミックタイムワーピングの幅であり、特に制限がなければ、ｗ＝ｎ−１である。Ｅ（Ｐ）とＥ（Ｑ）は、シーケンスＰとＱのエネルギーであり、それぞれ次式で与えられる：
【数７】
2004348594.tif 000009
また、δ（Ｐ，Ｑ）＝（ｍｉｎ（Ｐ）−ｍａｘ（Ｑ））２である。
【００４０】
ここで、ｍｉｎ（Ｐ）＜ｍｉｎ（Ｑ）かつｍｉｎ（Ｐ）＜０のときには、式（１０）のＥ（Ｐ）と式（１１）のＥ（Ｑ）を、以下のＥ’（Ｐ）とＥ’（Ｑ）にそれぞれ置き換える。
【数８】
2004348594.tif 000010
【００４１】
また、ｍｉｎ（Ｐ）＞ｍｉｎ（Ｑ）かつｍｉｎ（Ｑ）＜０のときには、式（１２）および式（１３）のｍｉｎ（Ｐ）をｍｉｎ（Ｑ）としてｌｅｘｔを求めることができる。
【００４２】
シーケンスＰが全てのＤＦＴ係数を用いて展開されている場合には、２乗ユークリッド距離Ｄ２Ｅｕｃｌｉｄ（Ｐ，Ｑ）は式（９）で与えられるが、そのＤＦＴ係数のうちの（ｍ＋１）個（ｍ≦ｎ−１）のみを用いて展開されている場合には、式（６）において、Ｄ２Ｅｕｃｌｉｄ（Ｐ，Ｑ）の代わりに、以下で定義されるＤｍｏｄｉｆｉｅｄ（Ｐ，Ｑ）を用いる：
【数９】
2004348594.tif 000011
【００４３】
以上により、ｄｉｓｊｏｉｎｔの場合のダイナミックタイムワーピング距離ＤＤＴＷ（Ｐ，Ｑ）の近似距離は、次のように求められる。
【数１０】
2004348594.tif 000012
【００４４】
図３は、Ｄｄｉｓｊｏｉｎｔ（Ｐ，Ｑ）の計算を概念的に示す説明図である。同図において、問合せシーケンスＱは、下限シーケンスＱｌｏｗｅｒと上限シーケンスＱｕｐｐｅｒに囲まていれる。ＰとＱの位置関係がｄｉｓｊｏｉｎｔ（ｍｉｎ（Ｐ）≧ｍａｘ（Ｑ））の場合、Ｑｕｐｐｅｒを用いて近似距離の計算を行う（式（１５）を参照）。このとき、Ｄｄｉｓｊｏｉｎｔ（Ｐ，Ｑ）は、ダイナミックタイムワーピング距離ＤＤＴＷ（Ｐ，Ｑ）を近似しており、なおかつＤＤＴＷ（Ｐ，Ｑ）以下の値をとる。
【００４５】
（２）ｏｖｅｒｌａｐ
図２（ｂ）に示すように、二つのシーケンスＰとＱの少なくとも一部が重なり合うとき、最大伸長の値は、ｌｅｘｔ＝ｗである。上述したＱｌｏｗｅｒおよびＱｕｐｐｅｒに加えて、
【数１１】
2004348594.tif 000013
を用いることにより、ｏｖｅｒｌａｐにおける近似距離Ｄｏｖｅｒｌａｐ（Ｐ，Ｑ）を次のように求めることができる：
【数１２】
2004348594.tif 000014
【００４６】
（３）ｄｉｓｊｏｉｎｔ（−）
本質的には、上記（１）ｄｉｓｊｏｉｎｔの場合と同じであり、近似距離
Ｄｄｉｓｊｏｉｎｔ（−）（Ｐ，Ｑ）は、次式で定義される：
【数１３】
2004348594.tif 000015
【００４７】
このｄｉｓｊｏｉｎｔ（−）の場合、式（８）におけるδ（Ｐ，Ｑ）＝（ｍｉｎ（Ｑ）−ｍａｘ（Ｐ））２であるが、他の量については、上述したｄｉｓｊｏｉｎｔの場合と同じである。
【００４８】
＜時系列データ検索方法＞
時系列データ検索処理を高速化するための特徴量として、本実施形態では離散フーリエ変換に基づいたＤＦＴ特徴ベクトルを用いる。
【００４９】
シーケンスＰのＤＦＴ特徴ベクトルＶ（Ｐ）は、次のように定義される：
Ｖ（Ｐ）＝｛Ｆ（Ｐ），  ｍｉｎ（Ｐ），  ｍａｘ（Ｐ），  Ｅｒｅｓｔ（Ｐ），  γ（Ｐ）｝      （２１）
ここで、Ｐの離散フーリエ変換Ｆ（Ｐ）が（ｍ＋１）次元であるとすると、このＤＦＴ特徴ベクトルＶ（Ｐ）の次元は２ｍ＋５である。
【００５０】
このような多次元データの問合せとして、ここではｋ近傍距離（ｋは所定の正の整数）以下の近似距離を有するシーケンスを探索するｋ近傍問合せを採用する。これ以外に、例えば範囲指定問合せを用いても、時系列データ検索のアルゴリズムは本質的に同じである。この点に関しては、後述する実施形態でも同様である。
【００５１】
図４は、本実施形態に係る時系列データ検索方法において、離散フーリエ変換を用いた近傍探索処理の流れを示すフローチャート図である。
【００５２】
まず、問合せシーケンスＱを入力してこのシーケンスＱのＤＦＴ特徴ベクトルＶ（Ｑ）を計算するとともに、近傍探索数ｋを入力する（ステップＳ１０１）。
【００５３】
その後、シーケンスを順序付けしてカウントするカウンタｉの値を０とする（ステップＳ１０２）。
【００５４】
次に、ループＬ１１を実行する。
【００５５】
ループＬ１１では，まずカウンタｉの値を１増加させ（ステップＳ１１１）、記憶部１３からシーケンスＰおよびこのシーケンスのＤＦＴ特徴ベクトルＶ（Ｐ）をロードし（ステップＳ１１２）、ＰとＱのＤＦＴ特徴ベクトルを用いた近似距離Ｄ１を計算する（ステップＳ１１３）。
【００５６】
このステップでは、近似距離Ｄ１として、Ｄｄｉｓｊｏｉｎｔ（Ｐ，Ｑ），  Ｄｏｖｅｒｌａｐ（Ｐ，Ｑ），  Ｄｄｉｓｊｏｉｎｔ（−）（Ｐ，Ｑ）のいずれかを計算することになるが、全てのシーケンスに対して近似距離を求める計算を行うと、多くのＣＰＵコストを要することになる。そこで、制御演算部１２では、記憶部１３に格納されているシーケンスにアクセスする前に、問合せシーケンスＱにおけるさまざまなシーケンス伸長ｌ１，  ｌ２，  ・・・  ，  ｌｈを想定し、これらのｈ個のシーケンス伸長の上限および下限を用意することもできる。
【００５７】
一例として、Ｄｄｉｓｊｏｉｎｔ（Ｐ，Ｑ）が伸長ｌｅｘｔを要求する場合、ｌｉ≧ｌｅｘｔを満足するシーケンス伸長の中で最小のものを選択し、ｌ’ｅｘｔとする：
【数１４】
2004348594.tif 000016
制御演算部１２がＤｄｉｓｊｏｉｎｔ（Ｐ，Ｑ）を計算する際には、このｌ’ｅｘｔに関する上限および下限を用いる。他の近似距離についても同様である。
【００５８】
ステップＳ１１３での計算の結果、求めたＤ１がｋ近傍距離以下であれば（ステップＳ１１４でＹＥＳ）、厳密なダイナミックタイムワーピング距離Ｄ３＝ＤＤＴＷ（Ｐ，Ｑ）を求める（ステップＳ１１５）。
【００５９】
ステップＳ１１５で求めたＤ３がｋ近傍距離以下であれば（ステップＳ１１６でＹＥＳ）、シーケンスＰのＩＤと距離Ｄ３を記憶部１３の最近傍リストへ格納し、ソートする（ステップＳ１１７）。
【００６０】
ステップＳ１１７が終了後、または、ステップＳ１１４かステップＳ１１６の判断でＮＯの場合には、その時点でのシーケンスの数ｉが記憶部１３に格納されているシーケンスの数に達するまで（ｉ＞＝ｅｎｔ）、ステップＳ１１１に戻って処理を繰り返す。すなわち、記憶部１３に格納されているシーケンスの各々に対して、ループＬ１１の処理が繰り返し実行される。
【００６１】
いうまでもなく、このループＬ１１では、最初のｋ回は常にステップＳ１１４およびステップＳ１１６における判断がＹＥＳとなる。
【００６２】
ループＬ１１が終了後、最近傍リストに格納されている候補シーケンスを最終的な探索結果として出力する（ステップＳ１２１）。
【００６３】
ここで説明した近似距離Ｄ１とダイナミックタイムワーピング距離Ｄ３の計算は、時系列データ検索装置１の制御演算部１２で行われる。したがって、制御演算部１２が、検索対象となる問合せシーケンスＱと記憶部１３に格納されているシーケンスＰの距離をＤＦＴ係数値を用いてを用いて近似する近似手段としての機能と、近似距離が所定の範囲内にある場合に、ＰとＱの間のダイナミックタイムワーピング距離を求める距離算出手段としての機能とを具備していることはいうまでもない。
【００６４】
近似距離の計算は、厳密なダイナミックタイムワーピングの距離計算よりも計算コストが低い。したがって、以上説明したように、まず近似距離を計算した上で、この計算した近似距離がその時点での最近傍処理よりも大きければ、厳密な計算をせずに初めから除外することができ、厳密な計算は、最近傍距離よりも小さいものに関してのみ行うことが可能となる。
【００６５】
以上説明した本発明の第１の実施形態によれば、ダイナミックタイムワーピングに基づく時系列データの検索を、検索漏れを発生させずに高速化することが可能となる。
【００６６】
本実施形態における時系列データ検索方法は、時系列データとして表現することができる画像、映像、音声、文書等を対象とする広範囲の時系列データ検索に適用可能である。
【００６７】
なお、本実施形態に係る時系列データ検索処理は、時系列データ検索プログラムがインストールされた所定のコンピュータを用いて実施しても同様の効果を得ることができる。
【００６８】
さらに、そのような時系列データ検索プログラムを記録したコンピュータ読み取り可能なプログラム記録媒体をコンピュータに装着し、そのプログラム記録媒体に格納されているプログラムを読み出すことによって、コンピュータが上述した処理を実行するようにしてもよい。ここで、「コンピュータ読み取り可能な」プログラム記録媒体としては、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、光磁気ディスク、ＰＣカード等を用いることができる。このようなプログラム記録媒体を提供することによって、本実施形態の時系列データ検索プログラムを広く流通させることができるようになる。
【００６９】
これらの時系列データプログラムならびに当該プログラムを記録したプログラム記録媒体については、本発明の全ての実施の形態において同様のことがいえる。
【００７０】
（第１の実施形態の変形例）
本実施形態においては、二つのシーケンスＰとＱの長さが等しい場合を取り扱ったが、異なる長さのシーケンス長を計算するために、全てのシーケンスの長さが等しくなるように調整することも可能である。
【００７１】
この場合、まず基準長ｎｂａｓｅを決定し、この基準長ｎｂａｓｅよりも長いシーケンス長を縮小する一方で、基準長ｎｂａｓｅよりも短いシーケンス長を伸長する。このような調整を行った後は、二つのシーケンスの長さが見かけ上等しくなるため、第１の実施形態と同じ方法で近似距離を求めることが可能となる。
【００７２】
シーケンス長の調整法をより詳細に説明する。
【００７３】
まず、Ｐ（の要素）を用いることにより、Ｐの下限シーケンスＰｌｏｗｅｒと上限シーケンスＰｕｐｐｅｒを以下のように計算する：
【数１５】
2004348594.tif 000017
ここで、下限シーケンスＰｌｏｗｅｒの要素ｐｌｉと上限シーケンスＰｕｐｐｅｒの要素ｐｕｉ（ともにｉ＝０，  １，  …  ，  ｎｂａｓｅ）は、
【数１６】
2004348594.tif 000018
であり、これらのシーケンス長は、基準長ｎｂａｓｅである。
【００７４】
以上のように計算したＰｌｏｗｅｒおよびＰｕｐｐｅｒの少なくともいずれか一方を、もとのシーケンスＰの代わりに用いることにより、ダイナミックタイムワーピングの近似距離を求める。
【００７５】
問合せシーケンスＱについても、その長さを調整する。まず、式（１７）、（１８）と同様にＱｌｏｗｅｒとＱｕｐｐｅｒを作成する。その後、前述したＱｌｏｗｅｒから下限シーケンスＱ’ｌｏｗｅｒ＝｛ｑｌ’０，  ｑｌ’１，・・・，  ｑｌ’ｎ−１｝を、Ｑｕｐｐｅｒから上限シーケンスＱ’ｕｐｐｅｒ＝｛ｑｕ’０，  ｑｕ’１，・・・，  ｑｕ’ｎ−１｝を計算する。ここで、
【数１７】
2004348594.tif 000019
である。式（２４）および式（２５）の右辺の定義は、それぞれ式（６）および式（７）の右辺の定義と同じである。
【００７６】
ここで、ＰとＱの位置関係がｄｉｓｊｏｉｎｔの場合、ｌｅｘｔは、式（８）において、ＰにＰｌｏｗｅｒを代入し、ＱにＱｕｐｐｅｒを代入することによって計算される。また、ＰとＱの位置関係がｏｖｅｒｌａｐの場合、シーケンスの伸長幅はｌｅｘｔ＝ｗである。ＰとＱの位置関係がｄｉｓｊｏｉｎｔ（−）の場合、ｌｅｘｔは、式（８）において、ＰにＰｕｐｐｅｒを代入し、ＱにＱｌｏｗｅｒを代入することによって計算される。
【００７７】
ダイナミックタイムワーピングの近似距離は、ｄｉｓｊｏｉｎｔを計算するためにＰｌｏｗｅｒとＱ’ｕｐｐｅｒを用い、ｄｉｓｊｏｉｎｔ（−）を計算するためにＰｕｐｐｅｒとＱ’ｌｏｗｅｒを用いる。また、ｏｖｅｒｌａｐを計算するために、４つの量全てを用いる。
【００７８】
以上の点を除く時系列データ検索方法については、上記第１の実施形態と同じである。
【００７９】
したがって、このような第１の実施形態の変形例においても、上記第１の実施形態と同様の効果を得ることができる。
【００８０】
（第２の実施形態）
本発明の第２の実施形態に係る時系列データ検索方法は、ダイナミックタイムワーピング距離を計算するための近似値の算出に、セグメンティッド・シーケンスを用いることを特徴とする。
【００８１】
本実施形態に係る時系列データ検索装置の基本的な構成は、上記第１の実施形態で説明したものと同様である（図１を参照）。
【００８２】
＜セグメンティッド・シーケンス＞
まず、セグメンティッド・シーケンスについて説明する。
【００８３】
範囲ｒと長さｎのシーケンスＰが与えられたとき、セグメンティッド・シーケンスＳｒは次のように定義される。
【００８４】
Ｓｒ＝｛ｓ０，  ｓ１，  ・・・，  ｓｎｓ−１｝        （２６）
ｓｉ＝｛ｓｌｉ，  ｓｕｉ，  ｓｒｉ｝
（ｎｓ≦ｎ，  １≦ｓｒｉ≦ｎ，ｓｕｉ−ｓｌｉ≦ｒ）
ここで、ｓｌｉはセグメンティッド・シーケンスＳｒの中のセグメントｓｉの最小値であり、ｓｕｉはセグメンティッド・シーケンスＳｒの中のセグメントｓｉの最大値である。したがって、ｓｕｉ−ｓｌｉはｓｉの範囲であり、ｓｕｉ−ｓｌｉ≦ｒである。また、ｓｒｉはｓｉの長さを、ｎｓはＳｒにおけるセグメントの数を示している。
【００８５】
図５は、セグメンティッド・シーケンスを作成するためのアルゴリズムを示すフローチャート図である。
【００８６】
まず、シーケンスの長さｎ、範囲ｒ、およびシーケンスＰの要素ｐｉ（ｉ＝０，  １，  ・・・，ｎ−１）を入力し（ステップＳ２０１）、カウンタｉを０にセットする（ステップＳ２０２）。
【００８７】
次に、ループＬ２１を実行する。
【００８８】
このループＬ２１では、隣接するｉ番目の要素ｐｉと（ｉ＋１）番目の要素のｐｉ＋１の差｜ｐｉ−ｐｉ＋１｜（ＬＩＳＴ．ｄｉｆｆｉという関数として定義）をｉ＝ｎ−１まで全て求める（ステップＳ２１１、Ｓ２１２）。
【００８９】
ループＬ２１が終了後、記憶部１３に格納されているデータをＬＩＳＴ．ｄｉｆｆｉのｉの昇順にソートする（ステップＳ２２１）。
【００９０】
その後、カウンタｉを０にリセットし（ステップＳ２２２）、ループＬ２３に移行する。
【００９１】
ループＬ２３では、近接するシーケンスの要素のペアを、要素の値の差が小さいものから順番に結合してセグメントにする（ステップＳ２３２）。
【００９２】
そして、近接するセグメントを結合して、より大きなセグメントにする（ステップＳ２３１、Ｓ２３２、Ｓ２３３、Ｓ２３４）。
【００９３】
近接する要素もしくはセグメントの差が、閾値ｒを超えた時点でループＬ２３を終了する。
【００９４】
この後、ふたたびセグメントとカウンタを初期値に戻し（ステップＳ２４１）、ループＬ２５に移行する。
【００９５】
ループＬ２５では、最初のセグメントから順に生成されたセグメントの数を数えていく。この処理は、シーケンスの長さｎに達するまで処理を続ける（ステップＳ２５１）。
【００９６】
最終的なｉの値をｎｓとして（ステップＳ２６１）、セグメンティッド・シーケンスＳｒとセグメント数ｎｓを結果として出力する（ステップＳ２６２）。
【００９７】
図６は、このようにして生成されたセグメンティッド・シーケンスＳｒの例を示す図である。
【００９８】
同図に示すセグメンティッド・シーケンスＳｒは、３つのセグメントｓ０，  ｓ１，  ｓ２から構成されている。これらのセグメントの範囲ｓｕｉ−ｓｌｉ  （ｉ＝０，１，２）は、所定の範囲（閾値）ｒよりも小さい。
【００９９】
＜距離近似方法＞
本実施形態に係る時系列データ検索方法は、セグメンティッド・シーケンスを用いることによって近似を行うものである。
【０１００】
セグメント数ｎｓのセグメンティッド・シーケンスＳ＝｛ｓ０，  ｓ１，  ・・・，  ｓｎｓ−１｝とセグメント数ｎｔのセグメンティッド・シーケンスＴ＝｛ｔ０，  ｔ１，  ・・・，  ｔｎｔ−１｝が与えられているとき、近似値Ｄｓｅｇｍｅｎｔ（Ｓ，Ｔ）は、次の演算によって得られる。
【０１０１】
【数１８】
2004348594.tif 000020
【０１０２】
ここで、ｇｕｒ（−１，−１）＝０であり、さらに、任意の整数ｉ，  ｊに対してｇｌｒ（ｉ，−１）＝ｇｕｒ（ｉ，−１）＝ｇｕｌ（−１，ｊ）＝ｇｕｒ（−１，ｊ）＝∞であるとする。また、ｇｓｅｇ（ｉ，ｊ）の定義式の右辺にあるαの値は任意であるが、少なくとも上述したユークリッド２乗距離におけるαと同じ値でなければならないので、ここではα＝２とするが、これにより、本実施形態が特段の限定を受けるわけでないことは勿論である。ちなみに、ｇｌｌ，  ｇｌｒ，  ｇｕｌ，  ｇｕｒは、それぞれ各セグメントにおける左下、右下、左上、右上の計算結果である。
【０１０３】
図７は、セグメンティッド・シーケンスを用いて行うシーケンスＳとＴの近似距離の計算を概念的に示す図である。同図に示す場合には、二つのシーケンスＳとＴのセグメントの個数が、それぞれｎｓ＝３，  ｎｔ＝５に対応している。したがって、この場合のシーケンス間の距離の近似値Ｄｓｅｇｍｅｎｔ（Ｓ，Ｔ）は、Ｄｓｅｇｍｅｎｔ（Ｓ，Ｔ）＝ｇｕｒ（２，４）となる。
【０１０４】
＜時系列データ検索方法＞
図８は、時系列データ検索方法においてセグメンティッド・シーケンスを用いた時系列データ検索処理の流れを示すフローチャート図である。なお、ここでの探索処理においても、ｋ近傍問合せを採用する。これ以外に、例えば範囲指定問合せを用いても、時系列データ検索のアルゴリズムは本質的に同じであることは第１の実施形態と同様である。
【０１０５】
まず、問合せシーケンスＱを入力して、このＱのセグメンティッド・シーケンスを上述した方法に従って計算するとともに、記憶部１３に格納されているシーケンスの数を入力する（ステップＳ３０１）。
【０１０６】
その後、シーケンスを順序付けしてカウントするカウンタｉの値を０とする（ステップＳ３０２）。
【０１０７】
次に、ループＬ３１を実行する。
【０１０８】
ループＬ３１では，まずカウンタｉの値を１増加させ（ステップＳ３１１）、記憶部１３からシーケンスＰのセグメンティッド・シーケンスをロードして（ステップＳ３１２）、ＰとＱのセグメンティッド・シーケンスを用いた近似距離Ｄ２＝Ｄｓｅｇｍｅｎｔ（Ｐ，Ｑ）を計算する（ステップＳ３１３）。
【０１０９】
ステップＳ３１３で求めたＤ２がｋ近傍距離以下であれば（ステップＳ３１４でＹＥＳ）、厳密な距離であるダイナミックタイムワーピング距離Ｄ３＝ＤＤＴＷ（Ｐ，Ｑ）を求める（ステップＳ３１５）。
【０１１０】
このステップで求めたＤ３がｋ近傍距離以下であれば（ステップＳ３１６でＹＥＳ）、シーケンスＰのＩＤと距離Ｄ３を記憶部１３の最近傍リストへ格納し、ソートする（ステップＳ３１７）。
【０１１１】
ステップＳ３１７が終了後、またはステップＳ３１４かステップＳ３１６の判断でＮＯの場合には、その時点でのシーケンスの数ｉが記憶部１３に格納されているシーケンスの数に達するまで（ｉ＞＝ｅｎｔ）、ステップＳ３１１に戻って処理を繰り返す。すなわち、記憶部１３に格納されているシーケンスの各々に対して、ループＬ３１の処理を行う。
【０１１２】
このループＬ３１でも、最初のｋ回は常にステップＳ３１４およびステップＳ３１６での判断がＹＥＳとなる。
【０１１３】
ループＬ３１が終了後、最近傍リストに格納されている候補シーケンスを最終的な探索結果として出力する（ステップＳ３２１）。
【０１１４】
ここで説明した近似距離Ｄ２とダイナミックタイムワーピング距離Ｄ３の計算は、時系列データ検索装置１の制御演算部１２で行われる。したがって、本実施形態においては、制御演算部１２が、ＰとＱ各々において近接する要素から順番に要素を結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段としての機能と、ＰとＱの距離の近似値を、各々のシーケンスに対応するセグメンティッド・シーケンスを用いて計算する近似手段としての機能と、その近似距離が所定の範囲内にある場合に、ＰとＱの間のダイナミックタイムワーピング距離を求める距離算出手段としての機能とを具備していることはいうまでもない。
【０１１５】
以上説明した本発明の第２の実施形態によれば、第１の実施形態と同様の効果を得ることができる。
【０１１６】
（第３の実施形態）
本発明の第３の実施形態に係る時系列データ検索方法は、上述した二つの実施形態の距離近似方法（ＤＦＴ，セグメンティッド・シーケンス）を共に利用するものである。
【０１１７】
本実施形態に係る時系列データ検索装置の構成は、図１に示す時系列データ検索装置１と同じである。
【０１１８】
このために、本実施形態においては、インデックスを構成する。図９は、このインデックスを概念的に示すと共に、そのインデックスの構成要素を示す説明図である。同図に示すように、インデックス５１は、多次元インデックス５３とシーケンスファイル５５から構成されている。
【０１１９】
多次元インデックス５３は、ＤＦＴ特徴ベクトルＶ（Ｐ）（式（１５）を参照）と包囲矩形から構成される一方で、シーケンスファイル５５は、シーケンスＰとセグメンティッド・シーケンス（式（２０）を参照）から構成される。
【０１２０】
本実施形態では、多次元インデックス５３として、ＤＦＴ特徴ベクトルＶ（Ｐ）を（２ｍ＋５）次元空間の点とみなし、これらの点を、予め超矩形面によって包囲することにより形成される包囲矩形が、検索木におけるノードの構造を有している場合を想定し、以後の説明を行う。
【０１２１】
この仮想的な検索木は、最上位層の根ノードから出発して枝が延出し、各ノードが包囲矩形に対応している。根ノード以外のノードのうち、一つの包囲矩形に囲まれた複数の点（すなわち、複数のＤＦＴ特徴ベクトル）を格納したノードををリーフノードと呼ぶことにする。また、ここでは延出する枝の数（レベルの数に対応）が同じ値で終端するような平行木の構造を有する場合を想定するが、これが一例に過ぎないのは勿論である。
【０１２２】
＜時系列データ検索処理＞
図１０、図１１および図１２は、本実施形態に係る時系列データ検索処理の流れを示すフローチャート図である。これらの図においては、多次元インデックスを用いた探索アルゴリズムを示しており、ＤＦＴ特徴ベクトルＶ（Ｐ）を用いた近似距離計算と同様に、ＤＦＴ特徴ベクトルＶ（Ｐ）を包含する包囲矩形と問合せシーケンスＱとの近似距離計算についても式（１７）、（１９）、（２０）のいずれかを用いて行う。
【０１２３】
まず、図１０を用いて処理を説明する。
【０１２４】
問合せシーケンスＱにおけるｈ個のペアの下限、上限シーケンスを作成し、それらのＤＦＴ特徴ベクトルＶ（Ｐ）を計算するとともに、制御演算部１２において、キューに根ノードへのポインタ、および距離０を設定する（ステップＳ４０１）。
【０１２５】
次に、ループＬ４１の処理を行う。
【０１２６】
まず、問合せ点（問合せシーケンスＱ）から最も近いノードＮをキューから取り出し、Ｎで示されるノード内のエントリ数を入力する（ステップＳ４１１）。
【０１２７】
この後、ノードＮがリーフノードか否かを判定し（ステップＳ４１２）、リーフノード以外のとき（ステップＳ４１２でＮＯ）、図１１に示す処理Ａを実行する。他方、ノードＮがリーフノードのとき（ステップＳ４１３でＹＥＳ）、処理Ｂを実行する（ステップＳ４１５）。処理ＡおよびＢについては、後述する。
【０１２８】
これらの処理を経て、キューが空になるまでループＬ４１を繰り返し実行した後、最近傍リストに格納されている候補シーケンスを探索結果として出力する（ステップＳ４２１）。
【０１２９】
ここで、図１１のフローチャート図を用いて、処理Ａの詳細を説明する。
【０１３０】
まず、カウンタｉを初期化して０とし（ステップＡ１）、ループＬＡ１を実行する。ループＬＡ１では、カウンタｉの設定後（ステップＡ２）、ノードＮの中でｉ番目に格納されているＤＦＴ特徴ベクトルを用いて近似距離Ｄ１を計算する（ステップＡ３、Ａ４）。近似距離Ｄ１として、Ｄｄｉｓｊｏｉｎｔ（Ｐ，Ｑ），  Ｄｏｖｅｒｌａｐ（Ｐ，Ｑ），  Ｄｄｉｓｊｏｉｎｔ（−）（Ｐ，Ｑ）のいずれかを計算することはいうまでもない。
【０１３１】
Ｄ１がｋ近傍距離以下であれば（ステップＡ５でＹＥＳ）、ノードＮのｉ番目のエントリに格納されている子ポインタと近似距離Ｄ１をキューへ格納する（ステップＡ６）。
【０１３２】
Ｄ１がｋ近傍距離より大きい場合（ステップＡ５でＮＯ）、ステップＡ２に戻って処理を繰り返す。
【０１３３】
このようにして、ループＬＡ１では、ノードＮに格納されている全エントリ（全データオブジェクト）に対する計算を行い、ループＬＡ１が終了後、キューの先頭データを削除してデータを前詰めし、近似距離Ｄ１の昇順にキュー内のデータをソートする（ステップＡ７）。
【０１３４】
以上の処理が終了後、図１０のフローチャート図に戻って処理を行う。
【０１３５】
次に、図１２のフローチャート図を用いて、Ｎがリーフノードであるときの処理Ｂの詳細を説明する。
【０１３６】
まず、カウンタｉを初期化して０とし（ステップＢ１）、ループＬＢ１を実行する。ループＬＡ１では、カウンタｉの設定後（ステップＢ２）、ノードＮの中でｉ番目に格納されているＤＦＴ特徴ベクトルを用いて近似距離Ｄ１を計算する（ステップＢ３、Ｂ４）。ここでも、近似距離Ｄ１は、Ｄｄｉｓｊｏｉｎｔ（Ｐ，Ｑ），  Ｄｏｖｅｒｌａｐ（Ｐ，Ｑ），  Ｄｄｉｓｊｏｉｎｔ（−）（Ｐ，Ｑ）のいずれかである。
【０１３７】
Ｄ１がｋ近傍距離以下であれば（ステップＢ４でＹＥＳ）、セグンメンティッド・シーケンスを用いて近似距離Ｄ２＝Ｄｓｅｇｍｅｎｔ（Ｐ，Ｑ）を計算する（ステップＢ５）。
【０１３８】
このＤ２もｋ近傍距離以下であれば（ステップＢ６でＹＥＳ）、厳密なダイナミックタイムワーピング距離Ｄ３＝ＤＤＴＷ（Ｐ，Ｑ）を計算する（ステップＢ８）。
【０１３９】
ステップＢ８で求めたＤ３がｋ近傍距離以下であれば（ステップＢ９でＹＥＳ）、シーケンスＰのＩＤと距離Ｄ３を記憶部１３の最近傍リストへ格納し、ソートする（ステップＢ１０）。
【０１４０】
ステップＢ１０が終了後、または、ステップＢ５、Ｂ７，Ｂ９のいずれかにおける判断でＮＯの場合には、その時点でのシーケンスの数ｉが記憶部１３に格納されているシーケンスの数に達するまで（ｉ＞＝ｅｎｔ）、ステップＢ２に戻って処理を繰り返す。すなわち、記憶部１３に格納されているシーケンスの各々に対して、ループＬＢ１の処理が繰り返し実行される。
【０１４１】
ループＬＢ１が終了後、最近傍リストによるキューのフィルタリングを行い、キューの中でアクセスする必要のないデータを削除する（ステップＢ１１）。
【０１４２】
その後、キューの先頭データを削除してデータを前詰めする（ステップＢ１２）。
【０１４３】
以上の処理が終了後、図１０のフローチャート図に戻って処理を行う。
【０１４４】
なお、本実施形態においても、ｋ近傍問合せの代わりに、範囲問合せを用いても勿論かまわない。
【０１４５】
ここで説明した近似距離Ｄ１，  Ｄ２，  ならびにダイナミックタイムワーピング距離Ｄ３の計算は、時系列データ検索装置１の制御演算部１２で行われる。したがって、本実施形態においては、制御演算部１２が、検索対象となる問合せシーケンスＱと記憶部１３に格納されているシーケンスＰの距離の近似値を、ＤＦＴ係数値を用いて計算する第１の近似手段としての機能と、この近似距離が所定の範囲内にある場合には、ＰとＱ各々において近接する要素から順番に要素を結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段としての機能と、検索対象となるシーケンスと前記記憶手段から読み出したシーケンスの距離を、各々のシーケンスに対応するセグメンティッド・シーケンスを用いてシーケンス間の距離の近似値を計算する第２の近似手段としての機能と、この第２の近似手段で求めた近似距離が所定の範囲内にある場合に、ＰとＱの間のダイナミックタイムワーピング距離を求める距離算出手段としての機能とを具備している。
【０１４６】
以上説明した本発明の第３の実施形態によれば、包囲矩形に相当するノードがリーフノードのときには、まず精度はやや劣るが高速に計算可能な離散フーリエ変換による近似で候補を絞った後、速度的にはやや劣るものの精度がよいセグメンティッド・シーケンスによる近似でさらに候補を絞り込むことにより、実際に厳密なダイナミックタイムワーピング距離の計算を行う回数を削減することができ、時系列データのさらに高速な検索が可能となる。
【０１４７】
【実施例】
本発明の一実施例として、第３の実施形態で説明した時系列データ検索方法を用いた場合を例にとり、検索時間を調査し、従来技術１（４次元ベクトルを用いる方法）および従来技術２（ＰＣＡを用いる方法）と比較した結果を示す。
【０１４８】
実験条件は以下の通りである：
・手法の性能を計測するための時系列データは、ランダムウォーク関数を用いて人工的に長さ１０２４のシーケンスデータを、漸化式ｐｉ＝ｐｉ−１＋ｘｉに基づいて１００，０００件作成している。ここで、ｐ０は各々のシーケンスの最初の要素であり、範囲（０，  １０）からランダムに取得している。また、ｘｉは正規分布関数によって取得しており、その正規分布関数の分散は１である。
【０１４９】
・最近傍探索の探索数（ｋ）は２０である。
【０１５０】
・ＣＰＵ時間は、ＳＵＮＵｌｔｒａＳＰＡＲＣ−ＩＩ  ４５０ＭＨｚによって計測した。
【０１５１】
・多次元インデックスとして、Ｒ＊−ｔｒｅｅ（Ｎｏｒｂｅｒｔ  Ｂｅｃｋｍａｎｎ，  Ｈａｎｓ−Ｐｅｔｅｒ  Ｋｒｉｅｇｅｌ，  Ｒａｌｆ  Ｓｃｈｎｅｉｄｅｒ，  ａｎｄ  Ｂｅｒｎｈａｒｄ  Ｓｅｅｇｅｒ，  ”Ｔｈｅ  Ｒ＊−Ｔｒｅｅ：  Ａｎ  Ｅｆｆｉｃｉｅｎｔ  ａｎｄ  Ｒｏｂｕｓｔ  Ａｃｃｅｓｓ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｐｏｉｎｔｓ  ａｎｄ  Ｒｅｃｔａｎｇｌｅｓ”，  Ｐｒｏｃ．  ｏｆ  Ｉｎｔ．  Ｃｏｎｆ．  ｏｎ  ＡＣＭ  ＳＩＧＭＯＤ，  ｐｐ  ３２２−３３１（Ｊｕｎｅ  １９９０）．  を参照）を用いた。
【０１５２】
・データサイズは２５，０００件から１００，０００件まで変化させた。
【０１５３】
・１５次元（ｍ＝５）のＤＦＴ特徴ベクトルＶ（Ｐ）を用いてインデックスを構築し、検索処理の前には１３ペアの下限シーケンスおよび上限シーケンスのＤＦＴ係数をそれぞれ計算した。
【０１５４】
・セグメンティッド・シーケンスの範囲ｒとして、（ｍａｘ（Ｐ）−ｍｉｎ（Ｐ））  ／１４  の値の平均を用いた。
【０１５５】
図１３は、ＣＰＵ時間に関する比較結果を示す図であり、横軸がデータサイズ、縦軸がＣＰＵ時間を表している。本実施例に基づく実験結果は、直線７１で与えられる。
【０１５６】
同図からも明らかなように、従来技術１（直線８１）および２（直線８２）の実験結果は、本発明の一実施例と比較して、同じデータサイズの時系列データの検索に多くのＣＰＵ時間を要していることを示している。具体的には、本発明のデータ検索方法によれば、データ検索時間を従来法よりも最大で１３倍程度軽減できることが分かる。
【０１５７】
【発明の効果】
以上の説明からも明らかなように、本発明によれば、ダイナミックタイムワーピングを用いた時系列データの検索を高速化することのできる時系列データ検索方法、時系列データ検索装置、時系列データ検索プログラム、およびプログラム記録媒体を提供することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る時系列データ検索装置の基本構成を示すブロック図である。
【図２】二つのシーケンスの位置関係を模式的に示す図である。
【図３】Ｄｄｉｓｊｏｉｎｔ（Ｐ，Ｑ）の計算を概念的に示す説明図である。
【図４】本発明の第１の実施形態に係る時系列データ検索方法の処理の流れを示すフローチャート図である。
【図５】本発明の第２の実施形態において近似距離の計算に用いられるセグメンティッド・シーケンスの作成処理のアルゴリズムを示すフローチャート図である。
【図６】セグメンティッド・シーケンスの一例を示す図である。
【図７】セグメンティッド・シーケンスを用いた近似距離計算を概念的に示す説明図である。
【図８】本発明の第２の実施形態に係る時系列データ検索方法の処理の流れを示すフローチャート図である。
【図９】本発明の第３の実施形態において用いられるインデックスを概念的に説明する図である。
【図１０】本発明の第３の実施形態に係る時系列データ検索方法の処理の流れを示すフローチャート図である。
【図１１】図１０の処理Ａの詳細を示すフローチャート図である。
【図１２】図１０の処理Ｂの詳細を示すフローチャート図である。
【図１３】本発明の一実施例の計算結果を示す図である。
【符号の説明】
１  時系列データ検索装置
１１  入力部
１２  制御演算部
１３  記憶部
１４  出力部
５１  インデックス
５３  多次元インデックス
５５  シーケンスファイル
【図１】
2004348594.tif 000021
【図２】
2004348594.tif 000022
【図３】
2004348594.tif 000023
【図４】
2004348594.tif 000024
【図５】
2004348594.tif 000025
【図６】
2004348594.tif 000026
【図７】
2004348594.tif 000027
【図８】
2004348594.tif 000028
【図９】
2004348594.tif 000029
【図１０】
2004348594.tif 000030
【図１１】
2004348594.tif 000031
【図１２】
2004348594.tif 000032
【図１３】
2004348594.tif 000033