(57)【特許請求の範囲】
【請求項１】
入力部、制御演算部、記憶部、出力部を有するコンピュータであり、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データ間の距離をダイナミックタイムワーピングに基づいて求める時系列データ距離算出装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスの距離を、シーケンスの離散フーリエ変換の各成分である係数値を用いて近似する近似手段と、
この近似手段で近似した近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスＱと前記記憶手段から読み出したシーケンスＰのダイナミックタイムワーピング距離を求める距離算出手段とを備え、
前記近似手段は、前記読み出したシーケンスＰの最小値が前記検索対象となるシーケンスＱの最大値以上の場合は次式を用いて距離を近似し（ただし、ｆｋ（Ｐ）は前記係数値、Ｑｕｐｐｅｒは前記検索対象となるシーケンスＱの下限シーケンスを表す）、
【数１９】
0004355824.tif 000020
前記読み出したシーケンスＰの最小値が前記検索対象となるシーケンスＱの最大値よりも小さく、前記読み出したシーケンスＰの最大値が前記検索対象となるシーケンスＱの最小値よりも大きい場合は次式を用いて近似し、
【数２０】
0004355824.tif 000021
前記読み出したシーケンスＰの最大値が前記検索対象となるシーケンスＱの最小値以下の場合は次式を用いて近似する（ただし、Ｑｌｏｗｅｒは検索対象となるシーケンスＱの上限シーケンスを表す）
【数２１】
0004355824.tif 000022
ことを特徴とする時系列データ距離算出装置。
【請求項２】
入力部、制御演算部、記憶部、出力部を有するコンピュータであり、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データ間の距離をダイナミックタイムワーピングに基づいて求める時系列データ距離算出装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを各々のシーケンスに対して作成する作成手段と、
検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する近似手段と、
この近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスＱと前記記憶手段から読み出したシーケンスＰのダイナミックタイムワーピング距離を求める距離算出手段とを備え、
前記近似手段は、次式を用いて距離を近似する
【数２２】
0004355824.tif 000023
ことを特徴とする時系列データ距離算出装置。
【請求項３】
入力部、制御演算部、記憶部、出力部を有するコンピュータであり、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データ間の距離をダイナミックタイムワーピングに基づいて求める時系列データ距離算出装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスの距離を、シーケンスの離散フーリエ変換の各成分である係数値を用いて近似する第１の近似手段と、
この第１の近似手段で近似した近似距離が所定の範囲内にある場合には、近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段と、
検索対象となるシーケンスＱと前記記憶手段から読み出したシーケンスＰの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する第２の近似手段と、
この第２の近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段とを備え、
前記第１の近似手段は、前記読み出したシーケンスＰの最小値が前記検索対象となるシーケンスＱの最大値以上の場合は次式を用いて距離を近似し（ただし、ｆｋ（Ｐ）は前記係数値、Ｑｕｐｐｅｒは前記検索対象となるシーケンスＱの下限シーケンスを表す）、
【数１９】
0004355824.tif 000024
前記読み出したシーケンスＰの最小値が前記検索対象となるシーケンスＱの最大値よりも小さく、前記読み出したシーケンスの最大値が前記検索対象となるシーケンスＱの最小値よりも大きい場合は次式を用いて近似し、
【数２０】
0004355824.tif 000025
前記読み出したシーケンスＰの最大値が前記検索対象となるシーケンスＱの最小値以下の場合は次式を用いて近似し（ただし、Ｑｌｏｗｅｒは検索対象となるシーケンスＱの上限シーケンスを表す）、
【数２１】
0004355824.tif 000026
前記第２の近似手段は、次式を用いて距離を近似する
【数２２】
0004355824.tif 000027
ことを特徴とする時系列データ距離算出装置。
【請求項４】
請求項１ないし３のいずれか１項に記載の時系列データ距離算出装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【請求項５】
請求項４に記載のプログラムを記録したことを特徴とする、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベース検索技術に関し、より詳しくは、ダイナミックタイムワーピングに基づいて時系列データを検索する時系列データ検索方法、時系列データ検索装置、時系列データ検索プログラム、およびプログラム記録媒体に関する。
【０００２】
【従来の技術】
時系列データは、時間軸に沿って要素値が定められているシーケンスとして表現される。
【０００３】
このような時系列データを扱う手法として、ダイナミックタイムワーピング（ＤＴＷ：Dynamic Time Warping、時間軸正規化）と呼ばれる手法が知られている。ダイナミックタイムワーピングとは、時間軸に沿ってシーケンスを伸長させ、二つのシーケンスの距離を最小化する変換のことである。
【０００４】
一般に、ユークリッド距離においては、長さやサンプリングレートの異なる時系列データを扱うことが難しいが、ダイナミックタイムワーピングの手法を用いれば、そのような時系列データを比較的容易に扱うことができ、二つのシーケンス間の距離、すなわち類似度をより的確に求めることができる。
【０００５】
ダイナミックタイムワーピング距離について、さらに具体的に説明する。
長さnのシーケンスP＝{p0, p1,・・・, pn-1}と長さmのシーケンスQ＝{q0, q1,・・・, qm-1}が与えられているとき、ダイナミックタイムワーピング距離DDTW(P,Q)は、次式で定義される：
【数１】
0004355824.tif 000002
ここで、gseg(-1, -1)＝0であり、さらに、任意の整数i, jに対してgseg(i,-1)＝gseg(-1,j)＝∞である。また、式（２）の右辺第２項は、gseg(i-1, j)、gseg(i, j-1)、gseg(i-1, j-1)のうちの最小値を意味する。さらに、式（３）の右辺のαの値は任意であるが、以後の説明においては、便宜上α＝２であるとする。
【０００６】
二つのシーケンスPとQの距離は、各シーケンスの要素を昇順にマッチングすることによって得られる。すなわち、ダイナミックタイムワーピングでは、二つのシーケンスの長さが異なっていても、シーケンス間の距離を定義することができる。このようなダイナミックタイムワーピングは、ダイナミックプログラミングと呼ばれるアルゴリズムにしたがって計算され、その計算コストは、およそO(nm)のオーダーであることが知られている。したがって、シーケンス長が長くなると、非常に多くの計算コストが必要となる。
【０００７】
従来、この計算コストを低減するためのさまざまな技術が開示されている。
【０００８】
このうち、非特許文献１に開示されている技術（以後、この技術を従来技術１と呼ぶ）は、ダイナミックタイムワーピングに基づく二つのシーケンス間の距離であるダイナミックタイムワーピング距離を近似し、時系列データの検索を高速化するための手法である。この手法では、シーケンスをなす要素から、（時間的に最初の要素値、時間的に最後の要素値、要素の最小値、要素の最大値）を抽出し、これら４つの要素から成る４次元ベクトルを作成し、この４次元ベクトル間のユークリッド距離をシーケンス間の距離の近似値として採用する。この近似値は、ダイナミックタイムワーピングの下限距離（厳密な距離と等しいか、または下回る値をとる）を示しており、このような近似値を用いることによって、探索漏れを発生させずに、ダイナミックタイムワーピングによる厳密な距離計算回数の削減を図っている。
【０００９】
また、非特許文献２に開示されている技術（以後、この技術を従来技術２と呼ぶ）では、シーケンスを等間隔に分割してサブシーケンスを作成し、このサブシーケンスのうちの最大値と最小値を計算し、そのユークリッド距離を、ダイナミックタイムワーピングの近似値としている。ちなみにこの手法は、ＰＣＡ（Piecewise Constant Approximation）と呼ばれている。
【００１０】
【非特許文献１】
Sang-Wook Kim, Sanghyaun Park, and Wesley W. Chu, "An Index-based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases", in Proceedings of ICDE, pp. 607-614 (April 2001).
【００１１】
【非特許文献２】
Eamonn J. Keogh, "Exact Indexing of Dynamic Time Warping", in Proceedings of VLDB, pp. 406-417 (August 2002).
【００１２】
【発明が解決しようとする課題】
しかしながら、上述した従来技術１の場合、近似値を求めるために採用する４次元ベクトルは、時系列データ全体に対して要素数が少ないため、近似値の精度が低く、ダイナミックタイムワーピング距離の計算回数を十分に削減することができないという問題があった。
【００１３】
また、従来技術２の場合にも、従来技術１と同様の問題、すなわち、近似値の精度が低く、ダイナミックタイムワーピング距離の計算回数を十分に削減できないという問題があった。
【００１４】
本発明はこのような事情に鑑みてなされたものであり、その目的は、ダイナミックタイムワーピングを用いた時系列データの検索を高速化することのできる時系列データ検索方法、時系列データ検索装置、時系列データ検索プログラム、およびプログラム記録媒体を提供することにある。
【００１５】
【課題を解決するための手段】
上記目的を達成するために、本願発明では以下の手段を講じた。
【００２１】
請求項１記載の発明は、入力部、制御演算部、記憶部、出力部を有するコンピュータであり、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データ間の距離をダイナミックタイムワーピングに基づいて求める時系列データ距離算出装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスの距離を、シーケンスの離散フーリエ変換の各成分である係数値を用いて近似する近似手段と、
この近似手段で近似した近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスＱと前記記憶手段から読み出したシーケンスＰのダイナミックタイムワーピング距離を求める距離算出手段とを備えたことを要旨とする。
【００２２】
請求項２記載の発明は、入力部、制御演算部、記憶部、出力部を有するコンピュータであり、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データ間の距離をダイナミックタイムワーピングに基づいて求める時系列データ距離算出装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを各々のシーケンスに対して作成する作成手段と、
検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する近似手段と、
この近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスＱと前記記憶手段から読み出したシーケンスＰのダイナミックタイムワーピング距離を求める距離算出手段とを備えたことを要旨とする。
【００２３】
請求項３記載の発明は、入力部、制御演算部、記憶部、出力部を有するコンピュータであり、時間軸に沿って要素値が定められているシーケンスとして表現される時系列データ間の距離をダイナミックタイムワーピングに基づいて求める時系列データ距離算出装置であって、
複数のシーケンスを格納して記憶する記憶手段と、
検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスの距離を、シーケンスの離散フーリエ変換の各成分である係数値を用いて近似する第１の近似手段と、
この第１の近似手段で近似した近似距離が所定の範囲内にある場合には、近接する要素から順番に結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段と、
検索対象となるシーケンスＱと前記記憶手段から読み出したシーケンスＰの距離を、前記作成手段で作成した各々のシーケンスに対応するセグメンティッド・シーケンスを用いて近似する第２の近似手段と、
この第２の近似手段で求めた近似距離が所定の範囲内にある場合には、前記検索対象となるシーケンスＱと前記記憶手段で記憶したシーケンスのダイナミックタイムワーピング距離を求める距離算出手段とを備えたことを要旨とする。
【００２４】
請求項４記載の発明は、請求項１ないし３のいずれか１項に記載の時系列データ距離算出装置を構成する各手段としてコンピュータを機能させるためのプログラムであることを要旨とする。
【００２５】
請求項５記載の発明は、請求項４に記載のプログラムを記録したことを要旨とする。
【００２６】
【発明の実施の形態】
以下、添付図面を参照して本発明の実施の形態を説明する。
【００２７】
（第１の実施形態）
図１は、本発明の第１の実施形態に係る時系列データ検索方法を実行するコンピュータシステムである時系列データ検索装置の概略構成を示す機能ブロック図である。同図に示す時系列データ検索装置１は、各種データを入力するためのキーボード、マウス等の入力装置から成る入力部１１、中央処理装置（ＣＰＵ：Central Processing Unit）を備え、後述する各種処理の制御および演算を行う制御演算部１２、入力部１１からの入力情報や制御演算部１２からの演算結果等を格納して記憶する記憶部１３、この記憶部１３で記憶した情報を出力するための（液晶）ディスプレイ画面等の出力装置から成る出力部１４を少なくとも有している。
【００２８】
記憶手段の少なくとも一部をなす記憶部１３は、ＲＡＭ（Random Access Memory）等から構成される主記憶装置と、ハードディスクドライブ、フレキシブルディスクドライブ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）ドライブ、ＤＶＤ（Digital Versatile Disk）ドライブ、光磁気ディスクドライブ、ＰＣカードドライブ等から構成される補助記憶装置とを具備しており、データ検索に必要なシーケンス情報を管理、記憶するデータベースとしての機能を有する。また、後述する計算結果を随時格納するために必要なメモリ領域が確保されている。
【００２９】
なお、本実施形態の各種処理は、一つの電子的な装置が実行する場合だけでなく、各ステップの実行を適宜分割して二つ以上の電子的な装置から構築されたシステムが全体で実行する場合も含まれる。この意味で、本実施形態に係る「時系列データ検索装置」は、一つまたは複数のコンピュータ（システム）によって構成されることはいうまでもない。この点は、本発明の全ての実施の形態に共通する事項である。
【００３０】
次に、以上の構成を有する時系列データ検索装置１が実行する時系列データ検索処理の詳細を説明する。
【００３１】
最初に、ダイナミックタイムワーピング距離の近似方法（距離近似方法）について説明した後、この距離近似方法を用いた時系列データ検索方法について説明する。
【００３２】
＜距離近似方法＞
本実施形態に係る時系列データ検索方法では、ダイナミックタイムワーピング距離DDTWの計算回数をできるだけ削減するために、離散フーリエ変換（ＤＦＴ：Discrete Fourier Transform）を用いて近似距離の計算を行う。
【００３３】
長さnのシーケンスP＝{p0, p1,・・・, pn-1}が与えられているとき、このシーケンスPの離散フーリエ変換F(P)＝{f0(P), f1(P),・・・, fn-1(P)}の各成分（ＤＦＴ係数）は、次式で定義される：
【数２】
0004355824.tif 000003
ここで、k≠0に対して、fn-k(P)はfk(P)の複素共役となる。本実施形態では、シーケンスPの各要素が実数であることを仮定する。このため、f0(P)は式（４）により実数となる。
【００３４】
逆に、離散フーリエ変換F(P)が与えられているとき、シーケンスPの要素は、F(P)に対して逆離散フーリエ変換（ＩＤＦＴ：Inverse Discrete Fourier Transform）
【数３】
0004355824.tif 000004
を施すことによって求めることができる。
【００３５】
以上のように定義される離散フーリエ変換を用いて、検索対象となるシーケンス（問い合わせシーケンスと呼ぶ）Q＝{q0, q1,・・・, qn-1}から任意のシーケンスPまでの距離近似方法を説明する。ここでは、両シーケンスの位置関係に応じて近似距離を求める。なお、以後の説明においては、min(P)およびmin(Q)を、それぞれシーケンスPおよびQの最小値とする一方、max(P)およびmax(Q)を、それぞれシーケンスPおよびQの最大値とする。
【００３６】
二つのシーケンスPとQの位置関係は、図２の概念図に示すように、次の３つの場合がある：
（１）min(P)≧max(Q)  （図２（ａ）：この配置をdisjoint呼ぶ）
（２）min(P)＜max(Q)かつmax(P)＞min(Q)  （図２（ｂ）：この配置をoverlapと呼ぶ）
（３）max(P)≦min(Q)  （図２（ｃ）：この配置をdisjoint(-)と呼ぶ）
以下、これら３つの位置関係の場合について、それぞれ近似距離を計算する。
【００３７】
（１）disjoint
問合せシーケンスQの下限シーケンスQlower＝{ql0, ql1,・・・, qln-1}と上限シーケンスQupper＝{qu0, qu1,・・・, qun-1}を求める。二つのシーケンスの要素は、i＝0, 1, ・・・ , n-1として、それぞれ次のように定義される。
【数４】
0004355824.tif 000005
ここで、min(qui:qui+j)とmax(qui:qui+j)は、部分シーケンス{qi, qi+1,・・・, qi+j}の最小値と最大値をそれぞれ表す。
【００３８】
式（６）および（７）の右辺に出てくるlextは、ダイナミックタイムワーピングによってシーケンスが伸長する場合の最大伸長の値を表す。換言すれば、ダイナミックタイムワーピングによるシーケンスの伸長は、たかだかlextに制限される。このlextは、min(P)≧0かつmin(Q)≧0のとき、
【数５】
0004355824.tif 000006
である。ここで、右辺に用いられている記号[x]は、xの値を超えない最大の整数を意味している。
【００３９】
式（８）の右辺において、
【数６】
0004355824.tif 000007
はシーケンスPとQの２乗ユークリッド距離である。wはダイナミックタイムワーピングの幅であり、特に制限がなければ、w＝n-1である。E(P)とE(Q)は、シーケンスPとQのエネルギーであり、それぞれ次式で与えられる：
【数７】
0004355824.tif 000008
また、δ(P,Q)＝（min(P)−max(Q)）2である。
【００４０】
ここで、min(P)＜min(Q)かつmin(P)＜0のときには、式（１０）のE(P)と式（１１）のE(Q)を、以下のE'(P)とE'(Q)にそれぞれ置き換える。
【数８】
0004355824.tif 000009
【００４１】
また、min(P)＞min(Q)かつmin(Q)＜0のときには、式（１２）および式（１３）のmin(P)をmin(Q)としてlextを求めることができる。
【００４２】
シーケンスPが全てのＤＦＴ係数を用いて展開されている場合には、２乗ユークリッド距離D2Euclid(P,Q)は式（９）で与えられるが、そのＤＦＴ係数のうちの(m+1)個(m≦n-1)のみを用いて展開されている場合には、式（６）において、D2Euclid(P,Q)の代わりに、以下で定義されるDmodified(P,Q)を用いる：
【数９】
0004355824.tif 000010
【００４３】
以上により、disjointの場合のダイナミックタイムワーピング距離DDTW(P,Q)の近似距離は、次のように求められる。
【数１０】
0004355824.tif 000011
【００４４】
図３は、Ddisjoint(P,Q)の計算を概念的に示す説明図である。同図において、問合せシーケンスQは、下限シーケンスQlowerと上限シーケンスQupperに囲まていれる。PとQの位置関係がdisjoint(min(P)≧max(Q))の場合、Qupperを用いて近似距離の計算を行う（式（１５）を参照）。このとき、Ddisjoint(P,Q)は、ダイナミックタイムワーピング距離DDTW(P,Q)を近似しており、なおかつDDTW(P,Q)以下の値をとる。
【００４５】
（２）overlap
図２（ｂ）に示すように、二つのシーケンスPとQの少なくとも一部が重なり合うとき、最大伸長の値は、lext＝wである。上述したQlowerおよびQupperに加えて、
【数１１】
0004355824.tif 000012
を用いることにより、overlapにおける近似距離Doverlap(P,Q)を次のように求めることができる：
【数１２】
0004355824.tif 000013
【００４６】
（３）disjoint(-)
本質的には、上記（１）disjointの場合と同じであり、近似距離
Ddisjoint(-)(P,Q)は、次式で定義される：
【数１３】
0004355824.tif 000014
【００４７】
このdisjoint(-)の場合、式（８）におけるδ(P,Q)＝（min(Q)−max(P)）2であるが、他の量については、上述したdisjointの場合と同じである。
【００４８】
＜時系列データ検索方法＞
時系列データ検索処理を高速化するための特徴量として、本実施形態では離散フーリエ変換に基づいたＤＦＴ特徴ベクトルを用いる。
【００４９】
シーケンスPのＤＦＴ特徴ベクトルV(P)は、次のように定義される：
V(P)＝{F(P), min(P), max(P), Erest(P), γ(P)}      (21)
ここで、Pの離散フーリエ変換F(P)が(m+1)次元であるとすると、このＤＦＴ特徴ベクトルV(P)の次元は2m+5である。
【００５０】
このような多次元データの問合せとして、ここではｋ近傍距離（kは所定の正の整数）以下の近似距離を有するシーケンスを探索するk近傍問合せを採用する。これ以外に、例えば範囲指定問合せを用いても、時系列データ検索のアルゴリズムは本質的に同じである。この点に関しては、後述する実施形態でも同様である。
【００５１】
図４は、本実施形態に係る時系列データ検索方法において、離散フーリエ変換を用いた近傍探索処理の流れを示すフローチャート図である。
【００５２】
まず、問合せシーケンスQを入力してこのシーケンスQのＤＦＴ特徴ベクトルV(Q)を計算するとともに、近傍探索数ｋを入力する（ステップＳ１０１）。
【００５３】
その後、シーケンスを順序付けしてカウントするカウンタiの値を０とする（ステップＳ１０２）。
【００５４】
次に、ループＬ１１を実行する。
【００５５】
ループＬ１１では，まずカウンタiの値を１増加させ（ステップＳ１１１）、記憶部１３からシーケンスPおよびこのシーケンスのＤＦＴ特徴ベクトルV(P)をロードし（ステップＳ１１２）、PとQのＤＦＴ特徴ベクトルを用いた近似距離D1を計算する（ステップＳ１１３）。
【００５６】
このステップでは、近似距離D1として、Ddisjoint(P,Q), Doverlap(P,Q), Ddisjoint(-)(P,Q)のいずれかを計算することになるが、全てのシーケンスに対して近似距離を求める計算を行うと、多くのＣＰＵコストを要することになる。そこで、制御演算部１２では、記憶部１３に格納されているシーケンスにアクセスする前に、問合せシーケンスQにおけるさまざまなシーケンス伸長l1, l2, ・・・ , lhを想定し、これらのh個のシーケンス伸長の上限および下限を用意することもできる。
【００５７】
一例として、Ddisjoint(P,Q)が伸長lextを要求する場合、li≧lextを満足するシーケンス伸長の中で最小のものを選択し、l'extとする：
【数１４】
0004355824.tif 000015
制御演算部１２がDdisjoint(P,Q)を計算する際には、このl'extに関する上限および下限を用いる。他の近似距離についても同様である。
【００５８】
ステップＳ１１３での計算の結果、求めたD1がｋ近傍距離以下であれば（ステップＳ１１４でＹＥＳ）、厳密なダイナミックタイムワーピング距離D3＝DDTW(P,Q)を求める（ステップＳ１１５）。
【００５９】
ステップＳ１１５で求めたD3がｋ近傍距離以下であれば（ステップＳ１１６でＹＥＳ）、シーケンスPのIDと距離D3を記憶部１３の最近傍リストへ格納し、ソートする（ステップＳ１１７）。
【００６０】
ステップＳ１１７が終了後、または、ステップＳ１１４かステップＳ１１６の判断でＮＯの場合には、その時点でのシーケンスの数iが記憶部１３に格納されているシーケンスの数に達するまで(i>=ent)、ステップＳ１１１に戻って処理を繰り返す。すなわち、記憶部１３に格納されているシーケンスの各々に対して、ループＬ１１の処理が繰り返し実行される。
【００６１】
いうまでもなく、このループＬ１１では、最初のk回は常にステップＳ１１４およびステップＳ１１６における判断がＹＥＳとなる。
【００６２】
ループＬ１１が終了後、最近傍リストに格納されている候補シーケンスを最終的な探索結果として出力する（ステップＳ１２１）。
【００６３】
ここで説明した近似距離D1とダイナミックタイムワーピング距離D3の計算は、時系列データ検索装置１の制御演算部１２で行われる。したがって、制御演算部１２が、検索対象となる問合せシーケンスQと記憶部１３に格納されているシーケンスPの距離をＤＦＴ係数値を用いてを用いて近似する近似手段としての機能と、近似距離が所定の範囲内にある場合に、PとQの間のダイナミックタイムワーピング距離を求める距離算出手段としての機能とを具備していることはいうまでもない。
【００６４】
近似距離の計算は、厳密なダイナミックタイムワーピングの距離計算よりも計算コストが低い。したがって、以上説明したように、まず近似距離を計算した上で、この計算した近似距離がその時点での最近傍処理よりも大きければ、厳密な計算をせずに初めから除外することができ、厳密な計算は、最近傍距離よりも小さいものに関してのみ行うことが可能となる。
【００６５】
以上説明した本発明の第１の実施形態によれば、ダイナミックタイムワーピングに基づく時系列データの検索を、検索漏れを発生させずに高速化することが可能となる。
【００６６】
本実施形態における時系列データ検索方法は、時系列データとして表現することができる画像、映像、音声、文書等を対象とする広範囲の時系列データ検索に適用可能である。
【００６７】
なお、本実施形態に係る時系列データ検索処理は、時系列データ検索プログラムがインストールされた所定のコンピュータを用いて実施しても同様の効果を得ることができる。
【００６８】
さらに、そのような時系列データ検索プログラムを記録したコンピュータ読み取り可能なプログラム記録媒体をコンピュータに装着し、そのプログラム記録媒体に格納されているプログラムを読み出すことによって、コンピュータが上述した処理を実行するようにしてもよい。ここで、「コンピュータ読み取り可能な」プログラム記録媒体としては、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、光磁気ディスク、ＰＣカード等を用いることができる。このようなプログラム記録媒体を提供することによって、本実施形態の時系列データ検索プログラムを広く流通させることができるようになる。
【００６９】
これらの時系列データプログラムならびに当該プログラムを記録したプログラム記録媒体については、本発明の全ての実施の形態において同様のことがいえる。
【００７０】
（第１の実施形態の変形例）
本実施形態においては、二つのシーケンスPとQの長さが等しい場合を取り扱ったが、異なる長さのシーケンス長を計算するために、全てのシーケンスの長さが等しくなるように調整することも可能である。
【００７１】
この場合、まず基準長nbaseを決定し、この基準長nbaseよりも長いシーケンス長を縮小する一方で、基準長nbaseよりも短いシーケンス長を伸長する。このような調整を行った後は、二つのシーケンスの長さが見かけ上等しくなるため、第１の実施形態と同じ方法で近似距離を求めることが可能となる。
【００７２】
シーケンス長の調整法をより詳細に説明する。
【００７３】
まず、P（の要素）を用いることにより、Pの下限シーケンスPlowerと上限シーケンスPupperを以下のように計算する：
【数１５】
0004355824.tif 000016
ここで、下限シーケンスPlowerの要素pliと上限シーケンスPupperの要素pui(ともにi=0, 1, … , nbase)は、
【数１６】
0004355824.tif 000017
であり、これらのシーケンス長は、基準長nbaseである。
【００７４】
以上のように計算したPlowerおよびPupperの少なくともいずれか一方を、もとのシーケンスPの代わりに用いることにより、ダイナミックタイムワーピングの近似距離を求める。
【００７５】
問合せシーケンスQについても、その長さを調整する。まず、式（１７）、（１８）と同様にQlowerとQupperを作成する。その後、前述したQlowerから下限シーケンスQ'lower＝{ql'0, ql'1,・・・, ql'n-1}を、Qupperから上限シーケンスQ'upper＝{qu'0, qu'1,・・・, qu'n-1}を計算する。ここで、
【数１７】
0004355824.tif 000018
である。式（２４）および式（２５）の右辺の定義は、それぞれ式（６）および式（７）の右辺の定義と同じである。
【００７６】
ここで、PとQの位置関係がdisjointの場合、lextは、式（８）において、PにPlowerを代入し、QにQupperを代入することによって計算される。また、PとQの位置関係がoverlapの場合、シーケンスの伸長幅はlext＝wである。PとQの位置関係がdisjoint(-)の場合、lextは、式（８）において、PにPupperを代入し、QにQlowerを代入することによって計算される。
【００７７】
ダイナミックタイムワーピングの近似距離は、disjointを計算するためにPlowerとQ'upperを用い、disjoint(-)を計算するためにPupperとQ'lowerを用いる。また、overlapを計算するために、４つの量全てを用いる。
【００７８】
以上の点を除く時系列データ検索方法については、上記第１の実施形態と同じである。
【００７９】
したがって、このような第１の実施形態の変形例においても、上記第１の実施形態と同様の効果を得ることができる。
【００８０】
（第２の実施形態）
本発明の第２の実施形態に係る時系列データ検索方法は、ダイナミックタイムワーピング距離を計算するための近似値の算出に、セグメンティッド・シーケンスを用いることを特徴とする。
【００８１】
本実施形態に係る時系列データ検索装置の基本的な構成は、上記第１の実施形態で説明したものと同様である（図１を参照）。
【００８２】
＜セグメンティッド・シーケンス＞
まず、セグメンティッド・シーケンスについて説明する。
【００８３】
範囲rと長さnのシーケンスPが与えられたとき、セグメンティッド・シーケンスSrは次のように定義される。
【００８４】
Sr＝{s0, s1, ・・・, sns-1}        (26)
si＝{sli, sui, sri}
(ns≦n, 1≦sri≦n，sui−sli≦r)
ここで、sliはセグメンティッド・シーケンスSrの中のセグメントsiの最小値であり、suiはセグメンティッド・シーケンスSrの中のセグメントsiの最大値である。したがって、sui−sliはsiの範囲であり、sui−sli≦rである。また、sriはsiの長さを、nsはSrにおけるセグメントの数を示している。
【００８５】
図５は、セグメンティッド・シーケンスを作成するためのアルゴリズムを示すフローチャート図である。
【００８６】
まず、シーケンスの長さn、範囲r、およびシーケンスPの要素pi(i=0, 1, ・・・，n-1)を入力し（ステップＳ２０１）、カウンタiを０にセットする（ステップＳ２０２）。
【００８７】
次に、ループＬ２１を実行する。
【００８８】
このループＬ２１では、隣接するi番目の要素piと(i+1)番目の要素のpi+1の差|pi-pi+1|（LIST.diffiという関数として定義）をi=n-1まで全て求める（ステップＳ２１１、Ｓ２１２）。
【００８９】
ループＬ２１が終了後、記憶部１３に格納されているデータをLIST.diffiのiの昇順にソートする（ステップＳ２２１）。
【００９０】
その後、カウンタiを０にリセットし（ステップＳ２２２）、ループＬ２３に移行する。
【００９１】
ループＬ２３では、近接するシーケンスの要素のペアを、要素の値の差が小さいものから順番に結合してセグメントにする（ステップＳ２３２）。
【００９２】
そして、近接するセグメントを結合して、より大きなセグメントにする（ステップＳ２３１、Ｓ２３２、Ｓ２３３、Ｓ２３４）。
【００９３】
近接する要素もしくはセグメントの差が、閾値rを超えた時点でループL２３を終了する。
【００９４】
この後、ふたたびセグメントとカウンタを初期値に戻し（ステップＳ２４１）、ループＬ２５に移行する。
【００９５】
ループＬ２５では、最初のセグメントから順に生成されたセグメントの数を数えていく。この処理は、シーケンスの長さnに達するまで処理を続ける（ステップＳ２５１）。
【００９６】
最終的なiの値をnsとして（ステップＳ２６１）、セグメンティッド・シーケンスSrとセグメント数nsを結果として出力する（ステップＳ２６２）。
【００９７】
図６は、このようにして生成されたセグメンティッド・シーケンスSrの例を示す図である。
【００９８】
同図に示すセグメンティッド・シーケンスSrは、３つのセグメントs0, s1, s2から構成されている。これらのセグメントの範囲sui-sli (i=0,1,2)は、所定の範囲（閾値）rよりも小さい。
【００９９】
＜距離近似方法＞
本実施形態に係る時系列データ検索方法は、セグメンティッド・シーケンスを用いることによって近似を行うものである。
【０１００】
セグメント数nsのセグメンティッド・シーケンスS＝{s0, s1, ・・・, sns-1}とセグメント数ntのセグメンティッド・シーケンスT＝{t0, t1, ・・・, tnt-1}が与えられているとき、近似値Dsegment(S,T)は、次の演算によって得られる。
【０１０１】
【数１８】
0004355824.tif 000019
【０１０２】
ここで、gur(-1,-1)＝0であり、さらに、任意の整数i, jに対してglr(i,-1)＝gur(i,-1)＝gul(-1,j)＝gur(-1,j)＝∞であるとする。また、gseg(i,j)の定義式の右辺にあるαの値は任意であるが、少なくとも上述したユークリッド２乗距離におけるαと同じ値でなければならないので、ここではα＝２とするが、これにより、本実施形態が特段の限定を受けるわけでないことは勿論である。ちなみに、gll, glr, gul, gurは、それぞれ各セグメントにおける左下、右下、左上、右上の計算結果である。
【０１０３】
図７は、セグメンティッド・シーケンスを用いて行うシーケンスSとTの近似距離の計算を概念的に示す図である。同図に示す場合には、二つのシーケンスSとTのセグメントの個数が、それぞれns＝3, nt＝5に対応している。したがって、この場合のシーケンス間の距離の近似値Dsegment(S,T)は、Dsegment(S,T)＝gur(2,4)となる。
【０１０４】
＜時系列データ検索方法＞
図８は、時系列データ検索方法においてセグメンティッド・シーケンスを用いた時系列データ検索処理の流れを示すフローチャート図である。なお、ここでの探索処理においても、k近傍問合せを採用する。これ以外に、例えば範囲指定問合せを用いても、時系列データ検索のアルゴリズムは本質的に同じであることは第１の実施形態と同様である。
【０１０５】
まず、問合せシーケンスQを入力して、このQのセグメンティッド・シーケンスを上述した方法に従って計算するとともに、記憶部１３に格納されているシーケンスの数を入力する（ステップＳ３０１）。
【０１０６】
その後、シーケンスを順序付けしてカウントするカウンタiの値を０とする（ステップＳ３０２）。
【０１０７】
次に、ループＬ３１を実行する。
【０１０８】
ループＬ３１では，まずカウンタiの値を１増加させ（ステップＳ３１１）、記憶部１３からシーケンスPのセグメンティッド・シーケンスをロードして（ステップＳ３１２）、PとQのセグメンティッド・シーケンスを用いた近似距離D2＝Dsegment（P,Q)を計算する（ステップＳ３１３）。
【０１０９】
ステップＳ３１３で求めたD2がｋ近傍距離以下であれば（ステップＳ３１４でＹＥＳ）、厳密な距離であるダイナミックタイムワーピング距離D3＝DDTW(P,Q)を求める（ステップＳ３１５）。
【０１１０】
このステップで求めたD3がｋ近傍距離以下であれば（ステップＳ３１６でＹＥＳ）、シーケンスPのIDと距離D3を記憶部１３の最近傍リストへ格納し、ソートする（ステップＳ３１７）。
【０１１１】
ステップＳ３１７が終了後、またはステップＳ３１４かステップＳ３１６の判断でＮＯの場合には、その時点でのシーケンスの数iが記憶部１３に格納されているシーケンスの数に達するまで(i>=ent)、ステップＳ３１１に戻って処理を繰り返す。すなわち、記憶部１３に格納されているシーケンスの各々に対して、ループＬ３１の処理を行う。
【０１１２】
このループＬ３１でも、最初のk回は常にステップＳ３１４およびステップＳ３１６での判断がＹＥＳとなる。
【０１１３】
ループＬ３１が終了後、最近傍リストに格納されている候補シーケンスを最終的な探索結果として出力する（ステップＳ３２１）。
【０１１４】
ここで説明した近似距離D2とダイナミックタイムワーピング距離D3の計算は、時系列データ検索装置１の制御演算部１２で行われる。したがって、本実施形態においては、制御演算部１２が、PとQ各々において近接する要素から順番に要素を結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段としての機能と、PとQの距離の近似値を、各々のシーケンスに対応するセグメンティッド・シーケンスを用いて計算する近似手段としての機能と、その近似距離が所定の範囲内にある場合に、PとQの間のダイナミックタイムワーピング距離を求める距離算出手段としての機能とを具備していることはいうまでもない。
【０１１５】
以上説明した本発明の第２の実施形態によれば、第１の実施形態と同様の効果を得ることができる。
【０１１６】
（第３の実施形態）
本発明の第３の実施形態に係る時系列データ検索方法は、上述した二つの実施形態の距離近似方法（ＤＦＴ，セグメンティッド・シーケンス）を共に利用するものである。
【０１１７】
本実施形態に係る時系列データ検索装置の構成は、図１に示す時系列データ検索装置１と同じである。
【０１１８】
このために、本実施形態においては、インデックスを構成する。図９は、このインデックスを概念的に示すと共に、そのインデックスの構成要素を示す説明図である。同図に示すように、インデックス５１は、多次元インデックス５３とシーケンスファイル５５から構成されている。
【０１１９】
多次元インデックス５３は、ＤＦＴ特徴ベクトルV(P)（式（１５）を参照）と包囲矩形から構成される一方で、シーケンスファイル５５は、シーケンスPとセグメンティッド・シーケンス（式（２０）を参照）から構成される。
【０１２０】
本実施形態では、多次元インデックス５３として、ＤＦＴ特徴ベクトルV(P)を(2m+5)次元空間の点とみなし、これらの点を、予め超矩形面によって包囲することにより形成される包囲矩形が、検索木におけるノードの構造を有している場合を想定し、以後の説明を行う。
【０１２１】
この仮想的な検索木は、最上位層の根ノードから出発して枝が延出し、各ノードが包囲矩形に対応している。根ノード以外のノードのうち、一つの包囲矩形に囲まれた複数の点（すなわち、複数のＤＦＴ特徴ベクトル）を格納したノードををリーフノードと呼ぶことにする。また、ここでは延出する枝の数（レベルの数に対応）が同じ値で終端するような平行木の構造を有する場合を想定するが、これが一例に過ぎないのは勿論である。
【０１２２】
＜時系列データ検索処理＞
図１０、図１１および図１２は、本実施形態に係る時系列データ検索処理の流れを示すフローチャート図である。これらの図においては、多次元インデックスを用いた探索アルゴリズムを示しており、ＤＦＴ特徴ベクトルV(P)を用いた近似距離計算と同様に、ＤＦＴ特徴ベクトルV(P)を包含する包囲矩形と問合せシーケンスQとの近似距離計算についても式（１７）、（１９）、（２０）のいずれかを用いて行う。
【０１２３】
まず、図１０を用いて処理を説明する。
【０１２４】
問合せシーケンスQにおけるh個のペアの下限、上限シーケンスを作成し、それらのＤＦＴ特徴ベクトルV(P)を計算するとともに、制御演算部１２において、キューに根ノードへのポインタ、および距離０を設定する（ステップＳ４０１）。
【０１２５】
次に、ループＬ４１の処理を行う。
【０１２６】
まず、問合せ点（問合せシーケンスQ）から最も近いノードＮをキューから取り出し、Ｎで示されるノード内のエントリ数を入力する（ステップＳ４１１）。
【０１２７】
この後、ノードＮがリーフノードか否かを判定し（ステップＳ４１２）、リーフノード以外のとき（ステップＳ４１２でＮＯ）、図１１に示す処理Ａを実行する。他方、ノードＮがリーフノードのとき（ステップＳ４１３でＹＥＳ）、処理Ｂを実行する（ステップＳ４１５）。処理ＡおよびＢについては、後述する。
【０１２８】
これらの処理を経て、キューが空になるまでループＬ４１を繰り返し実行した後、最近傍リストに格納されている候補シーケンスを探索結果として出力する（ステップＳ４２１）。
【０１２９】
ここで、図１１のフローチャート図を用いて、処理Ａの詳細を説明する。
【０１３０】
まず、カウンタiを初期化して０とし（ステップＡ１）、ループＬＡ１を実行する。ループＬＡ１では、カウンタiの設定後（ステップＡ２）、ノードＮの中でi番目に格納されているＤＦＴ特徴ベクトルを用いて近似距離D1を計算する（ステップＡ３、Ａ４）。近似距離D1として、Ddisjoint(P,Q), Doverlap(P,Q), Ddisjoint(-)(P,Q)のいずれかを計算することはいうまでもない。
【０１３１】
D1がｋ近傍距離以下であれば（ステップＡ５でＹＥＳ）、ノードＮのi番目のエントリに格納されている子ポインタと近似距離D1をキューへ格納する（ステップＡ６）。
【０１３２】
D1がｋ近傍距離より大きい場合（ステップＡ５でＮＯ）、ステップＡ２に戻って処理を繰り返す。
【０１３３】
このようにして、ループＬＡ１では、ノードＮに格納されている全エントリ（全データオブジェクト）に対する計算を行い、ループＬＡ１が終了後、キューの先頭データを削除してデータを前詰めし、近似距離D1の昇順にキュー内のデータをソートする（ステップＡ７）。
【０１３４】
以上の処理が終了後、図１０のフローチャート図に戻って処理を行う。
【０１３５】
次に、図１２のフローチャート図を用いて、Ｎがリーフノードであるときの処理Ｂの詳細を説明する。
【０１３６】
まず、カウンタiを初期化して０とし（ステップＢ１）、ループＬＢ１を実行する。ループＬＡ１では、カウンタiの設定後（ステップＢ２）、ノードＮの中でi番目に格納されているＤＦＴ特徴ベクトルを用いて近似距離D1を計算する（ステップＢ３、Ｂ４）。ここでも、近似距離D1は、Ddisjoint(P,Q), Doverlap(P,Q), Ddisjoint(-)(P,Q)のいずれかである。
【０１３７】
D1がｋ近傍距離以下であれば（ステップＢ４でＹＥＳ）、セグンメンティッド・シーケンスを用いて近似距離D2＝Dsegment(P,Q)を計算する（ステップＢ５）。
【０１３８】
このD2もｋ近傍距離以下であれば（ステップＢ６でＹＥＳ）、厳密なダイナミックタイムワーピング距離D3＝DDTW(P,Q)を計算する（ステップＢ８）。
【０１３９】
ステップＢ８で求めたD3がｋ近傍距離以下であれば（ステップＢ９でＹＥＳ）、シーケンスPのIDと距離D3を記憶部１３の最近傍リストへ格納し、ソートする（ステップＢ１０）。
【０１４０】
ステップＢ１０が終了後、または、ステップＢ５、Ｂ７，Ｂ９のいずれかにおける判断でＮＯの場合には、その時点でのシーケンスの数iが記憶部１３に格納されているシーケンスの数に達するまで(i>=ent)、ステップＢ２に戻って処理を繰り返す。すなわち、記憶部１３に格納されているシーケンスの各々に対して、ループＬＢ１の処理が繰り返し実行される。
【０１４１】
ループＬＢ１が終了後、最近傍リストによるキューのフィルタリングを行い、キューの中でアクセスする必要のないデータを削除する（ステップＢ１１）。
【０１４２】
その後、キューの先頭データを削除してデータを前詰めする（ステップＢ１２）。
【０１４３】
以上の処理が終了後、図１０のフローチャート図に戻って処理を行う。
【０１４４】
なお、本実施形態においても、k近傍問合せの代わりに、範囲問合せを用いても勿論かまわない。
【０１４５】
ここで説明した近似距離D1, D2, ならびにダイナミックタイムワーピング距離D3の計算は、時系列データ検索装置１の制御演算部１２で行われる。したがって、本実施形態においては、制御演算部１２が、検索対象となる問合せシーケンスQと記憶部１３に格納されているシーケンスPの距離の近似値を、ＤＦＴ係数値を用いて計算する第１の近似手段としての機能と、この近似距離が所定の範囲内にある場合には、PとQ各々において近接する要素から順番に要素を結合することによってセグメント化した時系列データであるセグメンティッド・シーケンスを作成する作成手段としての機能と、検索対象となるシーケンスと前記記憶手段から読み出したシーケンスの距離を、各々のシーケンスに対応するセグメンティッド・シーケンスを用いてシーケンス間の距離の近似値を計算する第２の近似手段としての機能と、この第２の近似手段で求めた近似距離が所定の範囲内にある場合に、PとQの間のダイナミックタイムワーピング距離を求める距離算出手段としての機能とを具備している。
【０１４６】
以上説明した本発明の第３の実施形態によれば、包囲矩形に相当するノードがリーフノードのときには、まず精度はやや劣るが高速に計算可能な離散フーリエ変換による近似で候補を絞った後、速度的にはやや劣るものの精度がよいセグメンティッド・シーケンスによる近似でさらに候補を絞り込むことにより、実際に厳密なダイナミックタイムワーピング距離の計算を行う回数を削減することができ、時系列データのさらに高速な検索が可能となる。
【０１４７】
【実施例】
本発明の一実施例として、第３の実施形態で説明した時系列データ検索方法を用いた場合を例にとり、検索時間を調査し、従来技術１（４次元ベクトルを用いる方法）および従来技術２（ＰＣＡを用いる方法）と比較した結果を示す。
【０１４８】
実験条件は以下の通りである：
・手法の性能を計測するための時系列データは、ランダムウォーク関数を用いて人工的に長さ1024のシーケンスデータを、漸化式pi＝pi-1＋xiに基づいて100,000件作成している。ここで、p0は各々のシーケンスの最初の要素であり、範囲(0, 10)からランダムに取得している。また、xiは正規分布関数によって取得しており、その正規分布関数の分散は１である。
【０１４９】
・最近傍探索の探索数(k)は２０である。
【０１５０】
・ＣＰＵ時間は、SUNUltraSPARC-II 450MHzによって計測した。
【０１５１】
・多次元インデックスとして、R*-tree（Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger, "The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles", Proc. of Int. Conf. on ACM SIGMOD, pp 322-331(June 1990). を参照）を用いた。
【０１５２】
・データサイズは25,000件から100,000件まで変化させた。
【０１５３】
・15次元(m=5)のＤＦＴ特徴ベクトルV(P)を用いてインデックスを構築し、検索処理の前には13ペアの下限シーケンスおよび上限シーケンスのＤＦＴ係数をそれぞれ計算した。
【０１５４】
・セグメンティッド・シーケンスの範囲rとして、(max(P)-min(P)) /14 の値の平均を用いた。
【０１５５】
図１３は、ＣＰＵ時間に関する比較結果を示す図であり、横軸がデータサイズ、縦軸がＣＰＵ時間を表している。本実施例に基づく実験結果は、直線７１で与えられる。
【０１５６】
同図からも明らかなように、従来技術１（直線８１）および２（直線８２）の実験結果は、本発明の一実施例と比較して、同じデータサイズの時系列データの検索に多くのＣＰＵ時間を要していることを示している。具体的には、本発明のデータ検索方法によれば、データ検索時間を従来法よりも最大で１３倍程度軽減できることが分かる。
【０１５７】
【発明の効果】
以上の説明からも明らかなように、本発明によれば、ダイナミックタイムワーピングを用いた時系列データの検索を高速化することのできる時系列データ検索方法、時系列データ検索装置、時系列データ検索プログラム、およびプログラム記録媒体を提供することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る時系列データ検索装置の基本構成を示すブロック図である。
【図２】二つのシーケンスの位置関係を模式的に示す図である。
【図３】  Ddisjoint(P,Q)の計算を概念的に示す説明図である。
【図４】本発明の第１の実施形態に係る時系列データ検索方法の処理の流れを示すフローチャート図である。
【図５】本発明の第２の実施形態において近似距離の計算に用いられるセグメンティッド・シーケンスの作成処理のアルゴリズムを示すフローチャート図である。
【図６】セグメンティッド・シーケンスの一例を示す図である。
【図７】セグメンティッド・シーケンスを用いた近似距離計算を概念的に示す説明図である。
【図８】本発明の第２の実施形態に係る時系列データ検索方法の処理の流れを示すフローチャート図である。
【図９】本発明の第３の実施形態において用いられるインデックスを概念的に説明する図である。
【図１０】本発明の第３の実施形態に係る時系列データ検索方法の処理の流れを示すフローチャート図である。
【図１１】図１０の処理Ａの詳細を示すフローチャート図である。
【図１２】図１０の処理Ｂの詳細を示すフローチャート図である。
【図１３】本発明の一実施例の計算結果を示す図である。
【符号の説明】
１  時系列データ検索装置
１１  入力部
１２  制御演算部
１３  記憶部
１４  出力部
５１  インデックス
５３  多次元インデックス
５５  シーケンスファイル
【図１】
0004355824.tif 000028
【図２】
0004355824.tif 000029
【図３】
0004355824.tif 000030
【図４】
0004355824.tif 000031
【図５】
0004355824.tif 000032
【図６】
0004355824.tif 000033
【図７】
0004355824.tif 000034
【図８】
0004355824.tif 000035
【図９】
0004355824.tif 000036
【図１０】
0004355824.tif 000037
【図１１】
0004355824.tif 000038
【図１２】
0004355824.tif 000039
【図１３】
0004355824.tif 000040