(57)【要約】  このデータ検索装置は、被検索対象データ系列中の各データに対応する表であって、対応するデータと検索データとの類似度のとりうる類似度範囲別に、検索データとの類似度が所定の閾値と比較して所定の関係になる可能性の有るデータのうち当該対応するデータ以降で最初に現れるデータを特定するスキップ先データ情報を記録した第１のスキップ対応表と、被検索対象データ系列の中から検索データとの類似度が上記閾値以下のデータを検索する際、検索データとの類似度を計算する必要のある被検索対象データ系列中のデータを、上記第１のスキップ対応表を用いて絞り込む制御手段とを備える。
2010084712.tif 000002
【特許請求の範囲】
【請求項１】
被検索対象データ系列中の各データに対応する表であって、対応するデータと検索データとの類似度のとりうる類似度範囲別に、検索データとの類似度が所定の閾値と比較して所定の関係になる可能性の有るデータのうち当該対応するデータ以降で最初に現れるデータを特定するスキップ先データ情報を記録した第１のスキップ対応表と、
被検索対象データ系列の中から検索データとの類似度が前記閾値以下のデータを検索する際、検索データとの類似度を計算する必要のある被検索対象データ系列中のデータを、前記第１のスキップ対応表を用いて絞り込む制御手段とを備えることを特徴とするデータ検索装置。
【請求項２】
前記所定の関係とは、検索データとの類似度が前記閾値以下になる関係である
ことを特徴とする請求項１に記載のデータ検索装置。
【請求項３】
前記制御手段は、被検索対象データ系列中の或るデータについて計算した検索データとの類似度が前記閾値以下でなかった場合に、当該計算された類似度と前記或るデータに対応する第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定することを特徴とする請求項２に記載のデータ検索装置。
【請求項４】
前記制御手段は、前記或るデータと検索データとの類似度を含む類似度範囲が前記第１のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定することを特徴とする請求項３に記載のデータ検索装置。
【請求項５】
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第１のスキップ対応表を生成する第１のスキップ対応表生成手段を備えることを特徴とする請求項２乃至４の何れか１項に記載のデータ検索装置。
【請求項６】
前記第１のスキップ対応表生成手段は、前記第１のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値以下になる可能性が無い、生成対象データと検索データとの類似度の下限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の下限の最大値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第１のスキップ対応表を生成することを特徴とする請求項５に記載のデータ検索装置。
【請求項７】
前記所定の関係とは、検索データとの類似度が前記閾値より大きくなる関係である
ことを特徴とする請求項１に記載のデータ検索装置。
【請求項８】
前記制御手段は、被検索対象データ系列中の或るデータについて計算した検索データと
の類似度が前記閾値以下であった場合に、当該計算された類似度と前記或るデータに対応する第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定することを特徴とする請求項７に記載のデータ検索装置。
【請求項９】
前記制御手段は、前記或るデータと検索データとの類似度を含む類似度範囲が前記第１のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定することを特徴とする請求項８に記載のデータ検索装置。
【請求項１０】
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第１のスキップ対応表を生成する第１のスキップ対応表生成手段を備えることを特徴とする請求項７乃至９の何れか１項に記載のデータ検索装置。
【請求項１１】
前記第１のスキップ対応表生成手段は、前記第１のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値より大きくなる可能性が無い、生成対象データと検索データとの類似度の上限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の上限の最小値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第１のスキップ対応表を生成することを特徴とする請求項１０に記載のデータ検索装置。
【請求項１２】
前記第１のスキップ対応表生成手段は、前記生成した第１のスキップ対応表の連続する複数の類似度範囲を１つの類似度範囲に統合し、統合後の類似度範囲に対応するスキップ先データとして、統合前の類似度範囲に対応するスキップ先データのうちの最も先行するデータを割り当てることを特徴とする請求項６または１１に記載のデータ検索装置。
【請求項１３】
前記第１のスキップ対応表生成手段は、被検索対象データ系列中のうちの一部のデータについてのみ、前記第１のスキップ対応表を作成することを特徴とする請求項４、５、６、１０、１１、または１２に記載のデータ検索装置。
【請求項１４】
被検索対象データ系列中の各データに対応する表であって、対応するデータと検索データとの類似度のとりうる類似度範囲別に、検索データとの類似度が前記閾値との関係で前記所定の関係にならない可能性の有るデータのうち当該対応するデータ以降で最初に現れるデータを特定するスキップ先データ情報を記録した第２のスキップ対応表を備え、
前記制御手段は、検索データとの類似度を計算する必要のある被検索対象データ系列中のデータを、前記第１および第２のスキップ対応表を用いて絞り込む
ことを特徴とする請求項２記載のデータ検索装置。
【請求項１５】
前記制御手段は、
被検索対象データ系列中の或るデータについて計算した検索データとの類似度が前記閾値以下でなかった場合に、当該計算された類似度と前記或るデータに対応する第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定し、
被検索対象データ系列中の或るデータについて計算した検索データとの類似度が前記閾値以下であった場合に、当該計算された類似度と前記或るデータに対応する第２のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定することを特徴とする請求項１４に記載のデータ検索装置。
【請求項１６】
前記制御手段は、
前記或るデータと検索データとの類似度を含む類似度範囲が前記第１のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定し、
前記或るデータと検索データとの類似度を含む類似度範囲が前記第２のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定することを特徴とする請求項１５に記載のデータ検索装置。
【請求項１７】
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第１のスキップ対応表を生成する第１のスキップ対応表生成手段と、
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第２のスキップ対応表を生成する第２のスキップ対応表生成手段を備えることを特徴とする請求項１４乃至１６の何れか１項に記載のデータ検索装置。
【請求項１８】
前記第１のスキップ対応表生成手段は、前記第１のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値以下になる可能性が無い、生成対象データと検索データとの類似度の下限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の下限の最大値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第１のスキップ対応表を生成し、
前記第２のスキップ対応表生成手段は、前記第２のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値よりも大きくなる可能性が無い、生成対象データと検索データとの類似度の上限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の上限の最小値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第２のスキップ対応表を生成することを特徴とする請求項１７に記載のデータ検索装置。
【請求項１９】
前記第１のスキップ対応表生成手段は、前記生成した第１のスキップ対応表の連続する複数の類似度範囲を１つの類似度範囲に統合し、統合後の類似度範囲に対応するスキップ先データとして、統合前の類似度範囲に対応するスキップ先データのうちの最も先行するデータを割り当て、
前記第２のスキップ対応表生成手段は、前記生成した第２のスキップ対応表の連続する複数の類似度範囲を１つの類似度範囲に統合し、統合後の類似度範囲に対応するスキップ先データとして、統合前の類似度範囲に対応するスキップ先データのうちの最も先行するデータを割り当てることを特徴とする請求項１８に記載のデータ検索装置。
【請求項２０】
前記第１のスキップ対応表生成手段は、被検索対象データ系列中のうちの一部のデータについてのみ、前記第１のスキップ対応表を作成し、
前記第２のスキップ対応表生成手段は、被検索対象データ系列中のうちの一部のデータについてのみ、前記第２のスキップ対応表を作成することを特徴とする請求項１７乃至１９の何れか１項に記載のデータ検索装置。
【請求項２１】
前記データは、特徴ベクトルであり、
前記類似度は、特徴ベクトルどうしの距離である
ことを特徴とする請求項１乃至２０の何れか１項に記載のデータ検索装置。
【請求項２２】
被検索対象データ系列中の各データに対応する表であって、対応するデータと検索データとの類似度のとりうる類似度範囲別に、検索データとの類似度が所定の閾値と比較して所定の関係になる可能性の有るデータのうち当該対応するデータ以降で最初に現れるデータを特定するスキップ先データ情報を記録した第１のスキップ対応表を用いて、被検索対象データ系列の中から検索データとの類似度が前記閾値以下のデータを検索する際、検索データとの類似度を計算する必要のある被検索対象データ系列中のデータを絞り込む
ことを特徴とするデータ検索方法。
【請求項２３】
前記所定の関係とは、検索データとの類似度が前記閾値以下になる関係である
ことを特徴とする請求項２２に記載のデータ検索方法。
【請求項２４】
前記絞り込みでは、被検索対象データ系列中の或るデータについて計算した検索データとの類似度が前記閾値以下でなかった場合に、当該計算された類似度と前記或るデータに対応する第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定する
ことを特徴とする請求項２３に記載のデータ検索方法。
【請求項２５】
前記絞り込みでは、前記或るデータと検索データとの類似度を含む類似度範囲が前記第１のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定する
ことを特徴とする請求項２４に記載のデータ検索方法。
【請求項２６】
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第１のスキップ対応表を生成する
ことを特徴とする請求項２３乃至２５の何れか１項に記載のデータ検索方法。
【請求項２７】
前記第１のスキップ対応表の生成では、前記第１のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値以下になる可能性が無い、生成対象データと検索データとの類似度の下限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の下限の最大値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第１のスキップ対応表を生成する
ことを特徴とする請求項２６に記載のデータ検索方法。
【請求項２８】
前記所定の関係とは、検索データとの類似度が前記閾値より大きくなる関係である
ことを特徴とする請求項２２に記載のデータ検索方法。
【請求項２９】
前記絞り込みでは、被検索対象データ系列中の或るデータについて計算した検索データとの類似度が前記閾値以下であった場合に、当該計算された類似度と前記或るデータに対応する第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定する
ことを特徴とする請求項２８に記載のデータ検索方法。
【請求項３０】
前記絞り込みでは、前記或るデータと検索データとの類似度を含む類似度範囲が前記第１のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定する
ことを特徴とする請求項２９に記載のデータ検索方法。
【請求項３１】
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第１のスキップ対応表を生成する
ことを特徴とする請求項２８乃至３０の何れか１項に記載のデータ検索方法。
【請求項３２】
前記第１のスキップ対応表の生成では、前記第１のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値より大きくなる可能性が無い、生成対象データと検索データとの類似度の上限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の上限の最小値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第１のスキップ対応表を生成する
ことを特徴とする請求項３１に記載のデータ検索方法。
【請求項３３】
前記第１のスキップ対応表の生成では、前記生成した第１のスキップ対応表の連続する複数の類似度範囲を１つの類似度範囲に統合し、統合後の類似度範囲に対応するスキップ先データとして、統合前の類似度範囲に対応するスキップ先データのうちの最も先行するデータを割り当てる
ことを特徴とする請求項２７または３２に記載のデータ検索方法。
【請求項３４】
前記第１のスキップ対応表の生成では、被検索対象データ系列中のうちの一部のデータについてのみ、前記第１のスキップ対応表を作成することを特徴とする請求項２５、２６、２７、３１、３２、または３３に記載のデータ検索方法。
【請求項３５】
前記絞り込みでは、前記第１のスキップ対応表に加えて、さらに、被検索対象データ系列中の各データに対応する表であって、対応するデータと検索データとの類似度のとりうる類似度範囲別に、検索データとの類似度が前記閾値との関係で前記所定の関係にならない可能性の有るデータのうち当該対応するデータ以降で最初に現れるデータを特定するスキップ先データ情報を記録した第２のスキップ対応表を用いて、検索データとの類似度を計算する必要のある被検索対象データ系列中のデータを絞り込む
ことを特徴とする請求項２３記載のデータ検索方法。
【請求項３６】
前記絞り込みでは、
被検索対象データ系列中の或るデータについて計算した検索データとの類似度が前記閾値以下でなかった場合に、当該計算された類似度と前記或るデータに対応する第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定し、
被検索対象データ系列中の或るデータについて計算した検索データとの類似度が前記閾値以下であった場合に、当該計算された類似度と前記或るデータに対応する第２のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定する
ことを特徴とする請求項３５に記載のデータ検索方法。
【請求項３７】
前記絞り込みでは、
前記或るデータと検索データとの類似度を含む類似度範囲が前記第１のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定し、
前記或るデータと検索データとの類似度を含む類似度範囲が前記第２のスキップ対応表に存在する場合、該存在した類似度範囲に対応して記録されたスキップ先データ情報が示すデータを、検索データとの類似度を次に計算する被検索対象データ系列中のデータとして決定する
ことを特徴とする請求項３６に記載のデータ検索方法。
【請求項３８】
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第１のスキップ対応表を生成し、
前記被検索対象データ系列を入力し、前記被検索対象データ系列中のデータ毎の前記第２のスキップ対応表を生成する
ことを特徴とする請求項３５乃至３７の何れか１項に記載のデータ検索方法。
【請求項３９】
前記第１のスキップ対応表の生成では、前記第１のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値以下になる可能性が無い、生成対象データと検索データとの類似度の下限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の下限の最大値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第１のスキップ対応表を生成し、
前記第２のスキップ対応表の生成では、前記第２のスキップ対応表の生成対象データの後続データについて、生成対象データとの類似度を計算し、該類似度と前記閾値とから、当該後続データと検索データとの類似度が前記閾値よりも大きくなる可能性が無い、生成対象データと検索データとの類似度の上限を示すスキップ可能条件を求め、自データおよび自データより先行する後続データのスキップ可能条件で与えられる類似度の上限の最小値を示す連続スキップ可能条件を計算し、前記計算した連続スキップ可能条件に従って、生成対象データの第２のスキップ対応表を生成する
ことを特徴とする請求項３８に記載のデータ検索方法。
【請求項４０】
前記第１のスキップ対応表の生成では、前記生成した第１のスキップ対応表の連続する複数の類似度範囲を１つの類似度範囲に統合し、統合後の類似度範囲に対応するスキップ先データとして、統合前の類似度範囲に対応するスキップ先データのうちの最も先行するデータを割り当て、
前記第２のスキップ対応表の生成では、前記生成した第２のスキップ対応表の連続する複数の類似度範囲を１つの類似度範囲に統合し、統合後の類似度範囲に対応するスキップ先データとして、統合前の類似度範囲に対応するスキップ先データのうちの最も先行するデータを割り当てることを特徴とする請求項３９に記載のデータ検索方法。
【請求項４１】
前記第１のスキップ対応表の生成では、被検索対象データ系列中のうちの一部のデータについてのみ、前記第１のスキップ対応表を作成し、
前記第２のスキップ対応表の生成では、被検索対象データ系列中のうちの一部のデータについてのみ、前記第２のスキップ対応表を作成することを特徴とする請求項３８乃至４０の何れか１項に記載のデータ検索方法。
【請求項４２】
前記データは、特徴ベクトルであり、
前記類似度は、特徴ベクトルどうしの距離である
ことを特徴とする請求項２２乃至４１の何れか１項に記載のデータ検索方法。
【請求項４３】
コンピュータに、
被検索対象データ系列中の各データに対応する表であって、対応するデータと検索データとの類似度のとりうる類似度範囲別に、検索データとの類似度が所定の閾値と比較して前記所定の関係になる可能性の有るデータのうち当該対応するデータ以降で最初に現れるデータを特定するスキップ先データ情報を記録した第１のスキップ対応表を用いて、被検索対象データ系列の中から検索データとの類似度が前記閾値以下のデータを検索する際、検索データとの類似度を計算する必要のある被検索対象データ系列中のデータを絞り込む処理
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ検索装置に関し、特に被検索対象データ系列の中から、検索データと類似するデータを検索するデータ検索装置に関する。
【背景技術】
【０００２】
記憶装置に蓄積された映像データや音響データなどの被検索対象データ系列の中から、検索データと類似するデータを検索する典型的な方法は、検索データと被検索対象データ系列中の全てのデータとの類似度を計算して、閾値と比較する方法である。しかし、一般にデータ間の類似度の計算量は多いため、被検索対象データ系列中の全てのデータと検索対象データとの類似度を計算しなければならない上記の方法では、検索に長時間を必要とする。このため、この種の検索の高速化手法が幾つか提案されている。【０００３】
例えば特許文献１の背景技術の欄には、類似度が或る閾値を超えた場合に類似度計算を途中で打ち切ることで検索を高速に行う手法が記載されている。また、特許文献１では、データ系列の或る部分と別の１つまたは複数の部分との類似度を自己類似度表として計算しておき、この自己類似度表を用いて検索を高速に行う手法を提案している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−６２５５５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
被検索対象データ系列を、図１７（ａ）に示すように、ｙj，ｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，…から構成されるデータの系列とする。この場合、例えば先頭のデータｙjの自己類似度表は、図１７（ｂ）に示すように、データｙjとデータｙj+1との類似度ｄ（ｙj，ｙj+1）、データｙjとデータｙj+2との類似度ｄ（ｙj，ｙj+2）、データｙjとデータｙj+3との類似度ｄ（ｙj，ｙj+3）、データｙjとデータｙj+4との類似度ｄ（ｙj，ｙj+4）、データｙjとデータｙj+5との類似度ｄ（ｙj，ｙj+5）、…を記録した表になる。ここで、類似度の数値は０以上の正の値を取り、値が小さいほど、より類似しているものとする。【０００６】
今、検索データｘiとの類似度が閾値ｔｈ以下のデータを被検索対象データ系列から検索する場合、自己類似度表を用いる検索は以下のような手順となる。【０００７】
まず、検索データｘiとデータｙjとの類似度を計算する。この計算された類似度をＤ（ｘi，ｙj）とすると、以下の式１を用いて、データｙjが検索データｘiの類似データか、非類似データかを判定する。すなわち、類似度Ｄ（ｘi，ｙj）が閾値ｔｈ以下であれば、データｙjは類似データとして出力され、閾値ｔｈより大きければ、データｙjは非類似データと見做される。
［式１］
Ｄ（ｘi，ｙj）≦ｔｈ【０００８】
データｙjを非類似データと見做した場合、検索データｘiとの類似度計算を行う次のデータを以下のようにして決定する。まず、データｙjとその直後のデータｙj+1との類似度ｄ（ｙj，ｙj+1）をデータｙjの自己類似度表から取得し、類似度Ｄ（ｘi，ｙj）から減算する。次に、この減算結果Ｄ（ｘi，ｙj）−ｄ（ｙj，ｙj+1）と閾値ｔｈとを比較し、Ｄ（ｘi，ｙj）−ｄ（ｙj，ｙj+1）≦ｔｈならば、データｙj+1を、検索データｘiとの類似度計算を次に行うデータとして決定する。他方、Ｄ（ｘi，ｙj）−ｄ（ｙj，ｙj+1）＞ｔｈならば、データｙj+1を類似度計算の対象から除外する。その理由は、データｙj+1と検索データｘiとの類似度を計算したとしても、その計算結果は閾値ｔｈ以下になることは理論的にあり得ないためである。データｙj+1を類似度計算の対象外とした場合、さらに後続のデータについて順番にデータｙj+1と同様の判定を繰り返すことにより、検索データｘiとの類似度計算を次に行うデータを決定する。【０００９】
このように自己類似度表を用いることで、検索データｘiとの類似度を計算する必要のあるデータ数を削減することができ、その分だけ高速な検索が可能になる。【００１０】
しかしながら、類似度計算を行うデータが決まるまで、データｙjの後続のデータ１つ１つについて順番に、類似度の減算と閾値判定の処理が必要であり、これが更なる高速化の障害となる。【００１１】
本発明の目的は、被検索対象データ系列の中から、検索データとの類似度が所定の閾値以下のデータを高速に検索することのできるデータ検索装置を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の一形態にかかるデータ検索装置は、被検索対象データ系列中の各データに対応する表であって、対応するデータと検索データとの類似度のとりうる類似度範囲別に、検索データとの類似度が所定の閾値と比較して所定の関係になる可能性の有るデータのうち当該対応するデータ以降で最初に現れるデータを特定するスキップ先データ情報を記録した第１のスキップ対応表と、被検索対象データ系列の中から検索データとの類似度が上記閾値以下のデータを検索する際、検索データとの類似度を計算する必要のある被検索対象データ系列中のデータを、上記第１のスキップ対応表を用いて絞り込む制御手段とを備える。
【発明の効果】
【００１３】
本発明によれば、被検索対象データ系列の中から、検索データとの類似度が所定の閾値以下のデータを高速に検索することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の第１の実施の形態のブロック図である。
【図２】本発明の第１の実施の形態における第１のスキップ対応表生成部の処理例を示すフローチャートである。
【図３】被検索対象データ系列の一例と本発明の第１の実施の形態における第１のスキップ対応表生成部が使用する内部テーブルの構成例を示す図である。
【図４】本発明の第１の実施の形態における第１のスキップ対応表生成部が使用する内部テーブルの具体例を示す図である。
【図５】本発明の第１の実施の形態における第１のスキップ対応表の具体例を示す図である。
【図６】本発明の第１の実施の形態における第１のスキップ対応表の別の具体例を示す図である。
【図７】本発明の第１の実施の形態における制御部の処理例を示すフローチャートである。
【図８】本発明の第２の実施の形態のブロック図である。
【図９】本発明の第２の実施の形態における第２のスキップ対応表生成部の処理例を示すフローチャートである。
【図１０】被検索対象データ系列の一例と本発明の第２の実施の形態における第２のスキップ対応表生成部が使用する内部テーブルの構成例を示す図である。
【図１１】本発明の第２の実施の形態における第２のスキップ対応表生成部が使用する内部テーブルの具体例を示す図である。
【図１２】本発明の第２の実施の形態における第２のスキップ対応表の具体例を示す図である。
【図１３】本発明の第２の実施の形態における第２のスキップ対応表の別の具体例を示す図である。
【図１４】本発明の第２の実施の形態における制御部の処理例を示すフローチャートである。
【図１５】本発明の第３の実施の形態のブロック図である。
【図１６】本発明の第３の実施の形態における制御部の処理例を示すフローチャートである。
【図１７】自己類似度表の一例を示す図である。
【発明を実施するための形態】
【００１５】
［第１の実施の形態］
図１を参照すると、本発明の第１の実施の形態に係るデータ検索装置１００は、類似度計算部１１０と、制御部１２０と、第１のスキップ対応表生成部１３０と、被検索対象データ系列記憶部１４０と、第１のスキップ対応表記憶部１５０とから構成されている。
【００１６】
被検索対象データ系列記憶部１４０は、１以上の被検索対象データ系列を記憶する。１つの被検索対象データ系列は、複数のデータの列で構成される。データ検索装置１００が例えば動画像検索装置である場合、被検索対象データ系列は動画像の連続するフレーム画像あるいはフレーム画像の特徴ベクトルを時間順に並べた時系列信号に相当し、１つのデータが１フレーム画像あるいはその特徴ベクトルに相当する。本発明のデータ検索装置は動画像検索に限定されず、音響検索など他の種類の検索にも広く適用できる。しかし、以降では、説明の便宜上、被検索対象データ系列は、動画像の連続するフレーム画像の特徴ベクトルを時間順に並べた信号として説明を行う。
【００１７】
第１のスキップ対応表生成部１３０は、被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータ毎の第１のスキップ対応表を生成する手段である。ここで、或るデータに対応する第１のスキップ対応表とは、当該データと検索データとの類似度のとりうる範囲別に、検索データとの類似度が予め設定された閾値ｔｈ以下の範囲に存在する可能性のあるデータのうち当該データ以降で最初に現れるデータを特定する情報を記録した表のことである。
【００１８】
第１のスキップ対応表記憶部１５０は、第１のスキップ対応表生成部１３０により生成された第１のスキップ対応表を記憶する手段である。第１のスキップ対応表は、その表がどのデータに対応する表であるかが明確に区別されるように、被検索対象データ系列中のデータと関連付けて、第１のスキップ対応表記憶部１５０に記憶される。
【００１９】
類似度計算部１１０は、検索データと被検索対象データ系列中のデータとの類似度を計算する手段である。検索データもまた、複数のデータの列で構成されるデータ列の中の１データであってもよい。本実施の形態では、被検索対象データ系列中の各データは特徴ベクトルであり、検索データも特徴ベクトルである。類似度計算部１１０は、ベクトルどうしの距離（例えば、ハミング距離、ユークリッド距離、ユークリッド距離の２乗）を類似度として計算する。この場合、類似度は値が０に近いほど、より類似していることを示す。本発明において、類似度の尺度は任意であり、上記以外の計算方法による類似度を計算することも勿論可能である。
【００２０】
制御部１２０は、データ検索装置１００全体の制御を司る手段である。制御部１２０は、データ検索装置１００の外部から検索データが入力されると、類似度計算部１１０を用いて検索データと被検索対象データ系列中のデータとの類似度を計算し、その計算結果の類似度を予め設定された閾値ｔｈと比較することにより、当該データが検索データに類似するデータか否かを判定する。そして、当該データが検索データに類似していれば、検索結果として出力し、当該データの次のデータについて、当該データと同様の処理を繰り返す。他方、制御部１２０は、当該データが検索データに類似していなければ、当該データと検索データとの類似度と当該データの第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定し、この決定したデータについて、当該データと同様の処理を繰り返す。
【００２１】
次に本実施の形態に係るデータ検索装置１００の動作を説明する。
【００２２】
データ検索装置１００の動作は、実際のデータ検索動作の実行に先立って行われる第１のスキップ対応表生成動作と、生成された第１のスキップ対応表を用いたデータ検索動作とに大別される。
【００２３】
（１）第１のスキップ対応表生成動作
第１のスキップ対応表生成部１３０は、被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータ毎に、図２のフローチャートに示す流れに沿って、そのデータに対応する第１のスキップ対応表を生成する。
【００２４】
まず第１のスキップ対応表生成部１３０は、第１のスキップ対応表を生成する被検索対象データ系列中のデータに注目する（ステップＳ１０１）。ここでは、説明の便宜上、被検索対象データ系列を、図３（ａ）に示すように、ｙj，ｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，…から構成されるデータ（本例ではｎ次元の特徴ベクトル）の系列とし、先頭のデータｙjに注目したものとする。
【００２５】
次に第１のスキップ対応表生成部１３０は、注目中データｙjとその後続のｍ個のデータｙj+1，ｙj+2，…，ｙj+mとの類似度ｄ（ｙj，ｙj+1），ｄ（ｙj，ｙj+2），…，ｄ（ｙj，ｙj+m）を計算し、計算結果を内部テーブルに保存する（ステップＳ１０２）。類似度の計算を行う後続データの数ｍは任意である。後続データ数ｍが多ければ、検索データと類似度計算するデータ数をより多く削減できる可能性があるが、スキップ対応表に必要な記憶容量は増大する。このため、両者を勘案してｍの値を事前に決めておく。
【００２６】
第１のスキップ対応表生成部１３０が第１のスキップ対応表を生成する過程で使用する内部テーブルの一例を図３（ｂ）に示す。内部テーブルは、最大ｍ個のエントリで構成され、各エントリは、後続データ、類似度、最小値、スキップ可能条件、連続スキップ可能条件の５項目から構成されている。ステップＳ１０２では、第１のスキップ対応表生成部１３０は、内部テーブルの各エントリの後続データの項目に、ｙj+1，ｙj+2，…，ｙj+mを設定し、類似度の項目に、データｙjとの類似度ｄ（ｙj，ｙj+1），ｄ（ｙj，ｙj+2），…，ｄ（ｙj，ｙj+m）を設定する。
【００２７】
次に第１のスキップ対応表生成部１３０は、後続データｙj+1，ｙj+2，…，ｙj+mのそれぞれについて、検索データとデータｙjとの類似度Ｄ（ｘ，ｙj）およびデータｙjと後続データとの類似度を用いて、検索データとの類似度の最小値を計算し、内部テーブルの最小値の項目に設定する（ステップＳ１０３）。例えば、後続データｙj+1の場合、データｙjとの類似度がｄ（ｙj，ｙj+1）、データｙjと検索データとの類似度がＤ（ｘ，ｙj）であるため、検索データと後続データｙj+1の類似度の最小値は、Ｄ（ｘ，ｙj）−ｄ（ｙj，ｙj+1）になる。
【００２８】
次に第１のスキップ対応表生成部１３０は、後続データｙj+1，ｙj+2，…，ｙj+mのそれぞれについて、検索データとの最小値と別途与えられる閾値ｔｈとを用いて、検索データとの類似度が閾値以下になる可能性のない（検索データと類似する可能性のない）、データｙjと検索データとの類似度の範囲の下限を計算し、内部テーブルのスキップ可能条件の項目に設定する（ステップＳ１０４）。例えば、後続データｙj+1の場合、最小値Ｄ（ｘ，ｙj）−ｄ（ｙj，ｙj+1）でさえも、閾値ｔｈより大きければ、前述した式１に照らせば、検索データと類似する可能性はないので、Ｄ（ｘ，ｙj）＞ｔｈ＋ｄ（ｙj，ｙj+1）が、スキップ可能条件となる。
【００２９】
次に第１のスキップ対応表生成部１３０は、後続データｙj+1，ｙj+2，…，ｙj+mのそれぞれについて、自データおよび自データより先行する他の後続データのスキップ可能条件で与えられる類似度の下限の最大値を計算し、内部テーブルの連続スキップ可能条件の項目に設定する（ステップＳ１０５）。
【００３０】
次に第１のスキップ対応表生成部１３０は、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件に従って、注目中データｙjの第１のスキップ対応表を生成し、第１のスキップ対応表記憶部１５０に保存する（ステップＳ１０６）。具体的には、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件で与えられる類似度の下限のうち、１番目に値の小さな下限を下限値、２番目に値の小さな下限を上限値とする第１の類似度範囲を生成し、注目中データｙjと検索データとの類似度がこの第１の類似度範囲を満たす場合のスキップ先データとして、第１の類似度範囲の上限値に等しい連続スキップ可能条件を持つ後続データのうち最も後続のデータを設定する。次に、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件で与えられる類似度の下限のうち、２番目に値の小さな下限を下限値、３番目に値の小さな下限を上限値とする第２の類似度範囲を生成し、注目中データｙjと検索データとの類似度がこの第２の類似度範囲を満たす場合のスキップ先データとして、第２の類似度範囲の上限値に等しい連続スキップ可能条件を持つ後続データのうち最も後続のデータを設定する。以下同様の処理を、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件で与えられる類似度の下限のうちの最大値を、下限値とする類似度範囲を生成するまで繰り返す。
【００３１】
データｙjの第１のスキップ対応表を生成する過程で使用した内部テーブルの具体例を図４に、データｙjの第１のスキップ対応表の具体例を図５に、それぞれ示す。この例では、閾値ｔｈを５０、ｍを１３としている。
【００３２】
例えば図４の内部テーブルの後続データｙj+3のエントリは、データｙjとの類似度が１２、検索データとの類似度の最小値がＤ（ｘ，ｙj）−１２、スキップ可能条件がＤ（ｘ，ｙj）＞６２、連続スキップ可能条件がＤ（ｘ，ｙj）＞６４であることを示している。後続データｙj+3の連続スキップ可能条件が、スキップ可能条件のＤ（ｘ，ｙj）＞６２ではなく、Ｄ（ｘ，ｙj）＞６４になる理由は、自データｙj+3より先行するデータｙj+2のスキップ可能条件がＤ（ｘ，ｙj）＞６４になっているためである。
【００３３】
また、例えば図５のデータｙjの第１のスキップ対応表における１つ目のエントリは、データｙjと検索データとの類似度が６０より大きく６４以下であれば、検索対象データとの類似度を計算する次のデータは、データｙj+2であることを示している。この１つ目のエントリは、図４の内部テーブルにおける後続データｙj+1，ｙj+2の連続スキップ可能条件から生成されたデータである。
【００３４】
さらに、例えば図５のデータｙjの第１のスキップ対応表における２つ目のエントリは、データｙjと検索データとの類似度が６４より大きく６７以下の範囲であれば、検索対象データとの類似度を計算する次のデータは、データｙj+5であることを示している。この２つ目のエントリは、図４の内部テーブルにおける後続データｙj+2〜ｙj+5の連続スキップ可能条件から生成されたデータである。
【００３５】
第１のスキップ対応表生成部１３０は、被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータｙj以外のデータの第１スキップ対応表についても、データｙjと同様の手順で作成する。ただし、被検索対象データ系列の最後尾のデータにはその後続データが存在しないので、第１スキップ対応表は作成されない。また、最後尾のデータを除く全てのデータについて第１のスキップ対応表を作成しておくのではなく、予め指定した一部のデータについてのみ第１のスキップ対応表を作成しておくこともできる。一部のデータの例としては、偶数番目のデータ、奇数番目のデータ、ｐ（＞２）個置き毎のデータなどが考えられる。
【００３６】
また、第１のスキップ対応表生成部１３０は、図２のステップＳ１０６において生成した第１のスキップ対応表の連続する複数のエントリを１つのエントリに統合することにより、第１のスキップ対応表のエントリ数を削減する処理を施しても良い。連続する複数のエントリを統合した１つのエントリは、統合前の複数のエントリにおける類似度の範囲の下限の最小値を下限値とし、それらにおける類似度の範囲の上限の最大値を上限値とする類似度の範囲を持ち、また、統合前の複数のエントリにおけるスキップ先データのうちの最も先行するデータをスキップ先データとして持つ。例えば、図５の第１のスキップ対応表の５番目と６番目のエントリを１つのエントリに統合し、７番目と８番目のエントリと１つのエントリに統合すると、図６に示すような第１のスキップ対応表となる。
【００３７】
このように第１のスキップ対応表の複数のエントリを統合し、エントリ数を削減することにより、スキップ可能な最大幅を犠牲にする（本当はもう少し先までスキップできる）代わりに、第１のスキップ対応表に必要な記憶容量を削減することができる。
【００３８】
また、第１のスキップ対応表の複数のエントリを統合する際には、以下のような処理を行うようにしてもよい。
【００３９】
例えば、第１のスキップ対応表に割り当て可能な記憶容量の上限が設定されている場合に、第１のスキップ対応表の記憶容量が上限より小さくなるまで、エントリの統合によるエントリ数の削減を繰り返すようにしてもよい。
【００４０】
また例えば、複数のエントリを統合する際に、エントリの統合によって犠牲となる（本当はもう少し先までスキップできる）類似度の範囲が小さくなるように、統合するエントリを選択してもよい。具体例で説明すると、例えば図５の５番目と６番目のエントリを１つのエントリに統合すると、６番目のエントリの類似度の範囲である７５＜Ｄ≦７７は犠牲になる（本当はもう少し先までスキップできる）。また、７番目と８番目のエントリを１つのエントリに統合すると、８番目のエントリの類似度の範囲である８０＜Ｄ≦８４は犠牲になる（本当はもう少し先までスキップできる）。この両者を比較すると、前者の方が犠牲となる類似度の範囲が小さいので、統合するエントリを５番目と６番目とする方が、効率がよい。このとき、さらに、犠牲となるフレーム数を考慮したり、類似度の取りうる確率なども考慮してよい。このように、犠牲となる可能性を考慮して、第１のスキップ対応表のエントリを統合してエントリ数を削減することによって、第１のスキップ対応表の単位記憶容量に対する、第１のスキップ対応表による高速化の効率を最大化することができる。
【００４１】
（２）データ検索動作
制御部１２０は、検索データが与えられると、図７のフローチャートに示す流れに沿って、その検索データに類似するデータを被検索対象データ系列から検索する。被検索対象データ系列が複数存在する場合、それぞれの被検索対象データ系列に対して、同じ処理が繰り返される。以下では、或る１つの被検索対象データ系列に注目し、そのデータ系列中から検索データと類似するデータを検索する場合を例に、本実施の形態におけるデータ検索動作を説明する。
【００４２】
制御部１２０は、被検索対象データ系列の先頭から何番目のデータを処理の対象としているかを管理する変数ｊを１に初期設定し（ステップＳ１１１）、１番目のデータと検索データとの類似度を類似度計算部１１０により計算する（ステップＳ１１２）。
【００４３】
１番目のデータと検索データとの類似度が、閾値ｔｈ以下であれば（ステップＳ１１３でＹＥＳ）、１番目のデータを類似データとして出力する（ステップＳ１１４）。そして、変数ｊを＋１して２とし（ステップＳ１１５）、ステップＳ１１９経由でステップＳ１１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００４４】
他方、１番目のデータと検索データとの類似度が、閾値ｔｈより大きければ（ステップＳ１１３でＮＯ）、１番目のデータに対応する第１のスキップ対応表が記憶部１５０に記憶されているか否かを調べる（ステップＳ１１６）。若し、無ければ、変数ｊを＋１して２とし（ステップＳ１１５）、ステップＳ１１９経由でステップＳ１１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００４５】
１番目のデータに対応する第１のスキップ対応表が有れば、１番目のデータと検索データとの類似度を含む類似度範囲がその第１のスキップ対応表に存在するか否かを調べる（ステップＳ１１７）。若し、存在しなければ、変数ｊを＋１して２とし（ステップＳ１１５）、ステップＳ１１９経由でステップＳ１１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００４６】
１番目のデータに対応する第１のスキップ対応表に、１番目のデータと検索データとの類似度を含む類似度範囲が存在すれば、その類似度範囲に対応して記録されているスキップ先データを次に類似度計算するデータに設定して（つまり、変数ｊがスキップ先データを示すように変更して）（ステップＳ１１８）、ステップＳ１１９経由でステップＳ１１２に戻り、スキップ先データについて、１番目のデータと同様の処理を繰り返す。
【００４７】
ステップＳ１１９では、変更後のｊの値が、被検索対象データ系列のデータ数の最大値ｊmaxを超えているか否かを判定し、若し超えていなければ、制御をステップＳ１１２に移し、若し超えていれば、当該被検索対象データ系列に対する検索処理を終了する。
【００４８】
このように本実施の形態によれば、被検索対象データ系列の中から、検索データとの類似度が所定の閾値以下のデータを高速に検索することができる。その理由は、被検索対象データ系列中の或るデータと検索データとの類似度が閾値より大きくなった場合、当該或るデータに対応する第１のスキップ対応表を参照することにより、類似度計算が不要なデータをスキップすることができるためである。
【００４９】
例えば、検索対象データ系列中のデータｙjと検索データとの類似度が７２であった場合、データｙjに対応する図５または図６の第１のスキップ対応表によれば、スキップ先データはｊ＋７である。このため、検索対象データ系列中のデータｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6の６個のデータについては、検索データとの類似度計算は行われないので、その分だけ検索時間が短縮される。また、データｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6のそれぞれについて個別に、検索データとの類似度計算の必要性を判定する必要がないため、その分だけより一層、検索時間の短縮が可能になる。
【００５０】
なお、本実施の形態では、閾値ｔｈは１種類に固定されているが、閾値ｔｈが複数存在するデータ検索装置にも適用可能である。その場合、それぞれの閾値ｔｈに関連付けて、その閾値用の第１のスキップ対応表を生成して記憶しておく。例えば、閾値ｔｈが、５０、６０、７０の３種類ある場合、ｔｈ＝５０の第１のスキップ対応表、ｔｈ＝６０の第１のスキップ対応表、ｔｈ＝７０の第１のスキップ対応表を生成して記憶しておけばよい。
【００５１】
［第２の実施の形態］
図８を参照すると、本発明の第２の実施の形態に係るデータ検索装置２００は、第１の実施の形態に係るデータ検索装置１００と比較して、制御部１２０、第１のスキップ対応表生成部１３０および第１のスキップ対応表記憶部１５０の代わりに、制御部２２０、第２のスキップ対応表生成部２３０および第２のスキップ対応表記憶部２５０を備えている点で相違する。
【００５２】
第２のスキップ対応表生成部２３０は、被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータ毎の第２のスキップ対応表を生成する手段である。ここで、或るデータに対応する第２のスキップ対応表とは、当該データと検索データとの類似度のとりうる範囲別に、検索データとの類似度が予め設定された閾値ｔｈより大きくなる可能性の有るデータのうち当該データ以降で最初に現れるデータを特定する情報を記録した表のことである。
【００５３】
第２のスキップ対応表記憶部２５０は、第２のスキップ対応表生成部２３０により生成された第２のスキップ対応表を記憶する手段である。第２のスキップ対応表は、その表がどのデータに対応する表であるかが明確に区別されるように、被検索対象データ系列中のデータと関連付けて、第２のスキップ対応表記憶部２５０に記憶される。
【００５４】
制御部２２０は、データ検索装置２００全体の制御を司る手段である。制御部２２０は、データ検索装置２００の外部から検索データが入力されると、類似度計算部１１０を用いて検索データと被検索対象データ系列中のデータとの類似度を計算し、その計算結果の類似度を予め設定された閾値ｔｈと比較することにより、当該データが検索データに類似するデータか否かを判定する。そして、当該データが検索データに類似していれば、検索結果として出力し、当該データと検索データとの類似度と当該データの第２のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定する。そして、この決定したデータが、当該データの次のデータでなければ、当該データの次のデータから、前記決定したデータの直前のデータまでを検索データに類似するデータとして出力し、前記決定したデータについて、当該データと同様の処理を繰り返す。他方、制御部１２０は、当該データが検索データに類似していなければ、当該データの次のデータについて、当該データと同様の処理を繰り返す。
【００５５】
次に本実施の形態に係るデータ検索装置２００の動作を説明する。
【００５６】
データ検索装置２００の動作は、実際のデータ検索動作の実行に先立って行われる第２のスキップ対応表生成動作と、生成された第２のスキップ対応表を用いたデータ検索動作とに大別される。
【００５７】
（１）第２のスキップ対応表生成動作
第２のスキップ対応表生成部２３０は、被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータ毎に、図９のフローチャートに示す流れに沿って、そのデータに対応する第２のスキップ対応表を生成する。
【００５８】
まず第２のスキップ対応表生成部２３０は、第２のスキップ対応表を生成する被検索対象データ系列中のデータに注目する（ステップＳ２０１）。ここでは、説明の便宜上、被検索対象データ系列を、図１０（ａ）に示すように、ｙj，ｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，…から構成されるデータ（本例ではｎ次元の特徴ベクトル）の系列とし、先頭のデータｙjに注目したものとする。
【００５９】
次に第２のスキップ対応表生成部２３０は、注目中データｙjとその後続のｍ個のデータｙj+1，ｙj+2，…，ｙj+mとの類似度ｄ（ｙj，ｙj+1），ｄ（ｙj，ｙj+2），…，ｄ（ｙj，ｙj+m）を計算し、計算結果を内部テーブルに保存する（ステップＳ２０２）。類似度の計算を行う後続データの数ｍは任意である。後続データ数ｍが多ければ、検索データと類似度計算するデータ数をより多く削減できる可能性があるが、スキップ対応表に必要な記憶容量は増大する。このため、両者を勘案してｍの値を事前に決めておく。
【００６０】
第２のスキップ対応表生成部２３０が第２のスキップ対応表を生成する過程で使用する内部テーブルの一例を図１０（ｂ）に示す。内部テーブルは、最大ｍ個のエントリで構成され、各エントリは、後続データ、類似度、最大値、スキップ可能条件、連続スキップ可能条件の５項目から構成されている。ステップＳ２０２では、第２のスキップ対応表生成部２３０は、内部テーブルの各エントリの後続データの項目に、ｙj+1，ｙj+2，…，ｙj+mを設定し、類似度の項目に、データｙjとの類似度ｄ（ｙj，ｙj+1），ｄ（ｙj，ｙj+2），…，ｄ（ｙj，ｙj+m）を設定する。
【００６１】
次に第２のスキップ対応表生成部２３０は、後続データｙj+1，ｙj+2，…，ｙj+mのそれぞれについて、検索データとデータｙjとの類似度Ｄ（ｘ，ｙj）およびデータｙjと後続データとの類似度を用いて、検索データとの類似度の最大値を計算し、内部テーブルの最大値の項目に設定する（ステップＳ２０３）。例えば、後続データｙj+1の場合、データｙjとの類似度がｄ（ｙj，ｙj+1）、データｙjと検索データとの類似度がＤ（ｘ，ｙj）であるため、検索データと後続データｙj+1の類似度の最大値は、Ｄ（ｘ，ｙj）＋ｄ（ｙj，ｙj+1）になる。
【００６２】
次に第２のスキップ対応表生成部２３０は、後続データｙj+1，ｙj+2，…，ｙj+mのそれぞれについて、検索データとの最大値と別途与えられる閾値ｔｈとを用いて、検索データとの類似度が閾値より大きくなる可能性の無い（検索データと類似しない可能性の無い）、データｙjと検索データとの類似度の範囲の上限を計算し、内部テーブルのスキップ可能条件の項目に設定する（ステップＳ２０４）。例えば、後続データｙj+1の場合、最大値Ｄ（ｘ，ｙj）＋ｄ（ｙj，ｙj+1）でさえも、閾値ｔｈ以下であれば、検索データと類似しない可能性はないので、Ｄ（ｘ，ｙj）≦ｔｈ−ｄ（ｙj，ｙj+1）が、スキップ可能条件となる。
【００６３】
次に第２のスキップ対応表生成部２３０は、後続データｙj+1，ｙj+2，…，ｙj+mのそれぞれについて、自データおよび自データより先行する他の後続データのスキップ可能条件で与えられる類似度の上限の最小値を計算し、内部テーブルの連続スキップ可能条件の項目に設定する（ステップＳ２０５）。
【００６４】
次に第２のスキップ対応表生成部２３０は、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件に従って、注目中データｙjの第２のスキップ対応表を生成し、第２のスキップ対応表記憶部２５０に保存する（ステップＳ２０６）。具体的には、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件で与えられる類似度の上限のうち、１番目に値の大きな上限を上限値、２番目に値の大きな上限を下限値とする第１の類似度範囲を生成し、注目中データｙjと検索データとの類似度がこの第１の類似度範囲を満たす場合のスキップ先データとして、第１の類似度範囲の下限値に等しい連続スキップ可能条件を持つ後続データのうち最も後続のデータを設定する。次に、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件で与えられる類似度の上限のうち、２番目に値の大きな上限を上限値、３番目に値の大きな上限を下限値とする第２の類似度範囲を生成し、注目中データｙjと検索データとの類似度がこの第２の類似度範囲を満たす場合のスキップ先データとして、第２の類似度範囲の下限値に等しい連続スキップ可能条件を持つ後続データのうち最も後続のデータを設定する。以下同様の処理を、後続データｙj+1，ｙj+2，…，ｙj+mの連続スキップ可能条件で与えられる類似度の上限のうちの最小値を、下限値とする類似度範囲を生成するまで繰り返す。
【００６５】
データｙjの第１のスキップ対応表を生成する過程で使用した内部テーブルの具体例を図１１に、データｙjの第２のスキップ対応表の具体例を図１２に、それぞれ示す。この例では、閾値ｔｈを５０、ｍを１３としている。
【００６６】
例えば図１１の内部テーブルの後続データｙj+3のエントリは、データｙjとの類似度が１２、検索データとの類似度の最大値がＤ（ｘ，ｙj）＋１２、スキップ可能条件がＤ（ｘ，ｙj）≦３８、連続スキップ可能条件がＤ（ｘ，ｙj）≦３６であることを示している。後続データｙj+3の連続スキップ可能条件が、スキップ可能条件のＤ（ｘ，ｙj）≦３８ではなく、Ｄ（ｘ，ｙj）≦３６になる理由は、自データｙj+3より先行するデータｙj+2のスキップ可能条件がＤ（ｘ，ｙj）≦３６になっているためである。
【００６７】
また、例えば図１２のデータｙjの第２のスキップ対応表における１つ目のエントリは、データｙjと検索データとの類似度が３６より大きく４０以下であれば、検索対象データとの類似度を計算する次のデータは、データｙj+2であることを示している。この１つ目のエントリは、図１１の内部テーブルにおける後続データｙj+1，ｙj+2の連続スキップ可能条件から生成されたデータである。
【００６８】
さらに、例えば図１２のデータｙjの第１のスキップ対応表における２つ目のエントリは、データｙjと検索データとの類似度が３３より大きく３６以下の範囲であれば、検索対象データとの類似度を計算する次のデータは、データｙj+5であることを示している。この２つ目のエントリは、図１１の内部テーブルにおける後続データｙj+2〜ｙj+5の連続スキップ可能条件から生成されたデータである。
【００６９】
第２のスキップ対応表生成部２３０は、被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータｙj以外のデータの第２スキップ対応表についても、データｙjと同様の手順で作成する。ただし、被検索対象データ系列の最後尾のデータにはその後続データが存在しないので、第２スキップ対応表は作成されない。また、最後尾のデータを除く全てのデータについて第２のスキップ対応表を作成しておくのではなく、予め指定した一部のデータについてのみ第２のスキップ対応表を作成しておくこともできる。一部のデータの例としては、偶数番目のデータ、奇数番目のデータ、ｐ（＞２）個置き毎のデータなどが考えられる。
【００７０】
また、第２のスキップ対応表生成部２３０は、図９のステップＳ２０６において生成した第２のスキップ対応表の連続する複数のエントリを１つのエントリに統合することにより、第２のスキップ対応表のエントリ数を削減する処理を施しても良い。連続する複数のエントリを統合した１つのエントリは、統合前の複数のエントリにおける類似度の範囲の下限の最小値を下限値とし、それらにおける類似度の範囲の上限の最大値を上限値とする類似度の範囲を持ち、また、統合前の複数のエントリにおけるスキップ先データのうちの最も先行するデータをスキップ先データとして持つ。例えば、図１２の第２のスキップ対応表の５番目と６番目のエントリを１つのエントリに統合し、７番目と８番目のエントリと１つのエントリに統合すると、図１３に示すような第１のスキップ対応表となる。
【００７１】
このように第２のスキップ対応表の複数のエントリを統合し、エントリ数を削減することにより、スキップ可能な最大幅を犠牲にする（本当はもう少し先までスキップできる）代わりに、第２のスキップ対応表に必要な記憶容量を削減することができる。
【００７２】
また、第２のスキップ対応表の複数のエントリを統合する際には、以下のような処理を行うようにしてもよい。
【００７３】
例えば、第２のスキップ対応表に割り当て可能な記憶容量の上限が設定されている場合に、第２のスキップ対応表の記憶容量が上限より小さくなるまで、エントリの統合によるエントリ数の削減を繰り返すようにしてもよい。
【００７４】
また例えば、複数のエントリを統合する際に、エントリの統合によって犠牲となる（本当はもう少し先までスキップできる）類似度の範囲が小さくなるように、統合するエントリを選択してもよい。具体例で説明すると、例えば図１２の５番目と６番目のエントリを１つのエントリに統合すると、６番目のエントリの類似度の範囲である２３＜Ｄ≦２５は犠牲になる（本当はもう少し先までスキップできる）。また、７番目と８番目のエントリを１つのエントリに統合すると、８番目のエントリの類似度の範囲である１６＜Ｄ≦２０は犠牲になる（本当はもう少し先までスキップできる）。この両者を比較すると、前者の方が犠牲となる類似度の範囲が小さいので、統合するエントリを５番目と６番目とする方がよい。このとき、さらに、犠牲となるフレーム数を考慮したり、類似度の取りうる確率なども考慮してよい。このように、犠牲となる可能性を考慮して、第２のスキップ対応表のエントリを統合してエントリ数を削減することによって、第２のスキップ対応表の単位記憶容量に対する、第２のスキップ対応表による高速化の効率を最大化することができる。
【００７５】
（２）データ検索動作
制御部２２０は、検索データが与えられると、図１４のフローチャートに示す流れに沿って、その検索データに類似するデータを被検索対象データ系列から検索する。被検索対象データ系列が複数存在する場合、それぞれの被検索対象データ系列に対して、同じ処理が繰り返される。以下では、或る１つの被検索対象データ系列に注目し、そのデータ系列中から検索データと類似するデータを検索する場合を例に、本実施の形態におけるデータ検索動作を説明する。
【００７６】
制御部２２０は、被検索対象データ系列の先頭から何番目のデータを処理の対象としているかを管理する変数ｊを１に初期設定し（ステップＳ２１１）、１番目のデータと検索データとの類似度を類似度計算部１１０により計算する（ステップＳ２１２）。
【００７７】
１番目のデータと検索データとの類似度が、閾値ｔｈ以下であれば（ステップＳ２１３でＹＥＳ）、１番目のデータを類似データとして出力する（ステップＳ２１５）。続いて、１番目のデータに対応する第２のスキップ対応表が記憶部２５０に記憶されているか否かを調べる（ステップＳ２１６）。若し、無ければ、変数ｊを＋１して２とし（ステップＳ２１４）、ステップＳ２２１経由でステップＳ２１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００７８】
１番目のデータに対応する第２のスキップ対応表が有れば、１番目のデータと検索データとの類似度を含む類似度範囲がその第２のスキップ対応表に存在するか否かを調べる（ステップＳ２１７）。若し、存在しなければ、変数ｊを＋１して２とし（ステップＳ２１４）、ステップＳ２２１経由でステップＳ２１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００７９】
１番目のデータに対応する第２のスキップ対応表に、１番目のデータと検索データとの類似度を含む類似度範囲が存在すれば、その類似度範囲に対応して記録されているスキップ先データが現在処理しているデータの次のデータであるか否かを判定する（ステップＳ２１８）。若し、スキップ先データが現在処理しているデータの次のデータでない場合（つまり、幾つかのデータをスキップする場合）、現在処理しているデータの次のデータからスキップ先データの直前のデータまでを、類似データとして出力する（ステップＳ２１９）。そして、スキップ先データを次に類似度計算するデータに設定して（つまり、変数ｊがスキップ先データを示すように変更して）（ステップＳ２２０）、ステップＳ２２１経由でステップＳ２１２に戻り、スキップ先データについて、１番目のデータと同様の処理を繰り返す。また、スキップ先データが現在処理しているデータの次のデータであれば、ステップＳ２１９を実行せずに、スキップ先データを次に類似度計算するデータに設定して（つまり、変数ｊがスキップ先データを示すように変更して）（ステップＳ２２０）、ステップＳ２２１経由でステップＳ２１２に戻り、スキップ先データについて、１番目のデータと同様の処理を繰り返す。
【００８０】
一方、１番目のデータと検索データとの類似度が、閾値ｔｈより大きければ（ステップＳ２１３でＮＯ）、変数ｊを＋１して２とし（ステップＳ２１４）、ステップＳ２２１経由でステップＳ２１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００８１】
ステップＳ２２１では、変更後のｊの値が、被検索対象データ系列のデータ数の最大値ｊmaxを超えているか否かを判定し、若し超えていなければ、制御をステップＳ１１２に移し、若し超えていれば、当該被検索対象データ系列に対する検索処理を終了する。
【００８２】
このように本実施の形態によれば、被検索対象データ系列の中から、検索データとの類似度が所定の閾値以下のデータを高速に検索することができる。その理由は、被検索対象データ系列中の或るデータと検索データとの類似度が閾値以下になった場合、当該或るデータに対応する第２のスキップ対応表を参照することにより、類似度計算が不要なデータをスキップすることができるためである。
【００８３】
例えば、検索対象データ系列中のデータｙjと検索データとの類似度が２８であった場合、データｙjに対応する図１２または図１３の第２のスキップ対応表によれば、スキップ先データはｊ＋７である。このため、検索対象データ系列中のデータｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6の６個のデータについては、検索データとの類似度計算は行われないので、その分だけ検索時間が短縮される。また、データｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6のそれぞれについて個別に、検索データとの類似度計算の必要性を判定する必要がないため、その分だけより一層、検索時間の短縮が可能になる。
【００８４】
なお、本実施の形態では、閾値ｔｈは１種類に固定されているが、閾値ｔｈが複数存在するデータ検索装置にも適用可能である。その場合、それぞれの閾値ｔｈに関連付けて、その閾値用の第２のスキップ対応表を生成して記憶しておく。例えば、閾値ｔｈが、５０、６０、７０の３種類ある場合、ｔｈ＝５０の第２のスキップ対応表、ｔｈ＝６０の第２のスキップ対応表、ｔｈ＝７０の第２のスキップ対応表を生成して記憶しておけばよい。
【００８５】
［第３の実施の形態］
図１５を参照すると、本発明の第３の実施の形態に係るデータ検索装置３００は、第１の実施の形態に係るデータ検索装置１００と比較して、第２のスキップ対応表生成部２３０と第２のスキップ対応表記憶部２５０とを新たに備え、また、制御部１２０の代わりに制御部３２０を備えている点で相違する。
【００８６】
第２のスキップ対応表生成部２３０は、第２の実施の形態における第２のスキップ対応表生成部２３０と全く同じものであり、被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータ毎の第２のスキップ対応表を生成する手段である。また、第２のスキップ対応表記憶部２５０は、第２の実施の形態における第２のスキップ対応表記憶部２５０と全く同じものであり、第２のスキップ対応表生成部２３０により生成された第２のスキップ対応表を記憶する手段である。
【００８７】
制御部３２０は、データ検索装置２００全体の制御を司る手段である。制御部３２０は、データ検索装置３００の外部から検索データが入力されると、類似度計算部１１０を用いて検索データと被検索対象データ系列中のデータとの類似度を計算し、その計算結果の類似度を予め設定された閾値ｔｈと比較することにより、当該データが検索データに類似するデータか否かを判定する。
【００８８】
制御部３２０は、当該データが検索データに類似していなければ、当該データと検索データとの類似度と当該データの第１のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定し、この決定したデータについて、当該データと同様の処理を繰り返す。
【００８９】
また制御部３２０は、当該データが検索データに類似していれば、検索結果として出力し、当該データと検索データとの類似度と当該データの第２のスキップ対応表とから、検索データとの類似度を次に計算する被検索対象データ系列中のデータを決定する。そして、この決定したデータが、当該データの次のデータでなければ、当該データの次のデータから、前記決定したデータの直前のデータまでを検索データに類似するデータとして出力し、前記決定したデータについて、当該データと同様の処理を繰り返す。
【００９０】
次に本実施の形態に係るデータ検索装置３００の動作を説明する。
【００９１】
データ検索装置３００の動作は、実際のデータ検索動作の実行に先立って行われる第１および第２のスキップ対応表生成動作と、生成された第１および第２のスキップ対応表を用いたデータ検索動作とに大別される。
【００９２】
（１）第１および第２のスキップ対応表生成動作
第１のスキップ対応表生成部１３０が被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータ毎に第１のスキップ対応表を生成する動作は、既に詳細な動作を説明した第１の実施の形態における第１のスキップ対応表生成部１３０と同じであるため、その説明は省略する。
【００９３】
第２のスキップ対応表生成部２３０が被検索対象データ系列記憶部１４０に記憶された被検索対象データ系列中のデータ毎に第２のスキップ対応表を生成する動作は、既に詳細な動作を説明した第２の実施の形態における第２のスキップ対応表生成部２３０と同じであるため、その説明は省略する。
【００９４】
（２）データ検索動作
制御部３２０は、検索データが与えられると、図１６のフローチャートに示す流れに沿って、その検索データに類似するデータを被検索対象データ系列から検索する。被検索対象データ系列が複数存在する場合、それぞれの被検索対象データ系列に対して、同じ処理が繰り返される。以下では、或る１つの被検索対象データ系列に注目し、そのデータ系列中から検索データと類似するデータを検索する場合を例に、本実施の形態におけるデータ検索動作を説明する。
【００９５】
制御部３２０は、被検索対象データ系列の先頭から何番目のデータを処理の対象としているかを管理する変数ｊを１に初期設定し（ステップＳ３１１）、１番目のデータと検索データとの類似度を類似度計算部１１０により計算する（ステップＳ３１２）。
【００９６】
１番目のデータと検索データとの類似度が、閾値ｔｈより大きければ（ステップＳ３１３でＮＯ）、１番目のデータに対応する第１のスキップ対応表が記憶部１５０に記憶されているか否かを調べる（ステップＳ３１４）。若し、無ければ、変数ｊを＋１して２とし（ステップＳ３１７）、ステップＳ３２４経由でステップＳ３１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００９７】
１番目のデータに対応する第１のスキップ対応表が有れば、１番目のデータと検索データとの類似度を含む類似度範囲がその第１のスキップ対応表に存在するか否かを調べる（ステップＳ３１５）。若し、存在しなければ、変数ｊを＋１して２とし（ステップＳ３１７）、ステップＳ３２４経由でステップＳ３１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【００９８】
１番目のデータに対応する第１のスキップ対応表に、１番目のデータと検索データとの類似度を含む類似度範囲が存在すれば、その類似度範囲に対応して記録されているスキップ先データを次に類似度計算するデータに設定して（つまり、変数ｊがスキップ先データを示すように変更して）（ステップＳ３１６）、ステップＳ３２４経由でステップＳ３１２に戻り、スキップ先データについて、１番目のデータと同様の処理を繰り返す。
【００９９】
他方、１番目のデータと検索データとの類似度が、閾値ｔｈ以下であれば（ステップＳ３１３でＹＥＳ）、１番目のデータを類似データとして出力する（ステップＳ３１８）。続いて、１番目のデータに対応する第２のスキップ対応表が記憶部２５０に記憶されているか否かを調べる（ステップＳ３１９）。若し、無ければ、変数ｊを＋１して２とし（ステップＳ３１７）、ステップＳ３２４経由でステップＳ３１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【０１００】
１番目のデータに対応する第２のスキップ対応表が有れば、１番目のデータと検索データとの類似度を含む類似度範囲がその第２のスキップ対応表に存在するか否かを調べる（ステップＳ３２０）。若し、存在しなければ、変数ｊを＋１して２とし（ステップＳ３１７）、ステップＳ３２４経由でステップＳ３１２に戻り、２番目のデータを次に類似度計算するデータに設定して、１番目のデータと同様の処理を繰り返す。
【０１０１】
１番目のデータに対応する第２のスキップ対応表に、１番目のデータと検索データとの類似度を含む類似度範囲が存在すれば、その類似度範囲に対応して記録されているスキップ先データが現在処理しているデータの次のデータであるか否かを判定する（ステップＳ３２１）。若し、スキップ先データが現在処理しているデータの次のデータでない場合（つまり、幾つかのデータをスキップする場合）、現在処理しているデータの次のデータからスキップ先データの直前のデータまでを、類似データとして出力する（ステップＳ３２２）。そして、スキップ先データを次に類似度計算するデータに設定して（つまり、変数ｊがスキップ先データを示すように変更して）（ステップＳ３２３）、ステップＳ３２４経由でステップＳ３１２に戻り、スキップ先データについて、１番目のデータと同様の処理を繰り返す。また、スキップ先データが現在処理しているデータの次のデータであれば、ステップＳ３２２を実行せずに、スキップ先データを次に類似度計算するデータに設定して（つまり、変数ｊがスキップ先データを示すように変更して）（ステップＳ３２３）、ステップＳ３２４経由でステップＳ３１２に戻り、スキップ先データについて、１番目のデータと同様の処理を繰り返す。
【０１０２】
ステップＳ３２４では、変更後のｊの値が、被検索対象データ系列のデータ数の最大値ｊmaxを超えているか否かを判定し、若し超えていなければ、制御をステップＳ３１２に移し、若し超えていれば、当該被検索対象データ系列に対する検索処理を終了する。
【０１０３】
このように本実施の形態によれば、被検索対象データ系列の中から、検索データとの類似度が所定の閾値以下のデータを高速に検索することができる。
【０１０４】
その第１の理由は、被検索対象データ系列中の或るデータと検索データとの類似度が閾値より大きくなった場合、当該或るデータに対応する第１のスキップ対応表を参照することにより、類似度計算が不要なデータをスキップすることができるためである。
【０１０５】
例えば、検索対象データ系列中のデータｙjと検索データとの類似度が７２であった場合、データｙjに対応する図５または図６の第１のスキップ対応表によれば、スキップ先データはｊ＋７である。このため、検索対象データ系列中のデータｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6の６個のデータについては、検索データとの類似度計算は行われないので、その分だけ検索時間が短縮される。また、データｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6のそれぞれについて個別に、検索データとの類似度計算の必要性を判定する必要がないため、その分だけより一層、検索時間の短縮が可能になる。
【０１０６】
第２の理由は、被検索対象データ系列中の或るデータと検索データとの類似度が閾値以下になった場合、当該或るデータに対応する第２のスキップ対応表を参照することにより、類似度計算が不要なデータをスキップすることができるためである。
【０１０７】
例えば、検索対象データ系列中のデータｙjと検索データとの類似度が２８であった場合、データｙjに対応する図１２または図１３の第２のスキップ対応表によれば、スキップ先データはｊ＋７である。このため、検索対象データ系列中のデータｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6の６個のデータについては、検索データとの類似度計算は行われないので、その分だけ検索時間が短縮される。また、データｙj+1，ｙj+2，ｙj+3，ｙj+4，ｙj+5，ｙj+6のそれぞれについて個別に、検索データとの類似度計算の必要性を判定する必要がないため、その分だけより一層、検索時間の短縮が可能になる。
【０１０８】
なお、本実施の形態では、閾値ｔｈは１種類に固定されているが、閾値ｔｈが複数存在するデータ検索装置にも適用可能である。その場合、それぞれの閾値ｔｈに関連付けて、その閾値用の第１および第２のスキップ対応表を生成して記憶しておく。例えば、閾値ｔｈが、５０、６０、７０の３種類ある場合、ｔｈ＝５０の第１および第２のスキップ対応表、ｔｈ＝６０の第１および第２のスキップ対応表、ｔｈ＝７０の第１および第２のスキップ対応表を生成して記憶しておけばよい。
【０１０９】
以上本発明の実施の形態について説明したが、本発明は以上の実施の形態にのみ限定されるものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解しうる様々な変更をすることができる。また、本発明のデータ検索装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における類似度計算部、制御部、第１のスキップ対応表生成部、第２のスキップ対応表生成部などとして機能させる。
【０１１０】
なお、本発明は、日本国にて２００９年１月２３日に特許出願された特願２００９−１２８１１の特許出願に基づく優先権主張の利益を享受するものであり、当該特許出願に記載された内容は、全て本明細書に含まれるものとする。
【符号の説明】
【０１１１】
１００、２００、３００…データ検索装置
１１０…類似度計算部
１２０、２２０、３２０…制御部
１３０…第１のスキップ対応表生成部
１４０…被検索対象データ系列記憶部
１５０…第１のスキップ対応表記憶部
２３０…第２のスキップ対応表生成部
２５０…第２のスキップ対応表記憶部
【図１】
2010084712.tif 000003
【図２】
2010084712.tif 000004
【図３】
2010084712.tif 000005
【図４】
2010084712.tif 000006
【図５】
2010084712.tif 000007
【図６】
2010084712.tif 000008
【図７】
2010084712.tif 000009
【図８】
2010084712.tif 000010
【図９】
2010084712.tif 000011
【図１０】
2010084712.tif 000012
【図１１】
2010084712.tif 000013
【図１２】
2010084712.tif 000014
【図１３】
2010084712.tif 000015
【図１４】
2010084712.tif 000016
【図１５】
2010084712.tif 000017
【図１６】
2010084712.tif 000018
【図１７】
2010084712.tif 000019
【国際調査報告】
2010084712.tif 000020
2010084712.tif 000021
2010084712.tif 000022
2010084712.tif 000023