       Æ                
 
 

         
      


  







      修士論文：ビット並列手法に基づく高度な時系列パターン照合アルゴリズム
斉藤 智哉
北海道大学 大学院情報科学研究科
コンピュータサイエンス専攻
札幌市北区北  条西  丁目

  

概要
本論文では，多次元実数ストリームに対する複雑な時系列パターンの照合問題に取り組む．ここで，時系列パターンは幾何的制約の時系列として表現され，ストリーム中でその制約の列が満たされるすべての位置を計算する問題である．幾何的に表現された時
系列パターンの高速な照合のために，複数の幾何制
約問合せの静的コンパイルとビット並列手法を組み合わせた機構を提案する．主結果として， 次元整数
ストリーム上の時系列パターン照合問題を  時間で，  次元実数ストリーム上の次元間に相関の無い時系列パターン照合問題を    !  時間
で， " # 次元実数ストリーム上の時系列パターン照合問題を    !  時間で解くアルゴリズムをそれぞれ与える．ここで，    はそれぞれ，パターン長と，パターンサイズ，ストリーム長，マシ
ンレジスタ長である．また，計算機実験を行い，既存手法を単純に拡張した場合に比べて $ $ 倍程
度高速に動作することを確認した．



はじめに



背景

図  連続データストリームに対するクエリ照合



研究目的

本論文では，連続データストリームに対して時系列パターンによる問合せが与えられる，プッシュ型ス
トリーム処理について考察する．すなわち，クエリ
が初めに与えられ，それを処理する機構に多次元の数値データが絶え間なく連続的に入力される場合を想定している（図 ）．これは，静的な関係データ
ベースに対してクエリを投げかけ，それに合致するデータを得るプル型のデータ処理とは対照的な処理である．
本論文では，多次元連続データストリームに対す
る新しいタイプの問合せ処理として，  次元実数ス
トリームに対する幾何的制約による時系列質問（! *  * +*,）を提案し，その効率よいパターン照合方法について研究する．すなわち，この照合機械は，ある単位時間毎に  次元の実数値ベクトルが流れ込むデータストリームに対し，パターンとして与えられた幾何的制約の系列をすべて満たすベクトル列が入力されたか否かを判別する．図 #に，ストリームの点列が時系列パターンに一致したときの概念図を示す．

自動測定技術や高速ネットワーク技術の発展により，センサーデータや，通信記録，半構造データなどのストリームの形をとるデータが増大している．これに伴い，ストリームデータに対する大規模データ処理が重要になっている %#& '& & & (& #)．

 

#論文で提案するパターン照合アルゴリズム  は，
まず前処理時に，パターンに含まれる幾何学質問の集合に対して前処理を行い，実行時に入力となる 次元実数ベクトル  上で成立するすべての質問からなる部分集合   "  "   を見つけるヒット表計算を高速に実行しながら，パター
ン照合を行う非決定性オートマトンを模倣する．このアルゴリズムは，特に幾何制約条件が軸並行である場合や次元数が # の場合において，効率の良い照合を行うことができる．本論文では，多数の幾何学質問に対するヒット表計算の高速な実現方法を与える．

  

図 # 幾何的制約の系列による時系列パターン照合        #  " #   " 
 "
- 
 "
"

" 



$
$



"

 



主結果

本論文では， 次元実数ストリーム上の時系列パターン照合問題に対し，次のアルゴリズムを与える．

図 - 実数ストリームに対するパターン






対するパターン照合問題を  前処理時間と， 領域を用いて    時間で解く素朴なアルゴリズム 
．

関連研究.* %& ) や，/* 0  ら %-) は， 次元の実数データストリームに対して，図 - のような不等式からなるパターンの照合を行う問題を定義した．
また，この問題に対し，よく知られた文字列照合手法である 12 法 %& $& ) と 32 法 %-& $& ) を拡張した高速な時系列パターン照合アルゴリズム 4#5と 5#4 をそれぞれ与えた．これらの手法では，時系
列パターンの制約間の包含関係をあらかじめ前処理時に解析することで実行時の高速化を行う．しかし，包含関係が成り立たない制約を多く含む場合や，成立しやすい制約を含む場合，パターン長が短い場合には有効性が低いという問題点がある．

#

 次元整数ストリーム上の不等式の論理和制約

-



'

 次元実数ストリーム上の次元間に相関のない

ビット並列パターン照合とは，前処理としてパターンに対応する 67非決定性オートマトン を構築し，実行時にビット演算を用いてその動作を高速に模倣する手法であり，ここではとくに高速かつ実装が容易な技法である / 8 7 手法 %#) の拡張を扱う．しかし，ビット並列手法の単純な適用では自明な手法と同じ  時間解法しか得られない．本のクラスに対するパターン照合問題を  前処理時間と，   領域を用いて  時間で解くアルゴリズム   ．

次元実数ストリーム上 の 不等 式 の論 理 和
制約のクラスに対するパターン照合問題を 前処理時間と，   領域を用いて    !  時間で解くアルゴリズム 
 ．
不等式の論理和制約のクラスに対するパターン
照合問題を   前処理時間と，  領域を用いて    !  時間で解くアルゴリズム  ．

提案手法

そこで本論文では，別のタイプのよく知られた文字列照合手法であるビット並列パターン照合 %#) を拡
張し， 次元実数変数上の時系列パターンに対する高速なパターン照合アルゴリズム  を与える．また，次元間に相関のない制約の場合とある制約の場合について，それぞれ高速なアルゴリズムを与える．

 次元実数ストリーム上の線形制約のクラスに$

 次元実数ストリーム上の線形制約のクラスに対するパターン照合問題を  前処理時間と， 領域を用いて    時間で解く素朴なアルゴリズム 
．



 " # 次元実数ストリーム上の線形制約のクラスに対するパターン照合問題を   前処理
時間と，   領域を用いて    ! 
時間で解くアルゴリズム  ．

   Æ          


 " # 次元実数ストリーム上の線形制約のクラスに対するパターン照合問題を     前
処理時間と，     領域を用いて   時間で解くアルゴリズム  ．

 

ここに，  "は，パターン のサイズであり，
 "  はストリーム  の長さ， はバケットの分
割数， は事後チェックに要する時間である．

 

また，提案アルゴリズムの有効性を検証するた
めに，人工データ上で評価実験を行った．その結果，パターン長が短い場合やその制約が緩い場合に，
3/ は 12 手法と 32 手法 %#) に基づく既存手
法  %& -) と  %) と比較して， $ 倍から $ 
倍程度高速であり，また安定した性能で動くことがわかった．
ビット並列手法は，ハードウェア化による高速化が容易であり，将来のビット幅の増大が性能向上に結びつくと考えられる．また，正規表現照合も可能であるなどの利点を持つなど，実用面でもストリーム処理のための有用な手法と考えられる．
本論文の構成は以下の通りである．まず # 章で，準備として用語と問題の定義を行う．- 章では，ビット並列手法を用いた提案手法である 3/ アルゴリ
ズムの概要について述べる． ' 章では， 次元実数
ストリームの場合のヒット表計算について述べる．$
章では，次元間に相関のない場合の複数次元実数ス
トリームのヒット表計算について述べる． 章では，次元間に相関のある場合の複数次元実数ストリームのヒット表計算について述べる． 章では，実験として，人工データを用いた計算時間の比較実験を行
い，提案アルゴリズムの性能を考察する．  章では，
実データへの応用としてモーションデータを用いた検索実験を行い，結果を考察する．
章 の 内 容 は 9:/;%) と/:<9;%') で 発 表 済 み で あ る ． $ 章 の 内 容は =>;%$) で発表済みであり，  章の内容は
9:/;%) で発表済みである．
な お ，'

準備

本章では，研究対象である  次元実数ストリー
ム上の幾何時系列パターン照合問題を定式化する．
さらに，幾何制約の種々のクラスとこれらに基づく
種々の幾何時系列パターンのクラスを導入する．また，必要な用語を導入する．

        -ビット演算

本論文では，計算モデルとして，以下の数値演算とビット演算をもつ 572 機械を仮定する %& #)．整
数レジスタのビット幅を  と仮定する．長さ  のビットマスクは，最下位ビットを右側としたビット列     で表す．長さ   のときは上位の残りビットに  を詰めることとする．
ビットごとの論理和と，論理積，否定をそれぞれ記
号 と，?， で表す．非負整数     に対して，ビットマスク  の  ビットの左シフトを  で表す． は  ビットのみのビットマスク
であり，
 "    は  番目のビットがのビットマスクである．整数集合       に対して， で  のビットマスク表
現を表す．

   



 





ビット幅を  "  とする． "   " と仮定する．このとき，次にビット演算の例を示す．
例

  " 
# ビットごとの論理積  ?  " 
- ビットごとの否定  " 
 " 
'  ビットの左シフト ビットごとの論理和 $ のみのビットマスク 

最下位に  の立ったビットマスク  " 



上のビットマスクを左に ' シフトして得られるビットマスク：' "  " 

 "  # - $ のビットマスク表現  "

現代の実用的な計算機では，通常  " -# または
 " ' である．ただし，本稿では  は定数でなく，任意に大きい値をとりうると考える．ここでは，上記すべての数値演算とビット演算は，ビット幅  の整数レジスタ上で  時間で実行できると仮定す
る．これを複数回繰り返すことで，長さ 
のビットマスクに対しては，これらの演算は  
時間で実行できる %& #)．

 

'

次元実数ストリーム上の幾何時系列パ
ターン照合問題Æ "   #     と Ê でそれぞれ非負整数全体と実数全体を表す． £ で集合  の反射的推移閉包%() を表す．正整数  に対して， Ê を  次元実数空間とする． Ê の点またはレコードは，ベクトル "         Ê である．変数 のとる値域を で表す．特に指定しない場合， " Êと仮定する．  次元実数ストリームは，  次元の点 £ である．
列  "      Ê Ê £ は長さ

例   "  $ - $ ' # '  # # の  次元実数ストリームである．
例  




 

"



     #           £ は，長さ  の # 次元実数ストリー
Ê

ムである．
次のようなデータは  次元実数ストリームとして扱うことができる．


#

-

'

交通データのレコードは，# 次元ベクトル "   である．ここに， と  は移動点の緯度と経度である．
蛋白質データのレコードは，ベクトル  "    ! である．ここに，   は原子の- 次元空間座標であり，! は原子の種類や電子価などの付加情報である．
センサーデータのレコードは，その測定値のベ
クトル  "        で表される．
モーションデータのレコードは，"

"  #  $          "  #  $  で ある．ここに，モデルは ( 個の関節を持つと仮定
し， 番目の関節に対して      Ê は - 次元
空間における関節の絶対座標を表し，"  #  $  ) は回転角を表す．

  

次元実数空間上の幾何制約

 に対して， 次元実数空間 Ê 上の二値

任意の 
関数  Ê  を， 次元の 幾何制約（制約）という．文脈から明らかなとき，幾何制約を Ê  の部分集合  Ê   " 
Ê と同一視する．
制約 の表現長をで表す． 次元実数空間上の幾何制約のクラスを  で表す．

 

 


 



を幾何制約の任意のクラスとする． 上の幾何
制約の集合  "      と  次元の点  に対して， における  のヒット表とは， によって満たされる  中の制約の集合   "  " である．ここで，各制約  は，添字  で表すと仮定
する．





  



上のヒット表計算問題とは，あらかじめ定義
上の幾何制約の集合  "      を受け取って前処理を行い，問い合わせとして  次元の点  を受け取り，出力として， の  におけるヒット表  
を計算する問題である．



本稿では，ヒット表は長さ  のビットマスク     として返されると仮定する．
上の長さ  の幾何時系列パターン は，列£ である．ここに，  "   に対して， は 上の長さ  の幾何制約である．

定義 





上記のパターン
のサイズを
"

 

   で定義し，の長さを
   で定義する．

"

長さ  のパターン "        が，長さ  £の  次元実数ストリーム  "      Êにおいて位置 %  に出現するとは， が成立することをいう．





 



定義  パターンのクラス に対する  次元実数ストリーム上の幾何時系列パターン照合問題（パターン照合問題）は，あらかじめ 上の幾何時系列パター
ンを受け取って前処理をし，入力として  次
 £ を受け元実数ストリーム  "      Ê取り，出力として  上の の全ての出現位置を計算する問題である．



ここでの目的は，パラメータ  "   と， " ， "   に対して前処理時間と，使用領域，入力ストリームにおける照合時間を小さくするアルゴ
リズムを設計することである．
この問題を解くアルゴリズムの計算時間の下限
は，明らかに @   時間である．また，実際のス
トリーム監視等の応用を考えたとき，パターン照合
アルゴリズムは，新しく到着する度に漸増的に動く
オンライン性をもつことが望ましい．本論文で与えるすべてのアルゴリズムは，オンライン性をもつア
ルゴリズムである．

   Æ          


幾何制約のクラス

本節では，本論文で扱う幾何制約のクラスを与える．
 次元実数空間 Ê において，変数集合       を考える．点  "       Ê において， 番
目の変数  は値  をとるとする．不等式 + , とは，表現 & " '
 であり，ここに，'
  は符号であり& Ê は定数である．線形不等式* + , は，式 & ' ' 
 である．ここに，'      '   Êは定数である．

















次元実数空間上の幾何制約のクラス

整数ストリーム上の不等式の論理積のクラス． 
次元整数ストリーム上の不等式の論理積のクラス
  を次のように定義する．   上の幾何制
約 は，不等式の論理積 " && である．ここに， ( に対して，& " '  であり，'  & Ê である． " Æ である．

  

である．ここで，各     % (  に対して，& は  番目の変数  に関する制約 & " '  である．ここに，'   であり， Ê，  " Ê である．





次元実数空間上の幾何制約のクラス：
次元間に相関のある場合

 次元の実数空間上の線形制約のクラス．  次元

実数空間上の線形制約のクラス  を次のように定義する．  上の線形制約 は， 次元線形不等式の論理積&      & ( である．ここに，& " '     ' 
 は， 次元線形不等式であり， '      '    Ê，   Ê"である．
例  線形制約の特別な場合として，次のような制約が表現可能である．

 軸並行直方体．  '    '   " %'   ) %'   ) "    '
  '   半平面．) '      '   "       '     '   
 凸多角形 点列  "       で表される凸包   " *    *  *   * " * は非負実数 ．



補題  および   上のすべての幾何制
約は，標準形として変数 に関する つの不等式の論理積 " ' '  として表すこと
ができる．



等式制約 "  も，# つの不等式の論理積    で表すことができる．本論文では，  および   上のすべての幾何制約は標準形であると暗黙のうちに仮定する．

 



次元実数空間上の幾何制約のクラス：
次元間に相関のない場合

 次元実数空間上の不等式の論理積のクラス．  次元実数空間上の不等式の論理積のクラス   を
次のように定義する．   上の幾何制約 は，不等式の論理積"&      &       &      & 

常に成立する線形制約を空の論理積または空集合  

 で表す．

実数ストリーム上の不等式の論理積のクラス． 次元実数ストリーム上の不等式の論理積のクラス
  を次のように定義する．   上の幾何制
約 は，不等式の論理積 " && である．ここに， ( に対して，& " '  であり，'  & Ê である． " Ê である．

        $ 各クラス間の関係 次の包含関係が成立する．すなわち，    かつ   である．











ビット並列手法に基づく幾何時系列
パターン照合アルゴリズムの概要

本節では， 次元の線形制約の列である時系列幾何パターン "        に対して，ビット並列手法を用いて  次元ストリーム上の時系列幾何パター
ン照合を効率よく行うアルゴリズム  を与える．
ビット並列手法は，整数レジスタ上の数値演算を用いて，ビット列上の演算を並列に実行する手法である %#)．ここでは，ビット並列手法を用いた効率良い部分文字列パターン照合手法の中で，実装が容易で高速な / 8 7 技法 %#) を採用する．

 
NFA ᭴▽
䊎䉾䊃䊙䉴䉪᭴▽䊎䉾䊃䊙䉴䉪

䊌䉺䊷䊮䊍䉾䊃⴫Ṷ▚

䊎䉾䊃ਗ೉ᚻᴺ䈮䉋䉎䌎䌆䌁䈱ᮨ୮

ᾖว⚿ᨐ

䉴䊃䊥䊷䊛

図 ' ビット並列パターン照合の概略





手法の概要

図 ' に，本論文の提案アルゴリズム  の構成を示す．  では，次の # つのフェイズに分けてパター
ン照合を行う．まず時系列パターンの静的コンパイ
ル処理として，与えられた時系列幾何パターン を解析し，含まれるすべての時点幾何パターンを抽出する．時点幾何パターンのクラスにしたがって，ヒッ
ト表計算のための前処理を行う．次に，ビット並列手法に基づく実行時の動的パターン照合処理として，実行時に入力ストリームから入力点を受け取りながら，ヒット表計算手続きを用いて時系列幾何パターンの照合を行う非決定性有限オートマトン  を高速に模倣する．



時系列パターンの静的コンパイル処理 の構築

を幾何制約のクラスとする．初めに最も単純な正規表現の族として，直線状の連続部分列からなるパターン "    £の 67 のクラスを考える．このクラスの 67 は一見単純に見えるが，部分文字列パターンだけでなく，常に真となる空制約  " や選言を用いることで，文字列照合におけるワイルドカードや集合文字に対応したパターン照合 %#) を表現可能であることに注意されたい．





<0>

0

<1>

1

<2>

2

<3>

3

<4>

4

<5>

5

図 $ 長さ $ の時系列幾何パターンに対する 67 与えられた長さ   の時系列幾何パター"       に 対 す る  "  A  Æ  +  , は，図 $ のような  から  までン
の全ての状態を直線状につないだ 67 である．状態  は  で自己に遷移する自己ループをもつ．ここで，各遷移の有向辺のラベル  は， の  番目の幾何制約  を表す．ここに，  " である．



 A は，文字集合        である．
 Æ    A   は遷移関係 Æ "      "            である．
 + は初期状態 + "  である．
 , は受理状態集合 , "  である．

  は，状態集合        である．

ヒット表計算 67 の遷移を行うためには，入力点  によって遷移する辺を決定する必要がある．パターン "        に対して，それが含むの幾何制約すべての集合を  " とおく．このとき，ヒット表   を計算すればよい．



最も単純なヒット表計算の方法は，実行時にストリームの点  を受け取ったときに， 個の制約      全てに対して真理値検査 B  " CD を行うことである．しかし，ひとつの制約 の評価に
時間を要すると仮定すると，この方法ではヒット表計算に  " 
時間を要する．そのため，総計算時間は  時間になってしまう．そこで，次章以降では，種々の幾何制約のクラスに対する高速なヒット表計算の実現方法を与える．

 



 

実行処理

 は実行時には，67  は初期状態  から出発
し，時点  で点  上で真となる時点幾何パターン "  をラベルとする遷移を非決定的に実行することを繰り返し，最終状態  で出現位置    を出力して，照合を模倣する．図  に入力  次元ス
トリーム  上でパターンを照合する 67 を模倣する手続き     を示す．このアルゴリズムは，
状態集合       を長さ  のビットマスク-    で表現し，ヒット表計算によって得られるヒット集合のビットマスク表現  を用いたビット並列計算で高速に照合を行う．図  の状態遷移にあたる行は   時間で処理できる．特にパターン
長が短い（ ）とき，  時間で 67 の遷移を行うことができる．



 





計算モデルとして，レジスタのビット幅  で，数値演算と論理演算を定数時間で実行する 572 %#)を考える．このとき，手続き     の実行時間として次の補題が成り立つ．
補題  図  の手続き     は，時系列幾何パ
ターン に対して， 次元ストリーム上の時系列幾何パターン照合問題を    
 時間で解く．ここで， はヒット表計算に要する時間である．

   Æ          
* *   

入力： 次元ストリーム  " ．
"
出力：パターン の  上の全ての出現+   E
 ,   E
 -  + E       






1 かつ  ならば，   "  
 &   "    &  £ "  £ でもし  ある．
以上で生成されるものだけが 

の要素で定義  言語  を正規表現パターン の展開と呼び，その要素   を展開例と呼ぶ．展開例は上の時系列パターンである．

力するE

例   節の図 - のパターン
単純パターンの例である．



複数パターンのクラス

前節の直線状の 67 のクラスに対するビット並列化を，複数パターン照合問題に拡張できる．パター
ン集合  "      に対して，各パターン
 のマスク   +  ,  - を直列に連結したマスク
 ¼ + ¼  , ¼  -¼ を用いて，各パターン  の 67 の動作の模倣をビット演算により一括して行うことができる．詳細については %#) を参照のこと．



幾何時系列パターンの正規表現への拡張

を幾何制約の任意のクラスとする．有限可変長ギ
ャップ %. /0/) や，省略可能幾何制約 C，繰り返しなどの演算をもつ複雑なパターンは，一般に正規
表現%() の部分クラスとして定義できる． 上の正規表現のクラス  を次のように帰納的に定義する．

 に対して，1   である．
 もし     ならば，      £   である．



"

ヒット表計算： に対するビットマスク  を計算する．

図  67 の模倣手続き   





に対して，1

ある．

 





幾何制約
"
である．



-  -   + ?  E  出現     を出
- ? , " 







        

線形制約



ある．

以上で生成されるものだけが  の要素で定義  上の正規表現幾何時系列パターン（正規表
現パターン）は，正規表現 である．



また，正規表現 の表す幾何時系列パターン 
を の言語 %() として次のように帰納的に定義する．

は， 次元の長さ $ の

定義  正規表現パターン がストリーム  において位置  %  に出現するとは， のある展開例
である幾何時系列パターン   が  において
位置 % に出現することをいう．

例  図 - のパターン は，例 # のストリーム  に位置  と位置 ' で出現する．
ビット並列手法による 67 の模倣は，ヒット表計算の実現とは独立であり，67 のクラスを拡張することで，以下に示すようなさまざまなクラスの正規表現パターンを適用可能である．
有限可変長ギャップをもつパターンは，  " %-)  のような制限された形の正規表現パターンである．ここに，有限ギャップ %% ) は線形制約を満たす任意のレコードの  個から % 個の連続を表す．これは，図  のように，ギャップを最大限に展開した単純パターン ¼ "
    の 67 に 1
遷移 (   . を追加した 67 で模倣できる．ここに，( は  の位置（"#），(  . (  %  とする．ビット演算による遷移計算では，通常の状態 - の遷移の直後に， と %  にだけビット  があるマスク 2+ と 2, を，数値減算 で組み合わせて次のビット並列演算を行い，2+ のビットからのすべての 1 遷移を正しく模倣する．

-  -  2,

- ? 2+?

2, E

これは，例えば，  "  のように，%
番目のビットのみが  のマスクから， % 番目のビットが  のマスクを算術減算すると， から % まで  が伝播することを利用している．

 



<0>

<0>

0

<1>

1

<0>
<2>

表  整数ストリームに対するヒット表

2

<2>

3

<2>

4

<3>

    5

図  有限可変長ギャップをもつパターン  に対す
る 67
さらにこの減算を用いた 1 遷移の実現技法を用いて，  "   C  のような省略可能幾何制約をもつパターンや，  "   £  のような幾何制約の繰り返しパターンを，ビット並列手法で扱うことができる．模倣技法の詳細については， %#) を参照のこと．



１次元ストリームに対する効率よい











-



$

-



'

#-'



-

#-'



#

#'$





#'$



例  次の不等式制約集合  を考える．

ヒット表計算本節では， 次元実数ストリーム上の時系列パターン照合問題を考察する．- # # 節の  時間のヒット表計算を用いた素朴な時系列パターン照合アルゴ
リズムでは，総計算時間が  時間になる．そのため，本節では  次元実数ストリーム上の不等式の論理積で表される幾何制約のクラス   に対して、二分探索を用いた    !  時間のヒット
表計算アルゴリズムを与える．さらに、 次元実数
ストリーム上のクラス   に対して、表一瞥方式を用いた   時間のヒット表計算アルゴリズム
を与える．



" 

#

 "

$

 "

#

 "

$

 "

-









このとき，表  に，値の集合 F "       に対するヒット表をあらかじめ計算したものを示す．各欄は順に，値  と， が満たすヒット集合   ，そのビットマスク表現   である．ただし，簡単のため   #  - を #- のように表記する．

     

手続き   は，幾何制約のクラス
  に対して，制約集合  に対するヒット表計算問題を，前処理時間   と領域   を用いて，各入力点  Æ  個あたり，   時間で解く．ここに， "  は， のサイズである．
定理



整数ストリームに対するヒット表の構築

図  に，クラス   に対する， 次元整数ストリーム上のヒット表計算アルゴリズム   を与える．
前処理では， 次元整数ストリームに対して，とりうる全ての値  に対して，あらかじめヒット表  
を計算しておく．具体的には，値の集合 F " 上の全ての値  に対して，あらかじめヒット集合       を表すビットマスク
 
 を計算し，ビットマスク配列
 %) "  %)      %)      に格納しておく．実行時には，配列の添字によるランダムアク
セスによって，ヒット表を表すビットマスクを取り
出す．

 


 
  

 


 

補題 # から，次の系がただちに成立する．
系
幾何制約のクラス   上に対して， 次元
実数ストリーム上の幾何時系列パターン照合問題
は，前処理時間   と領域   を用いて，
  時間で解ける．  "は，パターンのサイズであり， "  はストリーム  の長さで
ある．

 

 

   Æ           ：ビット マ ス ク 配 列    %)      %)

入力：制約集合  & 値の集合 F．
出 力：ビット マ ス ク 配算       % )   E
       





 



列

の

計

入力：制約集合  ．
出力：ビットマスク配列の計算
 のすべての線形不等式の端点を，数直線  上 上のすべての端点と極小開区間に対してビッにプロットする．

"    % )   % )  E

トマスクを計算し，表 # のようなヒット表の配列を構築する．この配列の要素は，端点の昇順にソートする．



GG実行時手続き

 %)      %)    F  ：ビット マ ス ク 配 列    % )GG前処理手続き

GG前処理手続き        (  GG実行時手続き



入力：F "   上の点  " Æ ．
出力：入力点  " に対するビットマスク  % )   % )    E



入力： 次元実数空間上上の点  "Ê．
出 力：入 力 点  "に 対 す る ビット マ ス ク

% ) を含む区間を配列から二分探索し，対応するビットマスク  を見つける．
       E 入力点

図  整数ストリームに対するヒット表計算アルゴ
リズム  

実数ストリームに対するヒット表の構築

図 ( に，クラス   に対する， 次元実数ストリーム上のヒット表計算アルゴリズム   を与える．実数ストリームのとりうる値は無限集合であるため先の手法が使えない．そこで，次の方法を
用いる．

 

初めに，先の図  のように， が含む総計個の線形不等式 & "  の端点  をすべて数直線  上にプロットする．このとき，次が成立する．
補題  任意の線形制約 を充足する値の集合は 上の端点と極小開区間の集合和として一意に表現できる．
証明 上の端点と極小開区間の集合和のうち，どの区間も，その区間内で満足される制約は同じである．よって補題が成り立つ．
¾
これより，節 '  がすべての値に対するビットマ
スクを計算したのと同様に，あらかじめ  上のすべ

図 ( 実数ストリームに対するヒット表計算アルゴ
リズム  ての端点と極小開区間に対してビットマスクを計算
し，表 # のようなヒット表を構築する．実行時に，入力点  Ê が含まれる区間をこの表から探索することで， に対応するビットマスク   を計算できる．

例  例  の不等式制約集合  に対して，図  に，
 のすべての不等式制約をプロットしたものを示す．この図では，数直線  がすべての端点と極小開区間に分割されていることがわかる．表 # に，すべての端点と極小開区間に対するヒット表をあらかじめ計算したものを示す．各欄は順に，端点または極小開区間の値  と， が満たすヒット集合   ，そのビットマスク表現   である．ただし，簡単のため   #  - を #- のように表記する．

     

 は高々  個の端点と極小開区間しか持たない 

y

表 # 実数ストリームに対するヒット表



 
 " $   " $-  $ " #   " #
 #

 

 









-



-



#-'



#-'



#-'$



#'$



#'$



q0y

q0

q2y

q2
q0x

q1x



q3

x

q2x

軸と  軸に分離された多次元ストリームに対する効率よい
ヒット表計算：次元間に相関のない

q2 =q45q1

図  軸平行な幾何制約と
制約

q1
7

q1y

幾何制約の場合3q5

2

図  制約集合  の数直線上の表現
ので，節 '  と同様の議論で，計算量は次のようになる．
定理  手 続 き   は ，幾 何 制 約 の ク ラ ス
  に対して，制約集合  に対するヒット表計算問題を，前処理時間   と領域   を用いて，各入力点  Ê  個あたり，    ! 
時間で解く．ここに， "  は， のサイズで
ある．



 

補題 # から，次の系がただちに成立する．
系  幾何制約のクラス   上に対して，  次
元実数ストリーム上の幾何時系列パターン照合問題
は，前処理時間   と領域   を用いて，
   !  時間で解ける． "は，パター
ン のサイズであり，  "  はストリーム  の長
さである．

 

 

本章では，ストリームを  次元に拡張し， 次元
実数ストリーム上の時系列パターン照合問題を考察する．クラス   上の，パターンが次元間に相関のない制約からなる場合のヒット表計算アルゴリ
ズムを与える．説明の簡便のため，入力点の空間として # 次元実数空間 Ê  を考える．

前章の手法を  次元ストリームに単純に適用すると， に関して指数サイズの領域のビットマスクを要する．そこで，次元間に相関がない制約に特化した手法を与える．



変数分離形のパターン



制約 中の線形不等式 &  がすべて各次元間に相関のない制約 & " ' であるとき，
変数分離形であるという．ここに，
%  である．即ち， & "  であり， " # 次元空間上では，
図  のように 軸または  軸に平行な直線からなる制約である．変数分離形の制約のみからなるパター
ンを変数分離形のパターンという．

 



変数分離形のパターンに対するヒット表
計算

図 # に，変数分離形のヒット表計算アルゴリズム
  を与える．幾何制約集合で用いられる線

   Æ          
* *  "     Ê   ' 上で  座標 に関する探索を行い， を含む垂直な帯状の領域
   *   を見つける．
 端点のリスト     上で , 座標  に関する探索を行い， を含む水平な帯状の領域   % 3   を見つける．
 それぞれのビットマスク  と  を取り出す．
    "  ?     E
 端点のリスト'

図 #   のヒット表計算
形制約が変数分離形の制約のみで定められる場合には，図  のように，軸平行な幾何制約集合 .
を 軸と  軸に平行な制約からなる部分集合に分離し，各次元毎に前処理を行い，実行時に入力点  "      に対して各次元のヒット表の論理積を求めることで扱える．これは，ヒット表のビットマ
スク表現のビット積   "  &   で高速に求めることができる．これにより，ビットマスクの検索処理の著しい簡素化と高速化が可能である．







まず，. 中の線形不等式で  軸に平行なもの（垂直線）の全体を考える．これらの垂直線全体
を 座標で昇順にソートしたリストを 4 " 5 '  5   とおく．次に，これらの垂直線を用いて，平面 Ê  を互いに交わらない，垂直
な帯状の領域 Ê  "    に分割する．各領域  
 * に，その領域との共通部分が存在する制約   すべての集合を表すビットマスク
   を関連付ける．同様に， 軸に平行な直線（水平線）の全体を用いて，互いに交わらない
水平な帯状の領域 Ê "    に平面 Ê を

分割し，各領域  
% 3 に，それを満たす

制約集合を表すビットマスク 
 
を関連付
ける．











 





算問題を，前処理時間   と領域   を用いて，各入力点  Ê  個あたり，    ! 
時間で解く．ここに， "  は， のサイズである．

て， 座標と , 座標それぞれに対して領域のリスト
上の探索を行い，それぞれに対応づけられたビット
マスクをビット積で結合したものを返す．
各次元に 個の制約が含まれているとする．各次
元に関して，  のリストを探索してビットマスクを返すので，変数分離形のアルゴリズムの計算量は次のようになる．
定理  手 続 き   は ，幾 何 制 約 の ク ラ ス  に対して，制約集合  に対するヒット表計 

補題 # から，次の系がただちに成立する．
系  幾何制約のクラス   上に対して，  次
元実数ストリーム上の次元間に相関のない幾何時系
列パターン照合問題は，前処理時間   と領域   を用いて，    !  時間で解く．
 " は，パターン のサイズであり，  " 
はストリーム  の長さである．

 



 

変数分離形でない制約集合への適用'    というような変数分離形でない制約は，新しい仮想的な変数 " '   を各時点で計算することで，変数分離形の制約
 に帰着することができる．また，変数の前の値との比較67 のような制約についても，変数 "67 の導入によって実現できる．



まとめ

本節で述べた変数分離形の場合のヒット表計算は，
 - の場合にもそのまま適用できる．これは次章で述べるスラブ法と比べて，構造と前処理の簡単さに利点がある．とくに，- 次元以上の高次元データの場合に有利である．



多次元ストリームに対する効率よい
ヒット表計算：次元間に相関のある
幾何制約の場合   は，与えられた入力点  "    に対し

        

本節では，複数次元間に相関がある場合のクラス の幾何制約集合に対するヒット表計算の効率良いアルゴリズムを与える．



手法の概要

議論の簡便のため，入力点の空間として # 次元実数空間 Ê を考える．いま，# 次元平面 Ê 上の線形幾
何制約の集合  "         が与えられたと仮定する．以後， 中に含まれるすべての線形不等式からなる集合を .
 で表し，その総数
を  " . で表す．すなわち，  " 
である．







 



 

 #

GG実 行 時 手 続 きÊ





"

 E

         &  & "       







Ͱ2 y

R0,6

Ͱ1

R0,4

R2,6

R4,6

R6,6

R2,4

R4,4

R6,4




 
 
    E



 E



R0,2

R4,2

図 - 素朴な方法によるヒット表計算アルゴリズム




Ͱ3
R0,0

R2,0

R4,0

S0

S1 S2 S3

S4

素朴な方法

素朴な方法として，前処理を行わず，入力が与えられるたびに，集合  の制約を逐次的に評価する方法が考えられる．図  に，素朴なヒット表計算手続き
 を示す．
定理  手続き 
は，幾何制約のクラス
 に対して，制約集合  に対するヒット表計算問題を，前処理時間  と領域  を用いて，各入力点  Ê  個あたり，  時間で解く．ここに， "  は， のサイズである．


 

補題 # から，次の系がただちに成立する．
系  幾何制約のクラス  上に対して， 次
元実数ストリーム上の次元間に相関のない幾何時
系列パターン照合問題は，手続き 
を
用いて前処理時間 
と領域 
で，   !  時間で解ける．ここに，  "はパターン のサイズであり， "  はストリーム  の長さである．

 



R2,2

 

スラブ法

本節では，スラブ法を用いたヒット表計算アルゴリ
ズム   を与える．スラブ法は，あらかじめ前
処理でビットマスクを計算しておき，入力毎のビッ
トマスクを表引きで高速化する方法である．アルゴ
リズム   は，時点幾何パターン集合  が与えられると，次のように前処理を行う．

R6,2
R6,0
S5

S6 x

図 ' スラブ法：帯状領域と台形領域
前処理 初めに，. 中のすべての線形不等式
から二つずつとった組み合わせ &  &. を考えて，それらの交点 && 全体の集合 +  "& & &  & .Ê を求める．次に交点の 座標を
 と昇順にソートして並べる．これらの点を通って  軸に平行な直線（垂直線）を引いて区切り，平面 Ê  を互いに交わらない垂直な帯状の領域と，垂直線のみからなる領域 Ê "    に分割する．ここに，  * に対して，# 番目の帯は  "    Ê であり，#   番目の帯は " %   ) Ê である．
ただし，  "  "  と定義する．

  

















各  "      #* に対して，垂直な帯  と，を横切る . のすべての直線を考える．  を横切る直線で区切り，台形領域と，直線のみからなる領域  " 8  
 8  に分割する．  の内部ではどの . の直線も交わらないので，台形
領域 8       8  は  軸の向きに一意に順序づけることができる．各台形領域 8 の内部では明らかに満足される制約は同じなので，各 8 に，満足される制約 
 すべての集合を表すビットマスク
   を関連付ける．図 ' に，- つの線形
制約 &      & による帯状領域と台形領域の分割を
示す．



 



検索処理 図  - に，スラブ法を用いて実行時に入力点に対するビットマスクを計算する手続きを与える．このアルゴリズムは，入力点  "    が与えられると， 座標に関して二分探索を行い， を   Æ          
* *

! .> /H

Ê

"







座標
    に関する二分探索を行い，
 を含む帯状の領域    #* を見つける．
  に含まれる台形領域に関する二分探索を行い，
 を含む台形領域 8  % #3 を見つける．
       E

        -

y
NΔ



R1,N

…

RN,N

…

RN,1

図 $ スラブ法におけるヒット表の計算

定理  手続き   は，幾何制約のクラス
 に対して，制約集合  に対するヒット表計算問題を，前処理時間   と領域   を用いて，各入力点  Ê  個あたり，    ! 
時間で解く．ここに， "  は， のサイズで
ある．



 

補題 # から，次の系がただちに成立する．
系  幾何制約のクラス  上に対して， 次元実数ストリーム上の次元間に相関のない幾何時系列パ
ターン照合問題は，手続き   を用いて前処
理時間   と領域   で，    ! 
時間で解ける．ここに， "はパターン のサイズであり， "  はストリーム  の長さである．

 

 

これは素朴な場合に比べて，指数的なスピード
アップである．



次元が  - の高次元データの場合にも，再帰的な拡張でスラブ法を適用可能である．しかし，索引
構造の複雑さから，実際には  # が実用的だと思
われる．



バケット法

実際的な高速化技法として，式の定数や交点の座標が，微小長さ F Ê を単位として離散化されてお



Δ

…

計算量 集合 . 中の  本の直線の交点数は最大で，9 "   箇所なので，領域の数 * 3 は高々9で抑えられる．計２回の  ! 9 "  !  時間の二分探索を行うので，計算量は次のようになる．

…

含む帯状の領域  を見つける．次に， の内部を
 座標に関して二分探索を行い， を含む台形領域
8 を見つける．最後に，台形領域 8 に対応づけられたビットマスクを返す．

R1,1

NΔ x

Δ
図  バケット法

り，入力値が上下限をもつ有限な実数区間 %' ) Êから与えられる場合が重要である．この場合は，ス
ラブ法における二分探索を行わず， # 次元配列上のバケットを用いた表引きによる高速化が可能である．
本節では，バケット法を用いたヒット表計算アルゴ
リズム  を与える．
本節で述べる手法は，'  節の  次元整数ストリー
ムのヒット表計算を， 次元実数ストリームへ拡張した手法と考えることができる．



問 合 せ 可 能 な 領 域 を %F  F%F  FÊ とする．# 次元配列 %  )上に，一辺が F の直方体状の小領域 8 " %F F%%F % F を表すバケット % % )  %  を配置する．その小領域 8 上で満足される制約集合   を表すビットマスク  
をバケットに直接格納する．直線がバケットを斜めに横断する場合には， を検索後に個々の制約を順に検査する事後チェックが必要である．
前処理







 

検索処理 図  ' に，実行時に入力点に対するビッ
トマスクを計算する手続きを示す． は，
入力点  "    が与えられると，  ":F と% " :F に対して，バケット % % ) を直接表引き
し，関連付けられたビットマスク 
 
を
返す．

 

 '

* *    "     Ê " :F E
 % " :F E
 バケット % % ) を直接表引きするE
 関連付けられたビットマスク     を


返す．



実験

本節では，提案アルゴリズムするための計算機実験を行う．

 の性能を評価

実験１' 章の  次元実数ストリームと  次元整数ストリー

図  バケット法におけるヒット表の計算

ムに対するアルゴリズムと， $ 章の変数分離形に対するアルゴリズムの性能を評価する実験を行った．

計算量実験  では，以下に示される  種類のアルゴリズ
ムを I言語で実装し用いた．

定理  手続き  は，幾何制約のクラス
 に対して，制約集合  に対するヒット表計算
問題を，前処理時間     と領域    を用いて，各入力点  Ê   個あたり，   
時間で解く．ここに， "  は， のサイズ，
は事後チェックに要する時間である．



 

 時間の素朴なパターン照合アル
ゴリズム %#) の実数ストリーム版．

!"#$

%$ 12 手法 %) の実数ストリーム版である.* %) と /* ら %-) の 4#5 アルゴリズ

ムの実装．
補題 # から，次の系がただちに成立する．
系  幾何制約のクラス  上に対して， 次元実数ストリーム上の次元間に相関のない幾何時系列パ
ターン照合問題は，手続き  を用いて前処理時間     と領域     で，   時間で解ける．ここに， " は，パターンのサイズであり， はバケットの分割数， " 
はストリーム  の長さ， は事後チェックに要する時間である．

   の時間計算量は理論的には  だが，ランダ
ムな制約データの場合は定数とみなせると期待できる．また，事後チェックを行わないことで， " となる近似的なパターン照合の実装とすることがで
きる．


まとめ

本節では，一般的な線形制約に対する高速なヒット
表計算のアルゴリズムとして，バケット法とスラブ法を与えた．バケット法はスラブ法と比べて，# 次
元空間上で検索領域が離散的かつ有界な場合に，構造の簡単さと検索速度で著しい利点がある．一方で，- 次元以上の高次元では，データが疎になりほとん
どのバケットが無駄になることから実用性は低いと思われる．

%$ 32 手法 %-) の実数ストリーム版である.* %) の 5#4 アルゴリズムの実装．

&'  $ ' 章の   を用いた 3/ アルゴ
リズムで，ヒット表計算を配列上の二分探索 %)で行うもの．
' 章の   の二分探索を線形探
索 %) に置き換えた 3/ アルゴリズム．

&'  $' 章の   を用いた整数スト
リームに対する 3/ アルゴリズムで，ヒット表計算を表引きで実現したもの．

&' $  次元の実験については，   &   &  を $ と同様の議論で  次元に拡張したアルゴリズム    &    &    をそれぞれ代替として用いた．



データ   " % )
Æ  上の一様分布
で独立に生成した  個の  次元上の点からなるスト
リームデータ  と，ランダムパターン "
を用いた．ここにパラメータ 
1  に対して，
独立なランダム整数 '% 1) に対し，  "



' 
*
*    かつ * " '  1 ととった．とくに指定しない限り， "  とし， "   "    " - とした．

 



  

   Æ                  $
NAÏVE
L2R
R 2L
B P S _bin
B P S _lin
B P S _tab

2

2

R 2L
BP S _lin
BP S _tab

T ime (s ec)

T ime (s ec)

1.5
1
0.5

1.5
1
0.5

0
0

5000000

100000000

L ength of Data

0

2

4
6
Length of P attern810

図  データサイズと計算時間
図 ( パターン長と計算時間

 

 

実験結果

5

NAÏV E
L2R
R 2L

4
T ime (s ec)

方 法 実 験  は ，I（  2
 -J.K，レジスタ長 -#H ，572 J3，I,!L，!- ' '）上で行った．パラメータを変えて生成したストリームデータに対して，各アルゴリズムの計
算時間を計測した．ストリームデータは主記憶上に読み込み実験を行った．計算時間には，データの読み込み時間は含めていない．

B P S _bin
B P S _lin

3

B P S _tab

2
1
0
0

データサイズに対する規模耐性． データサイズ に対するアルゴリズムの規模耐性を評価するため，

5#4 と，3/ ，3/ H に対して，  を  個から  個まで変化させて，それぞれの計算時間を測定した．計算時間は - 回の平均である．結果を図  に示す．3/ アルゴリズムの計算時間は  に比例し，- - 節の定理 # から予測されるふるまいと整合する．具体的には， "  "    のとき，3/ H の計算時間は   秒程度であり，十分高速だった．
パターン長と計算時間． パターン長  の変化に対するふるまいを評価するため，実装した  つのアルゴリズムに対して，  を  から  まで変化させたときの計算時間を測定した．計算時間は - 回の平均である．結果を図 ( に示す．3/ H の計算
時間は， の値によらず   秒前後であり， つのアルゴリズムの中で最も高速であった．67=M と，
4#5，5#4 の計算時間はパターン長によらず  $ 秒
前後で一定だった．3/  は， ' では 67=M
と，4#5，5#4 より高速だったが， $ ではこれ
らのアルゴリズムより低速だった．3/ H は，同様の傾向を持つがより低速だった．



&'  のデータ幅に対する耐性． 整数ストリー
ムに対するアルゴリズム 3/H は，ストリームの

4

8

12
16
R ange of Data

20

24

図 # データ幅と計算時間
値域  に比例するサイズのマスク配列を用いるため，
 が大きい場合の有効性は未知である．そこで，パターンの相対幅 / " #$N を一定に保ったまま，
を # "  から # "   # まで変化させて計算時間を測定した．結果を図 # に示す． ビット整数程度のデータ幅までは，3/ H は他のアルゴ
リズムの # $ 倍高速であり，十分使用に耐えることがわかった．
複数パターン照合． - つの 3/ アルゴリズムを複数パターン照合へ拡張し（- ' 節参照），パターン
数 . を  から  まで変化させて計算時間を測定した．
67=M と，4#5，5#4 は複数パターンへの拡張が自明でないため，各パターンの照合にかかった計算
時間の和を用いた．結果を図 # に示す．3/ H の計算時間は，パターン数によらず一定で，  秒程度だった．3/ H と 3/  の計算時間は，パターン数の増加にともない増加したものの， . # では，
67=M と，4#5，5#4 よりも高速だった．たとえば，パターン数  では，5#4 と比較して，3/ Hは  倍程度，3/ H と 3/  は # $ 倍程度高速
であった．



 



12NAÏV E

10

R 2L

8

B P S _bin

6

B P S _lin

Time (s ec)

T ime (s ec)

4

B P S _tab

4
2
0
0

4

3
2
1

1

4

5

6

7

8



1
R ange of P attern
003' では 3/  が，
$ では 4#5
しては，
や 5#4 が高速だった．また，3/ アルゴリズムはパターンの内容によらず比較的安定した性能であった．

Naïve
L2R
R 2L
d-B P S _bin
d-B P S _lin
d-B P S _tab22

図 #- 次元数  に対する計算時間

図 # パターン数と計算時間

3

Number of Variables

08

Number of P attern

Time (s ec)

Naïve
L2R
R 2L
d-B P S _bin
d-B P S _lin
d-B P S _tab

L2R

10 20 30 40 50 60 70 80 90

図 ## パターン幅 1 に対する計算時間

パターン幅に対する計算時間． パターンに対する依存性を知るために，1 を  から ( まで変化させてたときの各アルゴリズムの計算時間を測定した．計
算時間は - 回の平均である． " - とした．結果を
図 ## に示す． 3/ H と， 3/ ， 3/ H
の計算時間は相対幅によらず安定して高速だった．
一方，67=M と& 4#5，5#4 の計算時間は，相対幅の増加にともない - 倍程度増加した．たとえば，
1 " N のとき， 3/ H と  3/  はそれ
ぞれ，67=M と& 4#5，5#4 と比較して ' 倍と # 倍程度高速であった．

 に対する計算時間． 図 #- に， を  から  まで変化させたときの各アルゴリズムの計算時間を示す．
 " ' とした．次元  によらず制約が空間 8 を満たす体積を一定割合 ; " #$ とするため，1 " ; とした．全アルゴリズムの計算時間は  に比例し，とくに，   は他のアルゴリズムと比較して#$ 倍程度高速だった．
 程度の整数ストリームで実験のまとめ． #
は 3/ H が最も高速だった．実数ストリームに対

実験２

 章の， 次元空間上の線形制約クラスの時系列
幾何パターンを扱うためのヒット表計算の実行速度を比較するため，合成データ上で実験を行った．こ
こでは，節 # ' - の例 ' で述べたような凸多角形からなるパターンに対応するヒット表構築アルゴリズ
ムを，自明なアルゴリズム 
と& スラブ法を用いたアルゴリズム  ，バケット法を用いたアルゴリズム  として実装した．なお，今回実験で用いた  は，ひとつのバケット内に複数の領域がある場合の事後チェックを行わない簡易な実装である．また，バケットの分割
は $# $# とした．



実験 # は，I（I * # 9 ># # J.K，レ
ジスタ長 -#H ，572 J3，MI #）上
で行った．



データ





二次元平面 8 " % ) % ) Ê 上にランダムに生成した 7 "  個の点       
8 に対する凸包を計算した．図 #' に凸包の例を示す．生成した
凸包を  個連結したものを長さ  のパターンとした．ランダムに生成した # 次元座標上の長さ  の点
列  "      
8£ を # 次元実数ストリームと
した．





   Æ                  

3000

y

d-HT-naived-HT-s lab
d-HT-bucket

2500

Time (ms ec)

1

2000
1500
1000
500
0

4

0

8

P attern length

図 #$ パターン長に対する計算時間

0
0

1

x

図 #' ランダムな 7 点の凸包



方法

生成したパターンに対応するヒット表を，各アルゴ
リズムを用いて構築した．これらのヒット表に対して点列を入力として与え，ビットマスクを計算するために必要とした総計算時間を計測した．



実験結果

パターン長  を  から  まで変化させたときの各ア
ルゴリズムの計算時間を図 #$ に示す．
の計算時間は  に比例して増大した．  の計算時間は  が大きくなるにつれ対数的に増大したものの， " ' で 
に比べて ' 倍程度高速であった． の計算時間は  の値に関わらず一定であり， " ' で 
に比べて #$
倍程度高速であった．これらの振舞いは， 章で述べた計算量に合致している．また， が事後チェックを行わないことにより誤ったビットマ
スクを返す割合を調べたところ，  " ' 7 "  のとき $N 程度であった．



次元実数ストリーム上の時系列パ
ターン照合のモーション検索への応用

本節では，アルゴリズム  の実データへの応用実験として，モーションデータからの検索実験を
行う．



データ

モ ー ション デ ー タ と し て ，   GG
LLL      で HO 形式で公開されている歩行モーションデータ L  * K HOを用いた．
今回データに用いた HO 形式は，スケルトン階
層記述部と各関節のモーションデータ記述部からなるファイル形式である．スケルトン階層記述部には，モデルの関節と関節間の長さが階層構造で記述されている．モーションデータ記述部には，各時点での姿勢が，各関節について - 次元の絶対座標と - 次元の回転角による相対座標の計  次元データで記述されている．
モ ー ション デ ー タ ファイ ル L  *のスケルトン階層記述部の一部抜粋を
図 # に，モーションデータ記述部の一部抜粋を
図 # にそれぞれ示す．L  * K HO では，腰を根とした ( 関節の木構造で人体モデルを記述している．このモーションデータは，$ 歩程度
歩いて  度方向転換することを # 往復繰り返した
動きのデータである．
K HO

今回の実験では，( 関節 ' 次元の実数ストリー
ムのうち，*
関節と絶対座標の次元を除いた $' 次
元を用いた．これは，人体モデルが同様の姿勢をとっていれば絶対座標や向きに関わらずマッチする結果を意図したためである．
パターンとして，モーションデータの時点  " #から切り出した長さ  "  の  " $' 次元ストリーム  %   ) に区間幅を加え，各次元の制約がすべて論理積で結合した変数分離形のパターン"
 を用いた．すなわち，制約  "**     であり，各次元について，* " 
 %)  1 :#  %) 1 :# である．









 

              $ %&  '%'           $ %&( %%

! 

 

! 

 

!"# "# 

!"# "#  '%' ' '%'           !    !"# $ %& )*%

,
,
$

,



"# "#  '%' ' '%'           !    !"# 
 +  %,

"# "# "# "#  '  -.

 ' '%'           $  -.( %%

! 

 

!"# "#  '%' ' '%'           !    !"# $  -. )*% %' ' '%'           !    !"# 
 +  %,

"# "# "# "# "#  ' 

図 # HO 形式のスケルトン階層記述部 抜粋
ただし， %) は  の  番目の要素とする．また 1 は% 番目の次元に定めた区間幅である．今回の実験では，% 番目の次元のストリーム上の最大値と最小値の差 6'07 とパラメータ / を用いて 1 " 6'07/とした．これは各次元がとりうる値の幅を考慮して区間幅を加えるためである．





方法

パターンを L  * K HO から生成し，L  * K HO
をストリームとして，    を用いて照合を行った．/ を  から$ ずつ大きくしていき，どのような検索結果が得られるか観察した．また，照合にかかった計算時間を測定した．
今回の実験を行うにあたって，  の JP= を実装した．概観を図 # に示す．各部位の説明は次の
とおり．
 

パターンのプレビュー画面

# 

モデルの関節リスト

- ストリームのプレビュー画面/ 
"#0% 1 
"#0%0%1 
  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   %'   ' ' '   %'  ' ' '   %'   ' ' '   %'  ' ' '   %'   ' ' '   %'  ' ' '   %'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'  ' ' '   %'  ' ' '   %'  ' ' '   %'  ' ' '   '%'  ' ' '   '%'  ' ' '   '%'

図 # HO 形式のモーションデータ記述部 抜粋
' 

照合結果

$ 

パターンの始点  を指定するスクロールバー 

パラメータ / の入力部

 

パターン長  の入力部

 

検索ボタン

( 

アニメーションの再生・停止ボタン

パターンとストリームとして，それぞれ HO ファ
イルを読み込み，パターンのパラメータ  と，/，
を JP= で指定できる実装となっている．また，パターンと照合結果の動きをアニメーションで確認で
きる．



結果

目視によれば，このストリーム中に，パターン
図 #( と似た動きは 自身を含め ( 箇所に存在した．/ を  から  -$ 照合結果を表 - に示す．ここに， に似た ( 箇所の動きを時系列順に       とする．また， に似ていないと判断される動きを時系列順に      とする．

   Æ          
(1)        (

表 - パラメータ / に対する照合結果

(3)

照合結果
(4)
(2)

(5)
(6)
(7)
(8)

 


 
 






                                                              

(9)

図 # 3/ の JP= 概観

おわりに

本論文では，文字列アルゴリズムにおけるビット
並列手法を，  次元実数ストリーム上のパターン照合問題に適用し，幾何的制約による複雑な時系列パ
ターンを照合する問題を考察した．また，この照合問題のために，複数の幾何制約問合せを高速に計算するヒット表計算の手法を示し，それらとビット並列手法を組み合わせる機構を提案した．特に制約条
件が軸並行の場合に対して，変数分離法というビッ
ト並列による高速な問合せ解決手法を提案し，これを用いて照合問題を実際に高速に解くアルゴリズムを導いた．提案手法は今後のビット幅の拡大に比例した高速化が期待できる．

(a)

(b)

(c)

図 #(  パターン
失敗例



H

照合の成功例  照合の/ "   の間では，  そのものしか得られなかった．/ " $ のとき， に似た動き  図 #(
Hが検索結果として得られた．/ " -$ まで引き上げた段階で ( 箇所すべてが結果として得られた．
しかし，同時に # 箇所の似ていない動き 図 #( が結果として得られた．
また計算時間は，ファイルからの読み込み時間を含めないで  " ' のモーションデータで $
程度だった．これは十分実用的な速度であると考えられる．

主結果として， 次元整数ストリームに対して，
 時間 の 67=M 手法より高速な  時間アルゴリズムを与えた．また， 次元実数ストリー
ムに対して，    !  時間アルゴリズムを与えた．ここに，   はそれぞれ，パターン長と，ストリーム長，マシンレジスタ長である．とくに  のときは前者は  時間アルゴリズムとなり，現行の  " -# * ' ビットのハードウェア上で実用的である．
加えて，変数分離形の  次元実数ストリームに対して，    !  時間の照合アルゴリズムを与えた．また， " # 次元実数ストリームに対して   !  時間の照合アルゴリズムを与えた．ここに， はパターンサイズである．
今後の課題として，より一般的な制約への拡張や，より柔軟な正規表現パターンへの拡張が挙げられる．
実数データストリームからのオンラインマイニングへの拡張も興味深い課題である %#)．また，モーションデータの検索実験では，正しい照合結果と共に，意図しない照合結果も得られた．より尤もらしい照合結果を得るための手法が必要と考えられる．また，動きの大きく違うモーションデータに対する照合実 

#験など，より深い観察が課題として挙げられる．モーションデータの他にも，センサーデータストリームの監視問題や蛋白質の三次元構造に対する検索などの実データに対する応用が今後の課題として挙げられる．

I*   *  :%$) 2%) 4 .*& I  > *  

喜田拓也先生には，研究のきっかけとなった講義をしていただいたことをはじめ，論文指導や研究議論の面でも大変お世話になりました．ここに厚く感謝いたします．
研究補助員の南野香子さんには日頃から数多くのサポートをしていただき，本当にお世話になりまし
た．ありがとうございます．

O* I    9  / *& * 

.*&*H 9 %) 9  1


*

2  !

/ *&O* 2 * "#$% &また，大学院修士課程に進学させてくれた両親に感謝します．最後に，執筆中に逝去した祖父に，この論文を捧げます．

& Q. * 8

 Q

9

7&

.

7**&1

7H& / 7*L& < 7! *

/

%)

2

 & /
/

3 ,*  Q

I*,&

P/2*& 7 2

I I O,& / 4& J /& 2 /6 > H  / 0 & 2 
7 6L I & * 

H**&*! / *

8 9  2!  & #$R##& ##7

3H& 2

7*& 39 *& J

2& I

3H
<



  9  / * 2!

* 

$(& #6O**

 2  +

"

5Æ

&

&

/, &)! * # IH*! PO* , *& ##/*&

I

0  &7

20*

Q 7H& < K  

8 /+ T* 9 H /, & * #,"& 7I2& R

& #
%') > /
7! *

& > 1  . 7**& 7 Æ 8 * I  

* 2  !

I    9  / * 32

& *  3O*

*

"',-& =& -R& #%$)

斉藤，喜田，有村& ビット並列手法に基づく大規模連続ストリームパターン照合& 第  回情報科
学技術フォーラム講演論文集 =># & 情報処
理学会・電子情報通信学会& 9 (& #%)

斉藤，喜田，有村& ビット並列手法に基づく効率
良い時系列パターン照合機構と多次元データス
トリーム処理への応用& 第 ( 回データ工学ワー
クショップ 9:/# & 電子情報通信学会・日本データベース学会&  & #/ *!

I *&: & 7

& Q 5    5 M*& T*, *%#) J& & #R#& (I  &L& Q!& 7*   &  5 * 2!

#R-'& ##/* ! 7! *森川，浅井，有村& データストリーム処理のための効率良い S 問合せ機構& *   '"(&%) 5

1L  &&"

/ *!&#R#& #- 8 * 2!

/  * * 9  / *& *  M 5 *



(

P&        & 7  :,& ('2  !

       & *  .&参考文献
7& Q . 2 ** Q*
*%() . 5 4L  I .  * & %%-) 5M& & -#-R-$& (トーマス・ツォイクマン先生と湊真一先生には本研究に関して貴重なコメントをいただきました．ここに感謝いたします．

%') 9* 9 

46I/ #'& R(-& ##

今回，この研究をする機会を与えてくださり，夜遅くまで議論に付き合っていただいた有村博紀先生に深く感謝いたします．修士課程で執筆した論文はすべて先生の厚い助力があってこそでした．

%-) 5

!  " & 'R''& ##

謝辞

%#) >

*&

 & <8 * PO* , *& (('

%) 4

%) 7

5,

   Æ          
%)斉藤，喜田，有村& 連続データストリームに対するビット並列手法を用いた高度な時系列パ
ターン照合& 第  回データ工学ワークショップ
9:/# & 電子情報通信学会・日本データベース学会& I (& #%) J7/  &"" +  &: * / U& (('%() 2 /H**  P I  & D< /K  7D 7 = :J & * %#) V > . I  

%.& #R& #$: H  .

1 !L& 7 2  I    T*, < K   23

 T*,    * ")/& ''-R'$& #'

* 7,&        #