DEIM Forum 2023 2b-2-4

区間 Min-Hash を用いた時系列データに対する近似最近傍探索
友田 涼太†

古賀 久志†† 電気通信大学大学院情報理工学研究科 〒 182–8585 東京都調布市調布ケ丘 1–5–1
E-mail: †t2231102@gl.cc.uec.ac.jp, ††koga@sd.is.uec.ac.jp
あらましDynamic Time Warping (DTW) は時系列データ間の非類似度を測る指標である．DTW は，長さや周期が異なる時系列間で類似性を算出できる一方で計算時間が大きい．そこで，DTW を近似して類似検索を高速化する手法が出現している．従来手法である SSH では，時系列を部分時系列の集合として表し，集合に対するハッシュ(Min-Hash) を利用して高速類似検索を表現する．しかし，ハッシュ値が時系列内の位置と無関係であるため，ハッシュ値の一致と DTW との相関が低かった．本研究では，データベースの量子化をユークリッド距離ベースで適応的に計算し，時系列内でハッシュ値を生成する区間を指定することで，DTW が許容する位置ずれにも対応しつつハッシュ値の一致と DTW との相関を高める手法を提案する．
キーワード 時系列データ処理，データ構造・索引，確率的データ処理，効率性・スケーラビリティ
通過する順番をスケッチとする手法を開発した．さらに，Luo

1 はじめに近年，時系列データはロボット工学，医学，気象学，音声処理，物体検出など多くの分野で用いられるようになり，その量も増加している．その結果，類似時系列検索の重要性が高まっている．2 つの時系列データ間の類似度は，データ長や周期がなるためユークリッド距離では計測が困難である．これに対して，時系列データ間の非類似度を測る指標として Dynamic

Time Warping（DTW）がある．DTW は，2 つの時系列デー
タの距離を最小化するように時間軸を伸長させるので，時系列データ同士の長さや周期が異なっていても類似度を測れるという利点がある．しかし，DTW は 2 つの時系列データの各点間で距離を総当たりで求めるため，計算時間が大きい．したがって，DTW の高速計算は重要な課題である．

Kim ら [1] と Keogh ら [2] は，クエリ時系列データとの DTW
非類似度（以下では DTW 距離と呼ぶ）が小さい時系列データ
をデータベースから求める問題に対して，分枝限定法を用いた．

Rakthanmanon ら [3] は，Kim らや Keogh らが提案した手法などを組み合わせた UCR suite という手法を提案した．同様に，Li ら [4] や Choi ら [5] も枝刈りベースの高速化手法を考案した．こうした枝刈りベースの厳密解法は DTW 距離を正確に計算できる一方で，長い時系列に対しては枝刈り効率が低下して実行速度が遅くなることが知られている．
そこで，DTW の近似値を算出することで高速化を目指す手法が出現している．近似類似検索を高速化する代表的なフら [8] は，Sketch, Shingle & Hash (SSH) という手法を提案した．SSH は数値を要素とする時系列に対して，ハッシュベース
で DTW を高速近似するアルゴリズムであり，厳密解法である UCR suite と比較して計算時間を大きく減らすことに成功した．しかし，SSH はランダムフィルタを使ってハッシュを生成するため，データベースに適応的でなく選択された乱数により検索効率が左右される．
また，ハッシュ値を時系列全体から生成するため，大きく位置が離れた部分時系列同士のマッチングや，複数のハッシュ値を比較する時に DTW が禁じる時間順序が逆転したマッチングが起こる．このように，ハッシュ値が一致したことと DTW との相関が低い．
本研究では，SSH を改善することを研究目的とする．データ
ベースの量子化をユークリッド距離ベースで適応的に計算し，時系列内でハッシュ値を生成する区間を定めることで，DTWが許容する位置ずれにも対応しつつハッシュ値の一致と DTWとの相関を高める手法を提案する．
本稿は以下の通りに構成される．2 節で背景知識である DTWと既存手法である SSH について述べる．3 節で SSH の抱える問題点を指摘し，4 節で問題点を改善した提案手法について述べる．5 節で提案手法の評価実験及び考察を述べる．最後に 6
節でまとめを述べる．

2 DTW

レームワークに Locality-Sensitive Hashing (LSH) があるが，本節では，Dynamic Time Warping (DTW) について述べ

時系列や文字列といった順序情報を持つデータに対しては理る．DTW は，2 つの時系列データ Q，C に対して距離を測る論的な性能保証に裏付けされた実用的なハッシュ関数がないた手法である．ここでは Q の長さを m，C の長さを n とする．

め，まだまだ発展途上な研究分野である．Yu ら [6] は多次元ベ

ここで，qi は Q の i 番目の要素を表す数値である．

クトルを要素とする時系列を対象とする LSH を考案した．また，Astefanoaei [7] らは 2 次元空間上の，つまり 2 次元座標

Q = (q1 , q2 , ..., qm )(1)

を要素とする軌跡に対して，空間内に配置されたディスクをC = (c1 , c2 , ..., cn )(2)

DTW はユークリッド距離と異なり時系列データの位置ずband がある．Sakoe-Chiba band はワーピングの範囲を b(> 0)

れを許してマッチングを行う．具体的には Q と C の各点 qiとすると，ワーピングパスに含まれる任意のインデックスペア

(1 <
=i<
= m) と cj (1 <=j<= n) の距離を総当たりで求めておい(ik , jk ) に対し |ik − jk | <= b という制約条件を追加する．ワーて，ある制約条件下で Q と C をアライメントさせた時の最小ピング制約を導入した場合，起こり得るインデックスペアの種

コストを Q と C の DTW 距離と定義する．アライメントの制類数が nb または mb 個に制限されるため，計算時間は O(nb)約条件は 3 つある．

または O(mb) になる．これは O(mn) よりは小さいが，デー（ 1 ） q1 は c1 と，qm は cn と必ずマッチングすること

タが長くなると計算時間が増大する．

（ 2 ） 任意の 2 つのマッチングペアで時間順序が逆転しないこと（ 3 ） Q と C の全要素が，マッチングに参加していること
以上 3 つの条件を満たすアライメントは，ワーピングパス

2. 2 SSH
Luo らによる SSH [8] は，クエリ時系列データ Q との DTW
距離が小さい時系列データを時系列データベース D からハッで表現できる．ワーピングパスとはインデックスペアの集合でシュを使って高速に求める近似解法である．SSH では各時系列ある．

データ X ∈ D に対してスケッチヒストグラム SX と呼ばれるデータ構造を抽出し，SX に対してハッシュ値を計算する．そ定義 1 (ワーピングパス)

時系列 Q, C 間のワーピングパス P

して，クエリ Q とハッシュ値が一致したデータベース内の時系
列データは DTW 距離が小さい可能性が高いとみなす．DTW

は，長さを K として，以下のように表される．

距離が小さい可能性が高い時系列データに対してのみ実際に

P (Q, C) = ((i1 , j1 ), (i2 , j2 ), ..., (iK , jK ))(3)

ik と jk はそれぞれ時系列データ Q, C のインデックスであり，DTW を計算することで，計算時間を削減する．
時系列データ X = (x1 , x2 , ..., xm ) に対するハッシュ値は以以下の 3 条件を満たす必要がある．

下の 3 ステップで計算される．各ステップを以下に詳述する．

（ 1 ） 先頭と終端同士は必ずマッチングすること，すなわちStep1 部分時系列に対するスケッチの抽出

P1 = (1, 1) かつ PK = (m, n)。

Step2 スケッチ集合からのスケッチヒストグラムの構築（ 2 ） ワーピングパスのインデックスが広義単調増加するこ

Step3 スケッチヒストグラムに対するハッシュ値の算出と．すなわち，2. 2. 1 Step1: 部分時系列に対するスケッチの抽出••

Step1 ではまず，サイズ w のスライディングウィンドウを δ

ik−1 <= ik
jk−1 <= jk

ずつ動かすことにより，X から長さ w の部分時系列（ 3 ） 連続的であること，すなわち，自分より 1 つ前のインデックスとの差は 0 または 1 であること

•
•

(6)

を取り出す．i は部分時系列の番号であり，全部で N = (m−w)δ

ik−1 <= ik <= ik−1 + 1<
jk−1 <jk== jk−1 + 1個の部分時系列が生成される．これらの部分時系列グループにワーピングパス P のコスト C(P ) は式 (4) のようにマッチン
グした点間の距離の合計と定義される．
√ ∑C(P ) =d(qi , cj )2

フィルタベクトル r を適用してスケッチを生成する．r は確率的に生成される w 次元ベクトルである．平均 0，分散 σ 2 で確
2率密度関数が f (x) = √ 1 2 exp(− x2 ) である 1 次元正規分布
2πσ

(4)

から w 個の確率変数を選択し，r = (r1 , r2 , ..., rw ) とする．
スケッチを生成する具体的な手順は次のようになる．N 個の(i,j)∈P

定義 2 (Dynamic Time Warping（DTW）)

DTW はコ

スト最小のワーピングパスのコストとして定義される．A(Q, C)
を Q, C 間の全てのワーピングパスの集合とすると，時系列 Q, C間の DTW は式 (5) となる．

DT W (Q, C) =(i)

XS = (xi∗δ , xi∗δ+1 , ..., xi∗δ+w−1 )min

P ∈A(Q,C)√ ∑部分時系列 XSi (1 <=i<
= N ) とフィルタベクトル r との間で内
(i)

計算する．

{
(i)
BX =

d(qi , cj )2

1
0

(5)

(i,j)∈P(i)

積 r · XS を計算してその正負からビット BX を式 (7) により(i): r · XS >=0(i)
: r · XS < 0

(7)

(i)

この BX は，多次元ベクトルに対する cos 類似度に対するコスト最小となるワーピングパスは動的計画法で求められる．

Locality-Sensitive Hashing (LSH) [9] そのものである．した

DTW の計算コストは，時系列データの各点の距離を総当たりがって，２つの時系列 X, Y に対して BX と BY が一致する確で求めるので O(mn) となる．

2. 1 ワーピング制約

(i)

(i)

ングの範囲を制限し極端な伸縮によるマッチングを防ぐワーピン
グ制約が導入される．代表的なワーピング制約に Sakoe-Chiba

(i)

(i)

となる．θ(XS , YS )
π
(i)
(i)
は 2 つのベクトル XS と YS がなす角である．
(i)

現実のアプリケーションに DTW を適用する際には，ワーピ(i)

率は P [BX = BY ] = 1 −

(i)

(i)
(i)
θ(XS , YS )

(1)

(2)

(N )

次に BX を並べた符号ストリーム BX = (BX , BX , ..., BX )を得る．図 1 に BX の計算手順を図示する．
最終的に BX に含まれる長さ n の部分系列（n-gram）をス

図1

BX の抽出
図3

ビットが不一致となる 2 つの部分時系列の距離が近い事例

ケッチとする．n-gram は X に含まれる長さ w + (n − 1)δ の部分時系列を n 次元バイナリベクトルとして表したものと見な
せる．

2. 2. 2 Step2: スケッチ集合からのヒストグラムの構築
ここでは，抽出したスケッチ集合（n-grams）から，スケッ
チヒストグラム SX = {(Si , wi )} を構築する．wi は，時系列に存在するビットパターン Si の頻度である．ここで，ビットパターンの種類数は最大で 2n となる．図 2 は，n = 2 のときの 2-gram からヒストグラムを構築した例である．

(i)

(i)

構成する 1 ビットが一致した，つまり BX = BY となったと(i)(i)
いうことは，部分時系列 XS ，YS をベクトルと見なした時(i)(i)に向きが近いということである．しかし，これは XS と YS(i)(i)
とが空間的に近いことを意味しない．同様に，BX =| BY と(i)(i)
なっても XS と YS が空間的に離れているとは限らない．図

3 に，部分時系列 q とビットが一致しない部分時系列との距離が近くなってしまう例を示す．この図では a, b, q がフィルタベ
クトルが定める分離面の同じ側に存在し，c のみ反対側に存在する．すなわち，a, b のビット値はクエリ q と一致するが，c のビット値は q と異なる．しかし，c は b よりクエリ q との距離が明らかに近い．DTW は要素間の距離から求められるので，本例は，SSH による n-gram と DTW との相関が弱いことを示している．
また，SSH では，Step1 のフィルタベクトル r をデータベー

図2

n = 2 のときの 2-grams のヒストグラム

ス D とは無関係に確率的に生成する．つまり，r は D に対して適応的に選択されていない．この結果，フィルタベクトルのSSH において SX は時系列データ X を長さ w + (n − 1)δ の部分時系列の多重集合として表したものとなる．

2. 2. 3 Step3: ヒストグラムに対するハッシュ値の算出(i)

値によっては内積値 r · XS の正負が偏り，ほとんどの時系列(i)に対してビット値 BX が等しくなってしまう危険性がある．この場合 n-gram が部分時系列を識別する能力が低下する．

Step3 ではヒストグラム SX に対して，頻度 wi を重みとす

SSH の 2 つ目の問題点は，top-k 検索でハッシュ値を照合す

る重み付き Min Hash を計算し，ハッシュ値とする．重み付

る際に部分時系列が持つ時刻情報を完全に捨てていることでき Min Hash は，Weighted Jaccard similarity と等しい衝突ある．この性質のため，ハッシュ値を時系列全体から生成する確率を持つハッシュ関数である．このハッシュ関数を mh(X)

SSH では，Sakoe-Chiba band 等で指定されたワーピング制約とする．重み付き Min Hash の計算には Consistent Weightedを満たさない部分時系列がマッチングする可能性がある．さらSampling [10] を利用する．

に，複数個のハッシュ値を照合する時に図 4 に示すような DTW

2. 2. 4 類 似 検 索

で禁じられている時間順序が逆転したマッチングが起こる可能時系列データベース D = {Xi |1 <=i<
= |D|} からクエリ Q に性がある．この図は 2 つの時系列データ X, Y 間に対して，2

対する DTW 距離に基くハッシュを利用した top-k 検索の手順を述べる．
前処理として，全ての Xi ∈ D に対して l 個のハッシュ関数

個のハッシュ関数 mh1 , mh2 のハッシュ値が一致する状況を描いているが，mh1 と mh2 のマッチングする部分時系列ペアが交差してしまっている．DTW ではワーピングパスは単調でなを使いハッシュ値 mh1 (Xi ), ..., mhl (Xi ) を計算する．LSH にければならないのでこうしたマッチングを許さないが，SSH でよる検索のため，これらをインデックスとし，l 個のハッシュ

は時間順序が逆転したマッチングを許容しており，DTW に忠

テーブルに登録する．クエリ Q を処理する時には，Q に対し実でない．

て l 個のハッシュ値 mh1 (Q), ..., mhl (Q) を計算し，対応する l
個のバケットを探す．そして，バケットに含まれる候補時系列
データの中から DTW を計算して top-k を出力する．

3 SSH の問題点
まず，SSH の 1 つ目の問題点として Step 1 で生成される

n-gram と DTW の相関が弱いことが挙げられる．n-gram を

図4

時間順序が逆転したマッチング例

(i)

(1)

(2)

(N )

CX とすると，X は所属クラスタの集合 {CX , CX , ..., CX }4 提案手法として表現できる．この集合に対するヒストグラムを，X に対するスケッチヒストグラム SX と定める．

前節では（ 1 ） n-gram が (a) 部分時系列（ベクトル）の向きに基づいており，時系列データの距離から計算される DTW との相関が弱いこと，及び，(b) ランダムに選択されたフィルタベクト

部分時系列の代表 Word への量子化は，部分時系列と代表Word のユークリッド距離に基づいている．したがって，同じ代表 Word に量子化された部分時系列同士は，距離が近い可能性が高い．本手法は，代表 Word をクラスタリングによって決ルがデータベース D に適応的でないこと（ 2 ） ハッシュ値を時系列全体から 1 つ生成するため，大きく離れた位置同士でのマッチングや，複数のハッシュ値を比較する時に時間順序が逆転したマッチングが起こり，DTW に忠実でないこと定している．つまり，代表 Word は D のデータ分布に適応的に決定されており，各時系列データ X のヒストグラム SX も

D のデータ分布に適応的になる．
4. 2 区間 Min Hashという SSH の問題点を 2 つ指摘した．本稿ではこれらを改善する Bag-of-sketch, Section Hash (BSecH) という手法を提案
する．1 つ目の問題点については，部分時系列をユークリッド
距離ベースで D に対して適応的に量子化することで改善する．

2 つ目の問題点については，時系列内でハッシュ値を生成する区間を定める区間 Min Hash を提案し，ハッシュ値の一致とDTW との相関を高めることで改良する．以下では，それぞれの手法について説明する．

し て ハッシュ値 を 生 成 す る ．具 体 的 に は X の ス ケッチ
(1)

(2)

(N )

{CX , CX , ..., CX } に対して，始点 u と幅 d を選択して部分
(u)

(u+1)

スケッチ {CX , CX

(u+d−1), ..., CX} を取り出す．部分スケッチに対して重み付き Min Hash を計算する．このハッシュ値を

mh(X) とする．ハッシュを生成する区間を定めることで，一定以上離れた部分時系列同士のマッチングや，時間順序が逆転したマッチングを防止する．時系列データ X, Y 間において，4. 1 ユークリッド距離ベースの部分時系列の量子化
本手法は，画像処理で使われてきた Bag-of-Visual-Words(BoVW) [11] から発想した．BoVW では画像データベース Iから抽出された局所特徴ベクトルをクラスタリングし I に適応的に量子化する．そして，1 枚の画像は Visual Word のヒスト
我々の手法は，時系列データ X から切り出された長さ w の部分時系列を w 次元の局所特徴ベクトルと見なしてクラスタリ
ングすることにより代表 Word を計算し，X を代表 Word のき，対応する部分時系列のマッチングのずれは必ず d 以下になる．また，2 つの異なる区間 [u1 , u1 + d − 1], [u2 , u2 + d − 1]

(u1 < u2 ) に対するハッシュ値が同時に一致したとき，部分ス
ケッチの先頭と最後尾の位置は u1 + d − 1 < u2 となるので，

X に対してハッシュ値を生成するステップは以下の通りである．
（ 1 ） X のスケッチを t 個の部分区間に等間隔に分割する．
（ 2 ） 各部分区間の中からランダムに始点 u を選択する．

ヒストグラムとして表現する．
具体的には，ウィンドウサイズ w のスライディングウィンド
ウをステップサイズ δ ずつ動かしながら，X より部分時系列(i)

XS = (xi∗δ , xi∗δ+1 , ..., xi∗δ+w−1 ) を切り取る．部分時系列の(i)

長さは w なので，XS を w 次元ベクトルと見なす．そして，(2)

ハッシュ値が一致したとき，すなわち mh(X) = mh(Y ) のと

時間順序が逆転したマッチングが起こらない．

グラムとして特徴表現される．

(1)

区 間 Min Hash は ，時 系 列 デ ー タ X の 部 分 区 間 に 対(N )部分時系列の集合 {XS , XS , . . . , XS

} を X の特徴点集合とする．この時点では SSH と全く同じ部分時系列が切り出さ（ 3 ） 始点 u から区間幅 d の範囲の部分スケッチを取り出す．
（ 4 ） 各部分スケッチに対して重み付き Min Hash を計算する．
図 5 は，区間 Min Hash におけるハッシュ値の生成を図示したものである．X のスケッチ CX を縦の黒線で t 個の部分区間に分割している．赤の枠線が区間幅 d の部分スケッチであり，各部分スケッチからハッシュ値 hv1 , hv2 , ..., hvt を生成する．各区れることに注意されたい．
この過程を全時系列データ ∀X ∈ D に対して繰り返し，D 全体に対する特徴点集合 Ω を得る．代表 word は Ω を k-means
法でクラスタリングすることで決定される．クラスタ数を k ，

i 番目のクラスタを Ci とすると，k-means 法では Ci の代表
Word を Ci に所属する特徴点の重心と定める．したがって，代表 Word の総数はクラスタ数と同じ k になる．また，各特徴点
は最もユークリッド距離が近い代表 Word (のクラスタ ID) に

図5

区間 Min Hash のハッシュ値の生成

量子化される．部分時系列は SSH では n-gram に変換されていたが，BSecH ではクラスタ ID に量子化される．したがって，

SSH における n-gram は提案手法におけるクラスタ ID に相当

間から 1 つのハッシュ値を生成するため，t 個のハッシュ値が生成される．区間幅 d と分割数 t が区間 Min Hash のパラメータとなる．また，区間の始点 u はすべての時系列データに対し

する．
(i)

時系列データ X の部分時系列 XS が所属するクラスタをて共通であり，時系列データ毎に値を変えてはいない．
実装では SSH と同様に l 個のハッシュ関数 mh1 , mh2 , · · · , mhl

を用意する．ハッシュ関数 mhi で j 番目の部分区間で取り出
ij•

Ubuntu20.04とする．ハッシュ関数によって取り

また，実装は全て C++で行った．SSH は，著者が公開して出す部分区間の位置は異なるため，部分スケッチの位置は全部いる C++プログラム [12] を使用して実装をした．提案手法ので tl 箇所になる．1 個のハッシュ関数に対して t 個のハッシュ実装において，k-means の実装は OpenCV を用いて行った．

される部分スケッチを X

値が生成されるため，X に対して合計で tl 個のハッシュ値が生成される．

4. 3 k-NN 探索アルゴリズム
ハッシュを利用した時系列データベース D = {Xi |1 <=i<=

|D|} からクエリ Q に対する DTW 距離に基く top-k 検索の手順を述べる．
前処理として，全ての Xi ∈ D に対して l 個のハッシュ関数

mh1 , mh2 , ..., mhl を使い l 個のハッシュ関数から t 個ずつハッシュ値を計算し，合計で tl 個のハッシュ値を計算する．LSH による検索のため，これらをインデックスとし，tl 個のハッシュテーブル T に登録する．クエリ Q に対する DTW 距離に基く

top-k 検索のアルゴリズムを Algorithm 1 に示す．クエリ Q を処理する時には，Q に対して tl 個のハッシュ値を計算し，対応する tl 個のバケットを探す．ハッシュ値を照合する際には，ハッシュ値だけではなく区間も一致してはじめてハッシュ値が一致したと判定する．そして，クエリと少なくとも 1 個以上のハッシュ値が一致した候補時系列に対して DTW を計算して top-k を出力する．この際に，候補時系列をハッシュの一致
した数の降順に並び替え，ハッシュの一致数が多い時系列から

DTW を計算する．ハッシュの一致数が多いほど DTW の値が小さくなることが期待できるので，ハッシュの一致数の降順にDTW を計算することで枝刈りにおける DTW の lower bound
を早期に減少させることが出来る．

データセットは，SSH の論文で用いられていた実データ(ECG データセット) を使用した．ECG データセットは，22 時
間 23 分の ECG データ（20,140,000 データポイント）で構成
されている．ECG データに対して，z-score normalization を行い，1024 データポイントごとに区切ることで，それぞれ長さ1024 の時系列データにした．時系列データは 4000 個使用した．
z-score normalization は，以下の式よりデータを正規化した．
xnew =(x − x̄)σ(x)(8)

x̄ は時系列データの平均，σ(x) はデータの標準偏差である．ク
エリ時系列データは，ECG データセットから長さ 1024 の時系
列データを切り出して作成した．

5. 1 SSH との性能比較
本節では，提案手法 BSecH と従来手法 SSH との性能を比較する．ECG データセットに対して，それぞれのアルゴリズム
で top-20 近傍探索を行った．各実験において，クエリ時系列を変えて 20 回，乱数 seed を変えて 5 回実行した時の平均をとった．評価指標として，D の全データに対して DTW 計算を行った際の top-20 厳密解と top-20 近傍探索により出力された解が一致した割合を再現率とした．

SSH の各パラメータは，SSH の論文で ECG データセットに対して最適だとしている w = 80, δ = 3, n = 15 とした．BSecH
では，w = 80, δ = 1, k = 1024, t = 10, d = 20 とした．ワー
ピング制約は b = 10 とした．このパラメータ設定を BSecH のAlgorithm 1 Query Process
1: 候補集合 R を null に初期化
2: for i = 1 to l dofor j = 1 to t do

3:4:

関係を調べた．結果を図 6 に示す．横軸は DTW 距離の計算回

ハッシュ値 mhi (Qij ) を計算数であり，ハッシュ値の一致回数が大きい順に何回 DTW 距離追加

end for6:

ハッシュ値の一致と DTW 距離との相関性を測る目的で，ハッシュ値が一致したデータに対する DTW の計算回数と再現率のクエリ Q のスケッチから区間 Min Hash で j 番目の区間のハッシュテーブル Tij のバケツ mhi (Qij ) の時系列を R に

5:

デフォルトパラメータとする．また，SSH，BSecH とも DTW
計算では，UCR suite による枝刈りを行った．

7: end for
8: return R から UCR suite を用いて top-k 探索を計算したのか表す．計算回数が少なく再現率が高いほどハッシュ値が DTW 距離に忠実ということになる．BSecH をフルに使用したもの，BoVW に基づく量子化と重み付き Min Hashを使用したもの (BoVW)，フィルタベクトルによる量子化と区間 Min Hash を使用したもの (区間 Min Hash)，SSH について実行した．このとき，乱数のばらつきによる性能への影響を抑えるため，ハッシュ関数の数を増やし BSecH と区間 Min Hash

5 実験評価を l = 20 とし，BoVW と SSH は l = 60 とした．BoVW と
区間 Min Hash は，単体でも SSH より常に高い再現率となっ実データを用いて，従来手法である SSH と提案手法である

た．BSecH は，これらよりさらに高い再現率を記録し，組み合

BSecH を実験により性能を比較した．また，提案手法においわせることでより性能が高まることが示された．また，SSH はて，問題による最適なパラメータについての実験を行った．

DTW 計算した時系列データ数にほぼ比例して再現率が上がっ

全ての実験は，以下に示す環境で行った．

ているのに対して，BSecH では SSH の場合より早期に再現率•

Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz × 16

が上がっている．これは，区間 Min Hash のハッシュの一致と•16GB メモリ

DTW の間に強い相関があることを示している．

5. 2 パラメータの効果
本節では，BSecH でのパラメータが検索性能にどう影響を与えるのか調べるため，区間幅 d とウィンドウサイズ w を変化させる実験を行った．

5. 2. 1 区 間 幅 d
BSecH における，区間幅の大きさによる再現率への影響を調べた．Sakoe-Chiba band b = 10 としたとき区間幅 d を 10から 40 まで変化させたときの再現率を図 8 に示す．再現率は

d = 10 で低く，d = 20 で最も高くなっており，更に d を増やすと再現率は低くなった．このことから，Sakoe-Chiba band に対する BSecH の性能を最大に引き出すことができるパラメー
タが存在することが考えられる．

図 6 BSecH と SSH の DTW 計算した時系列データ数と再現率

次に，実行時間による評価実験を行った．BSecH と SSH における top-20 近傍探索を行ったときの実行時間とそのときの再現率の関係を図 7 に示す．実行時間による評価では，BSecHのハッシュ関数の数を l = 10 とし，SSH は，SSH の論文で最適としている l = 20 にして実行時間とそのときの再現率を調べた．横軸が実行時間であり，縦軸が再現率である．BSecH は

SSH に比べて実行時間が短く，全体的に再現率も高い値を記録した．平均の実行時間は，BSecH は 22.26ms，SSH は 47.86ms
であり，BSecH は SSH と比較して約 53% 短くなった．また，BSecH は SSH より実行時間のばらつきが少ない．実行時間は
DTW の計算量に大きく影響される．SSH ではランダムなフィルタベクトルでスケッチを作成しているため，ハッシュの一致
する時系列データ数が不安定であり，実行ごとの候補時系列

図 8 BSecH における Sakoe-Chiba band b = 10 の場合の区間幅 dを変化させたときの再現率

データ数のばらつきが大きく実行時間も不安定である．一方で，BSecH では，BoVW による安定かつ適切なスケッチの作成に
より実行時間のばらつきも少ない．

次に，BSecH における，Sakoe-Chiba band b = 20, 50 としたとき区間幅 d を変化させたときの再現率をそれぞれ図 9 及び図 10 に示す．異なる b のそれぞれの場合において，高い再現率を記録する d の値があり，適したパラメータが存在することが分かった．いずれの場合も，b より 10 大きい区間幅の再現率が高い結果となった．

5. 2. 2 ウィンドウサイズ w
BSecH における，ウィンドウサイズの大きさによる再現率への影響を調べた．Sakoe-Chiba band b = 10 としたときウィンドウサイズ w を 40 から 100 まで変化させたときの再現率をそれぞれ図 11 に示す．ウィンドウサイズが大きいほど再現率は高くなり，w = 80 でピークになり，w = 100 はほぼ同じ高さとなった．ウィンドウサイズ w は時系列データから切り出す
部分時系列の長さである. BSecH においてハッシュ値が一致したという事は，部分時系列ペアがユークリッド距離が小さく似ていたために同一クラスタに所属したということである．そして，BSecH はハッシュ値が一致する時系列データペアほど類似
図 7 BSecH と SSH の実行時間 (ms) と再現率性が高いと判定する．したがって，図 11 の実験結果は，部分時系列の類似性に着目して時系列データの類似性判定を行うア
プローチにおいて，部分時系列の適切な長さが存在することを図 9 BSecH における Sakoe-Chiba band b = 20 の場合の区間幅 dを変化させたときの再現率

図 10 BSecH における Sakoe-Chiba band b = 50 の場合の区間幅 dを変化させたときの再現率示している．

図 11 BSecH における Sakoe-Chiba band b = 10 の場合のウィンド
ウサイズ w を変化させたときの再現率

図 12 BSecH における Sakoe-Chiba band b = 20 の場合のウィンド
ウサイズ w を変化させたときの再現率

いことであり，もう 1 つはハッシュ値を時系列全体から 1 つ生

次に，Sakoe-Chiba band b = 20, 50 としたときウィンドウ成するため，大きく離れた位置同士でのマッチングや，複数のサイズ w を変化させたときの再現率をそれぞれ図 12 及び図 13

ハッシュ値を比較する時に時間順序が逆転したマッチングが起に示す．Sakoe-Chiba band の大きさを変えたいずれの場合も，こり，DTW に忠実でないことである．そして，これら 2 つのw = 40 の w が小さい場合では再現率が低く，W = 80, 100 で問題点を改善した計算手法である BSecH を提案した．新たなス

高くなった．この結果から，BsecH における適切な部分時系列

ケッチ生成方法では，ユークリッド距離ベースで部分時系列を

長は Sakoe-Chiba band のパラメータに依存しないと言える．

量子化し，DTW との相関が強いスケッチを生成できるようにした．新たなハッシュ計算方法である区間 Min Hash では，ス

6 結論

本論文では，データベースから，クエリ時系列データとのDTW 距離が小さい時系列データを求める問題に対しての，ハッシュを用いた近似高速計算手法である SSH について，データの特徴表現であるスケッチと類似検索アルゴリズムであるハッシュの 2 つの問題点を指摘した．1 つは n-gram が時系列データの距離から計算される DTW との相関が弱いこと，及びランダ
ムに選択されたフィルタベクトルがデータベースに適応的でなケッチから部分的に区間を定めて取り出し，ハッシュ値を生成することで，DTW が許容する位置ずれに対応しつつハッシュ値の一致と DTW との相関が強いハッシュ値を生成できるようにした．実データを用いた実験により，BSecH が SSH より高い精度を得られることを示した．また，区間幅を DTW のワー
ピング制約のサイズより少し大きくすることで，高い性能を得られることも分かった．今後は，Sakoe-Chiba band の大きさによらずパラメータの調節が必要としない手法の検討を行う．

図 13 BSecH における Sakoe-Chiba band b = 50 の場合のウィンド
ウサイズ w を変化させたときの再現率

謝

辞

本研究は JSPS 科研費 JP21K11901 の助成を受けたもので
ある．

文

献

[1] Sang-Wook Kim, Sanghyun Park, and Wesley W. Chu. An
index-based approach for similarity search supporting time
warping in large sequence databases. In Proceedings of the
17th International Conference on Data Engineering, pp.
607–614, USA, 2001. IEEE Computer Society.
[2] Eamonn Keogh, Li Wei, Xiaopeng Xi, Michail Vlachos,
Sang-Hee Lee, and Pavlos Protopapas. Supporting exact
indexing of arbitrarily rotated shapes and periodic time series under euclidean and warping distance measures. The
VLDB Journal, Vol. 18, No. 3, pp. 611–630, oct 2008.
[3] Thanawin Rakthanmanon, Bilson Campana, Abdullah
Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu,
Jesin Zakaria, and Eamonn Keogh. Searching and mining
trillions of time series subsequences under dynamic time
warping. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, pp. 26–270, 2012.
[4] Zhengxin Li, Jiansheng Guo, Hailin Li, Tao Wu, Sheng Mao,and Feiping Nie. Speed up similarity search of time series
under dynamic time warping. IEEE Access, Vol. 7, pp.
163644–163653, 2019.
[5] Wonyoung Choi, Jaechan Cho, Seongjoo Lee, and Yunho
Jung. Fast constrained dynamic time warping for similarity measure of time series data. IEEE Access, Vol. 8, pp.
222841–222858, 2020.
[6] Chenyun Yu, Lintong Luo, Leanne Lai-Hang Chan,
Thanawin Rakthanmanon, and Sarana Nutanong. A fastlsh-based similarity search method for multivariate time series. Information Sciences, Vol. 476, pp. 337–356, 2019.
[7] Maria Astefanoaei, Paul Cesaretti, Panagiota Katsikouli,
Mayank Goswami, and Rik Sarkar.
Multi-resolution
sketches and locality sensitive hashing for fast trajectory
processing. In Proceedings of the 26th ACM SIGSPATIALInternational Conference on Advances in Geographic Information Systems, SIGSPATIAL ’18, pp. 279–288, New York,NY, USA, 2018. Association for Computing Machinery.
[8] Chen Luo and Anshumali Shrivastava. SSH (sketch, shingle,& hash) for indexing massive-scale time series. In Proceedings of the NIPS 2016 Time Series Workshop, co-locatedwith the 30th Annual Conference on Neural Information
Processing Systems (NIPS 2016), Barcelona, Spain, December 9, 2016, Vol. 55, pp. 38–58, 2016.
[9] Moses S. Charikar. Similarity estimation techniques fromrounding algorithms. In Proceedings of the Thiry-Fourth
Annual ACM Symposium on Theory of Computing, STOC
’02, pp. 380–388, New York, NY, USA, 2002. Association
for Computing Machinery.
[10] Mark Manasse, Frank McSherry, and Kunal Talwar. Consistent weighted sampling. Technical Report MSR-TR-201073, June 2010.
[11] Fuentes-Pineda Gibran, Koga Hisashi and Watanabe Toshinori. Scalable Object Discovery: A Hash-Based Approachto Clustering Co-occurring Visual Words. IEICE Transactions. 94-D. 2024-2035. 10.1587/transinf.E94.D.2024, 2011.
[12] Chen Luo. ssh, 2017. https://github.com/rackingroll/ssh.