シグネチャを用いた類似検索

シグネチャを用いた類似検索

スペクトルシグネチャ

問題:R木は15次元以上の空間では性能が下がる
解決法:個々のシークエンスから低い次元のシグネチャを取り出し,シグネチャスペースにインデックスする

  • 類似性を判定する方法
    • 時系列を時間軸上で考える方法
    • 時系列を周波数領域に変換して考える方法
  • efficient similarity search in sequence database
    • 時系列を周波数領域に変換して考える方法を使ってる
    • 離散フーリエ変換(Discrete Fourier Transform; DFT)を使ってるらしい.
      • DFT とは系列の時間領域から周波数領域への変換
  • 空間アクセス法
    • 多次元の点,線,多角形などの幾何学的なものをあつかう
    • R木とその変形
      • 空間アクセス手法(spatial access method: SAM)は複雑な空間オブジェクトをデータ空間の軸に平行な矩形(minimum bounding rectangle)により近似することに基づいている。
      • この簡単な近似での最も重要な特徴は複雑なオブジェクトを少ないデータ量で表現できることにある。
      • 多くの情報は失われるが、空間オブジェクトの最小包囲矩形はオブジェクトの最も重要な幾何学的性質を保持している。
  • R木
    • B木に似た木構造のデータ構造であり、多次元情報(例えば、二次元座標データなど)のインデックス付け、すなわち空間インデックスに使われる。
    • それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。
    • http://ja.wikipedia.org/wiki/R%E6%9C%A8


  • F-index
    • k次元空間の展集合の空間索引(R木とかR*木を利用)
  • ST-index
    • 時系列Siを長さwの部分系列に(重複を許して)分割
    • 長さwの各部分系列をw点DFT変換
    • w点DFTの係数k個を特徴関数値として利用
    • 時系列Siは特徴空間上でtrail(小径)として表現される
    • trailの各点をすべて記憶(R*木などを利用)
  • MBR
    • (Minimum Bounding Rectangle = 最小外接矩形)または Envelope。
    • これは境界ジオメトリであり、最小と最大(X,Y)の座標で形成される。
      • 要するにR木で使ってる長方形