[[2015__SIGMOD__k-Shape - Efficient and Accurate Clustering of Time Series|k-Shape]] で提案されている [[クラスタリング]]の距離尺度。 SBDは2つのベクトルの類似性を決定する統計的な尺度である[[相互相関]]に基づく距離尺度である． 相互相関を規格化するために以下の正規のうち，データの正規化に関係なく-1から1の間の値を与える係数正規化 $NCC_c$を採用する．  類似度である規格化された相互相関から最大のものを取り出し，1から引くことで非類似度，すなわちベクトル同士の距離になる．NCCが-1から1の値を取るため，SBDは0から2の値を取る．  ### SBDの高速性 上の式の$CC_w$の計算量は$O(m^2)$である． 畳み込み定理により，2つの時系列の畳み込みは，時系列の個々の離散フーリエ変換(DFT)の積の逆離散フーリエ変換(IDFT)として計算できる．しかしDFTとIDFTは依然として $O(m^2)$の計算量をもつ． 畳み込み和を計算すると$O(m^2)$かかるが，下の式からそれぞれを一旦DFTしてから掛け算をして，IDFで元に戻すという計算方法がある． $F(f*g)=F(f)F(g)$ さらにDFTは[[高速フーリエ変換]]で計算可能であり，計算量は$O(m\log(m))$（線形対数時間）に抑えられる． 参考 - [離散フーリエ変換 - Wikipedia](https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B) 相互相関の正規化も効率的に計算でき、SBDの全体的な時間の複雑さは $O(m\log(m))$のままである．