# 時系列類似度検索 ## 定義 時系列類似度検索（time series similarity search）は、クエリ時系列と形状が類似した部分系列や時系列を、大規模な時系列コレクションから効率的に発見するタスクである。運用監視の文脈では、異常が検知された時系列と過去の障害パターンや他のメトリクスとを照合することで、根本原因の候補を絞り込む用途に使われる。全対全比較は $O(n^2)$ の計算量になるため、フィンガープリントや近似手法で探索空間を絞ることが実用化の鍵となる。([[@2015__SREcon15 Europe__Signatures, Patterns, and Trends - Timeseries Data Mining at Etsy]]) 主なアプローチ: - **特徴量変換ベース**: 時系列を特徴ベクトル（形状記述アルファベット、SAX、傾きトークン等）に変換し、転置インデックスや近似最近傍探索で類似候補を絞り込む - **動的時間伸縮(DTW)ベース**: 位相ずれに対して不変な距離尺度で全対全比較するが計算コストが高い - **埋め込みベース**: 深層学習で時系列を低次元ベクトルに変換し、ベクトルデータベースで近似最近傍検索を行う（近年の傾向） ## 横断的知見 - （横断的知見は複数ソースの突き合わせで更新する。現時点では 1 ソースのみのため未記入） ## 未解決の問い - 形状記述アルファベット（Etsy の [[Oculus]] が採用）の精度・再現率の定量評価は公開されていない。DTW や SBD（k-Shape で採用）と比較した場合のトレードオフはどうか。([[@2015__SREcon15 Europe__Signatures, Patterns, and Trends - Timeseries Data Mining at Etsy]]) - Elasticsearch のスロッピーフレーズクエリはトークン順序の一部を無視できるが、どの程度の形状変動まで許容できるか。許容範囲のパラメータ設定はどう決めるか。 - 埋め込みベースの深層学習手法は 2015 年の形状記述アルファベット手法を精度・速度の両面で上回っているか。運用監視の文脈での比較評価が必要。 - 時系列類似度検索の成功が根本原因特定（[[Fault Localization]]）にどの程度貢献するか。形状が似た時系列が同じ根本原因を持つ保証はないため、因果推論との組み合わせが必要か。 ## 関連 - 手法: [[Oculus]]（Etsy 製の時系列類似度検索 OSS） - 接続概念: [[異常検知]]（類似度検索は異常検知の後段として根本原因を絞る）/ [[時系列クラスタリング]]（類似度計算を共有する）/ [[Fault Localization]]（根本原因候補の絞り込みへの応用） - エンティティ: [[Andrew Clegg]] / [[Etsy]] ## 出典 - [[@2015__SREcon15 Europe__Signatures, Patterns, and Trends - Timeseries Data Mining at Etsy]]