master.dvi

全文

(1) .

(2) . . Æ

(3)

(4) .

(5) .

(6)

(7) .

(8) .

(9)

(10)

(11) . . . . .

(12)

(13) 修士論文：ビット並列手法に基づく高度な時系列パターン照合アルゴリズム斉藤智哉北海道大学大学院情報科学研究科コンピュータサイエンス専攻札幌市北区北条西丁目. . 概要本論文では，多次元実数ストリームに対する複雑な時系列パターンの照合問題に取り組む．ここで，時系列パターンは幾何的制約の時系列として表現され，ストリーム中でその制約の列が満たされるすべての位置を計算する問題である．幾何的に表現された時系列パターンの高速な照合のために，複数の幾何制約問合せの静的コンパイルとビット並列手法を組み合わせた機構を提案する．主結果として，次元整数ストリーム上の時系列パターン照合問題を時間で，次元実数ストリーム上の次元間に相関の無い時系列パターン照合問題を ! 時間で， " # 次元実数ストリーム上の時系列パターン照合問題を ! 時間で解くアルゴリズムをそれぞれ与える．ここで，はそれぞれ，パターン長と，パターンサイズ，ストリーム長，マシンレジスタ長である．また，計算機実験を行い，既存手法を単純に拡張した場合に比べて $ $ 倍程度高速に動作することを確認した．. . 図. . . 連続データストリームに対するクエリ照合. 研究目的. 本論文では，連続データストリームに対して時系列パターンによる問合せが与えられる，プッシュ型ストリーム処理について考察する．すなわち，クエリが初めに与えられ，それを処理する機構に多次元の数値データが絶え間なく連続的に入力される場合を想定している（図）．これは，静的な関係データベースに対してクエリを投げかけ，それに合致するデータを得るプル型のデータ処理とは対照的な処理である．本論文では，多次元連続データストリームに対する新しいタイプの問合せ処理として，次元実数ストリームに対する幾何的制約による時系列質問（!. * * +*,）を提案し，その効率よいパターン照合方法について研究する．すなわち，この照合機械は，ある単位時間毎に次元の実数値ベクトルが流れ込むデータストリームに対し，パターンとして与えられた幾何的制約の系列をすべて満たすベクトル列が入力されたか否かを判別する．図 # に，ストリームの点列が時系列パターンに一致したときの概念図を示す．. はじめに背景. 自動測定技術や高速ネットワーク技術の発展により，センサーデータや，通信記録，半構造データなどのストリームの形をとるデータが増大している．これに伴い，ストリームデータに対する大規模データ処理が重要になっている %#& '& & & (& #)．. .

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

(15) # " $. "

(16) # " $. " - 図. -. . . ". . 実数ストリームに対するパターン . . 主結果. 本論文では，次元実数ストリーム上の時系列パターン照合問題に対し，次のアルゴリズムを与える．次元実数ストリーム上の線形制約のクラスに対するパターン照合問題を前処理時間と，領域を用いて時間で解く素朴なアルゴリズム

(17) ．.

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

(19) ．. #

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

(21) . '

(22). 不等式の論理和制約のクラスに対するパターン照合問題を前処理時間と，領域を用いて ! 時間で解くアルゴリズム．. 提案手法. そこで本論文では，別のタイプのよく知られた文字列照合手法であるビット並列パターン照合 %#) を拡張し，次元実数変数上の時系列パターンに対する高速なパターン照合アルゴリズムを与える．また，次元間に相関のない制約の場合とある制約の場合について，それぞれ高速なアルゴリズムを与える．ビット並列パターン照合とは，前処理としてパターンに対応する 67非決定性オートマトンを構築し，実行時にビット演算を用いてその動作を高速に模倣する手法であり，ここではとくに高速かつ実装が容易な技法である / 8 7 手法 %#) の拡張を扱う．しかし，ビット並列手法の単純な適用では自明な手法と同じ時間解法しか得られない．本. 次元実数ストリーム上の次元間に相関のない. $

(23). 次元実数ストリーム上の線形制約のクラスに対するパターン照合問題を前処理時間と，領域を用いて時間で解く素朴なアルゴリズム

(24) ．.

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

(26) Æ

(27)

(28)

(29). " # 次元実数ストリーム上の線形制約のクラスに対するパターン照合問題を前処理時間と，領域を用いて時間で解くアルゴリズム

(30) ．. . ここに， " は，パターンのサイズであり， " はストリームの長さ，はバケットの分割数，は事後チェックに要する時間である．. . また，提案アルゴリズムの有効性を検証するために，人工データ上で評価実験を行った．その結果，パターン長が短い場合やその制約が緩い場合に， 3/ は 12 手法と 32 手法 %#) に基づく既存手法 %& -) と %) と比較して，

(31) $ 倍から $

(32) 倍程度高速であり，また安定した性能で動くことがわかった．ビット並列手法は，ハードウェア化による高速化が容易であり，将来のビット幅の増大が性能向上に結びつくと考えられる．また，正規表現照合も可能であるなどの利点を持つなど，実用面でもストリーム処理のための有用な手法と考えられる．本論文の構成は以下の通りである．まず # 章で，準備として用語と問題の定義を行う．- 章では，ビット並列手法を用いた提案手法である 3/ アルゴリズムの概要について述べる． ' 章では，次元実数ストリームの場合のヒット表計算について述べる．$ 章では，次元間に相関のない場合の複数次元実数ストリームのヒット表計算について述べる．章では，次元間に相関のある場合の複数次元実数ストリームのヒット表計算について述べる．章では，実験として，人工データを用いた計算時間の比較実験を行い，提案アルゴリズムの性能を考察する．章では，実データへの応用としてモーションデータを用いた検索実験を行い，結果を考察する．章の内容は 9:/;%) と /:<9;%') で発表済みである． $ 章の内容は =>;%$) で発表済みであり，章の内容は 9:/;%) で発表済みである．なお，'. . 準備. 本章では，研究対象である次元実数ストリーム上の幾何時系列パターン照合問題を定式化する．さらに，幾何制約の種々のクラスとこれらに基づく種々の幾何時系列パターンのクラスを導入する．また，必要な用語を導入する．. . -. ビット演算. 本論文では，計算モデルとして，以下の数値演算とビット演算をもつ 572 機械を仮定する %& #)．整数レジスタのビット幅をと仮定する．長さ

(33) のビットマスクは，最下位ビットを右側としたビット列で表す．長さのときは上位の残りビットにを詰めることとする．ビットごとの論理和と，論理積，否定をそれぞれ記号と，?，で表す．非負整数に対して，ビットマスクのビットの左シフトをで表す．はビットのみのビットマスクであり， " は番目のビットがのビットマスクである．整数集合に対して，でのビットマスク表現を表す．. . . . . . . ビット幅を " とする． " " と仮定する．このとき，次にビット演算の例を示す．例.

(34) #

(35) -

(36) '

(37). "

(38) ビットごとの論理積 ? "

(39) ビットごとの否定 "

(40) ビットの左シフト "

(41) ビットごとの論理和. $

(42) . のみのビットマスク. . "

(43).

(44). 最下位にの立ったビットマスク.

(45). 上のビットマスクを左に ' シフトして得られるビットマスク： ' "

(46).

(47). "

(48). " # - $ のビットマスク表現 . ".

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

(50) のビットマスクに対しては，これらの演算は時間で実行できる %& #)．.

(51).

(52) . '. . 次元実数ストリーム上の幾何時系列パターン照合問題. # と Ê でそれぞれ非負整数全体と実数全体を表す． £ で集合の反射的推移閉包 %() を表す．正整数に対して， Ê を次元実数 Æ. ". 空間とする． Ê の点またはレコードは，ベクトル " Ê である．変数のとる値域をで表す．特に指定しない場合， " Ê と仮定する．次元実数ストリームは，次元の点 £ である．列 " Ê. . . Ê. 例 " $ - $ ' # ' # # の次元実数ストリームである．例 . . ". . . £ は長さ. # . . Ê. £ は，長さの # 次元実数ストリー. ムである．次のようなデータは次元実数ストリームとして扱うことができる．

(53). #

(54). -

(55). '

(56). 交通データのレコードは，# 次元ベクトル " である．ここに，とは移動点の緯度と経度である．蛋白質データのレコードは，ベクトル " ! である．ここに，は原子の - 次元空間座標であり，! は原子の種類や電子価などの付加情報である．センサーデータのレコードは，その測定値のベクトル " で表される．モーションデータのレコードは， " . " # $ " # $ である．ここに，モデルは ( 個の関節を持つと仮定し，番目の関節に対して Ê は - 次元空間における関節の絶対座標を表し，" # $ ) は回転角を表す．. . . . . 次元実数空間上の幾何制約. 任意の

(57) に対して，次元実数空間 Ê 上の二値関数 Ê を，次元の幾何制約（制約）という．文脈から明らかなとき，幾何制約を Ê の部分集合 Ê " Ê と同一視する．. . 制約の表現長をで表す．次元実数空間上の幾何制約のクラスをで表す．. を幾何制約の任意のクラスとする．上の幾何制約の集合 " と次元の点に対して，におけるのヒット表とは，によって満たされる中の制約の集合 " " である．ここで，各制約は，添字で表すと仮定する．. . . . . 上のヒット表計算問題とは，あらかじめ定義上の幾何制約の集合 " を受け取って前処理を行い，問い合わせとして次元の点を受け取り，出力として，のにおけるヒット表を計算する問題である．. . . 本稿では，ヒット表は長さのビットマスクとして返されると仮定する．上の長さの幾何時系列パターンは，列 £ である．ここに， " に対して，は上の長さの幾何制約である．. 定義 . . . . . 上記のパターンの長さを " で定義し，のサイズを " で定義する．. . 長さのパターン " が，長さ £ の次元実数ストリーム " Ê において位置 % に出現するとは， . . が成立することをいう．. . . . . 定義パターンのクラスに対する次元実数ストリーム上の幾何時系列パターン照合問題（パターン照合問題）は，あらかじめ上の幾何時系列パターンを受け取って前処理をし，入力として次 £ を受け元実数ストリーム " Ê 取り，出力として上のの全ての出現位置を計算する問題である．. . . ここでの目的は，パラメータ " と， " ， " に対して前処理時間と，使用領域，入力ストリームにおける照合時間を小さくするアルゴリズムを設計することである．この問題を解くアルゴリズムの計算時間の下限は，明らかに @ 時間である．また，実際のストリーム監視等の応用を考えたとき，パターン照合アルゴリズムは，新しく到着する度に漸増的に動くオンライン性をもつことが望ましい．本論文で与えるすべてのアルゴリズムは，オンライン性をもつアルゴリズムである．.

(58) Æ

(59)

(60) . . 幾何制約のクラス. 本節では，本論文で扱う幾何制約のクラスを与える．次元実数空間 Ê において，変数集合を考える．点 " Ê において，番目の変数は値をとるとする．不等式 + , とは，表現 & " ' であり，ここに，' は符号であり& Ê は定数である．線形不等式* + , は，式 & ' ' である．ここに，' ' Ê は定数である．. . . . . . . . . 次元実数空間上の幾何制約のクラス. 整数ストリーム上の不等式の論理積のクラス．次元整数ストリーム上の不等式の論理積のクラス

(61) を次のように定義する．

(62) 上の幾何制約は，不等式の論理積 " & & である．ここに， ( に対して，& " ' であり，' & Ê である． " Æ である．. . . . である．ここで，各 % ( に対して，& は番目の変数に関する制約 & " ' である．ここに，' であり， Ê， " Ê である．. . . . . 等式制約 " も，# つの不等式の論理積で表すことができる．本論文では，

(63) および

(64) 上のすべての幾何制約は標準形であると暗黙のうちに仮定する．. . . 次元実数空間上の幾何制約のクラス：次元間に相関のない場合. 次元実数空間上の不等式の論理積のクラス．次元実数空間上の不等式の論理積のクラス


(66) 上の幾何制約は，不等式の論理積. " & &

(67) & &

(68). . 常に成立する線形制約を空の論理積または空集合. . 次元実数空間上の幾何制約のクラス：次元間に相関のある場合. 次元の実数空間上の線形制約のクラス．次元. 実数空間上の線形制約のクラスを次のように定義する．上の線形制約は，次元線形不等式の論理積. " & & ( である．ここに，& " ' ' は，次元線形不等式であり， ' ' Ê， Ê である．例線形制約の特別な場合として，次のような制約が表現可能である．. . ' " %' ) ' ) " ' ' 半平面．) ' ' " ' ' 凸多角形点列 " で表される凸包 " * * * * " * は非負実数．軸並行直方体． ' % . 補題

(69) および

(70) 上のすべての幾何制約は，標準形として変数に関するつの不等式の論理積 " ' ' として表すことができる．. . で表す．. 実数ストリーム上の不等式の論理積のクラス．次元実数ストリーム上の不等式の論理積のクラス


(72) 上の幾何制約は，不等式の論理積 " & & である．ここに， ( に対して，& " ' であり，' & Ê である． " Ê である．. . . $. 各クラス間の関係次の包含関係が成立する．すなわち，

(73)

(74) かつ

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

(76) . NFA ᭴▽ 䊎䉾䊃䊙䉴䉪᭴▽. 䊎䉾䊃䊙䉴䉪. 䊌䉺䊷䊮図. . 䊍䉾䊃⴫Ṷ▚. 䊎䉾䊃ਗ೉ᚻᴺ䈮䉋䉎䌎䌆䌁䈱ᮨ୮. ᾖว⚿ᨐ. 䉴䊃䊥䊷䊛 '. ビット並列パターン照合の概略. . 手法の概要. 図 ' に，本論文の提案アルゴリズムの構成を示す．では，次の # つのフェイズに分けてパターン照合を行う．まず時系列パターンの静的コンパイル処理として，与えられた時系列幾何パターンを解析し，含まれるすべての時点幾何パターンを抽出する．時点幾何パターンのクラスにしたがって，ヒット表計算のための前処理を行う．次に，ビット並列手法に基づく実行時の動的パターン照合処理として，実行時に入力ストリームから入力点を受け取りながら，ヒット表計算手続きを用いて時系列幾何パターンの照合を行う非決定性有限オートマトンを高速に模倣する．. . 時系列パターンの静的コンパイル処理. . の構築. を幾何制約のクラスとする．初めに最も単純な正規表現の族として，直線状の連続部分列からなるパターン " £ の 67 のクラスを考える．このクラスの 67 は一見単純に見えるが，部分文字列パターンだけでなく，常に真となる空制約 " や選言を用いることで，文字列照合におけるワイルドカードや集合文字に対応したパターン照合 %#) を表現可能であることに注意されたい．. . . <0>. 0 図. $. <1>. 1. <2>. 2. <3>. 3. <4>. 4. <5>. 5. 長さ $ の時系列幾何パターンに対する 67. . の時系列幾何パターン " に対する " A Æ + , は，図 $ のようなからまで与えられた長さ. の全ての状態を直線状につないだ 67 である．状態はで自己に遷移する自己ループをもつ．ここで，各遷移の有向辺のラベルは，の番目の幾何制約を表す．ここに， " である．. . A は，文字集合である． Æ A は遷移関係 Æ " " である． + は初期状態 + " である． , は受理状態集合 , " である．. . は，状態集合である．. ヒット表計算 67 の遷移を行うためには，入力点によって遷移する辺を決定する必要がある．パターン " に対して，それが含むの幾何制約すべての集合を " とおく．このとき，ヒット表を計算すればよい．. . . 最も単純なヒット表計算の方法は，実行時にストリームの点を受け取ったときに，個の制約. 全てに対して真理値検査 B " CD を行うことである．しかし，ひとつの制約の評価に . 時間を要すると仮定すると，この方法ではヒット表計算に " 時間を要する．そのため，総計算時間は時間になってしまう．そこで，次章以降では，種々の幾何制約のクラスに対する高速なヒット表計算の実現方法を与える．. . . . 実行処理. は実行時には，67 は初期状態から出発し，時点で点上で真となる時点幾何パターン " をラベルとする遷移を非決定的に実行することを繰り返し，最終状態で出現位置を出力して，照合を模倣する．図に入力次元ストリーム上でパターンを照合する 67 を模倣する手続き

(77) を示す．このアルゴリズムは，状態集合を長さのビットマスク - で表現し，ヒット表計算によって得られるヒット集合のビットマスク表現を用いたビット並列計算で高速に照合を行う．図の状態遷移にあたる行は時間で処理できる．特にパターン長が短い（）とき，時間で 67 の遷移を行うことができる．. . . . . 計算モデルとして，レジスタのビット幅で，数値演算と論理演算を定数時間で実行する 572 %#) を考える．このとき，手続き

(78) の実行時間として次の補題が成り立つ．補題図の手続き

(79) は，時系列幾何パターンに対して，次元ストリーム上の時系列幾何パターン照合問題を時間で解く．ここで，はヒット表計算に要する時間である．. .

(80) Æ

(81)

(82) * *.

(83) . . ．の上の全ての出. 入力：次元ストリーム出力：パターン ". 現

(84). ". + E , E - +E.

(85). ヒット表計算：に対するビットマスクを. . . 67. の模倣手続き

(86) . 複数パターンのクラス. . . 幾何時系列パターンの正規表現への拡張. を幾何制約の任意のクラスとする．有限可変長ギャップ %. /0/) や，省略可能幾何制約 C，繰り返しなどの演算をもつ複雑なパターンは，一般に正規表現%() の部分クラスとして定義できる．上の正規表現のクラスを次のように帰納的に定義する．. . . ならば， " & " & £ " £ で . もし . ある． . 以上で生成されるものだけがの要素で. ある．. 例節の図 - のパターンは，次元の長さ $ の単純パターンの例である．. 前節の直線状の 67 のクラスに対するビット並列化を，複数パターン照合問題に拡張できる．パターン集合 " に対して，各パターンのマスク + , - を直列に連結したマスク ¼ + ¼ , ¼ -¼ を用いて，各パターンの 67 の動作の模倣をビット演算により一括して行うことができる．詳細については %#) を参照のこと．. . 1 かつ. 力するE. 図. . ". 計算する．.

(87) . . . に対して，1. 定義言語を正規表現パターンの展開と呼び，その要素を展開例と呼ぶ．展開例は上の時系列パターンである．. - - + ? E - ? , " 出現を出. . . . 幾何制約. " である．. . に対して，1 である．もしならば， . 線形制約. . £ である．. . . ある．. 以上で生成されるものだけがの要素で. 定義上の正規表現幾何時系列パターン（正規表現パターン）は，正規表現である．. . また，正規表現の表す幾何時系列パターンをの言語 %() として次のように帰納的に定義する．. . 定義正規表現パターンがストリームにおいて位置 % に出現するとは，のある展開例である幾何時系列パターンがにおいて位置 % に出現することをいう．. . . 例図 - のパターンは，例 # のストリームに位置と位置 ' で出現する．ビット並列手法による 67 の模倣は，ヒット表計算の実現とは独立であり，67 のクラスを拡張することで，以下に示すようなさまざまなクラスの正規表現パターンを適用可能である．有限可変長ギャップをもつパターンは， ". %-) のような制限された形の正規表現パターンである．ここに，有限ギャップ %% ) は線形制約. を満たす任意のレコードの個から % 個の連続を表す．これは，図のように，ギャップを最大限に展開した単純パターン ¼ ". の 67 に 1 遷移 ( . を追加した 67 で模倣できる．ここに，( はの位置（"#），( . ( % とする．ビット演算による遷移計算では，通常の状態 - の遷移の直後に，と % にだけビットがあるマスク 2+ と 2, を，数値減算で組み合わせて次のビット並列演算を行い，2+ のビットからのすべての 1 遷移を正しく模倣する．. . . - - 2, - ? 2+ ? 2, E これは，例えば， " のように，% 番目のビットのみがのマスクから， % 番目のビットがのマスクを算術減算すると，から % までが伝播することを利用している．.

(88) . . <0>. <0>. 0. <1>. 1. <0> <2>. 表. 2. <2>. 3. <2>. 4. <3>. 5. さらにこの減算を用いた 1 遷移の実現技法を用いて， " C のような省略可能幾何制約をもつパターンや， " £ のような幾何制約の繰り返しパターンを，ビット並列手法で扱うことができる．模倣技法の詳細については， %#) を参照のこと．. １次元ストリームに対する効率よい. . . . . . . -. . $. -. . '. #-'. . -. #-'. . #. #'$. . . #'$. . 例次の不等式制約集合を考える．. "

(89) #. " $. "

(90) # . " $. " -. ヒット表計算本節では，次元実数ストリーム上の時系列パターン照合問題を考察する．-

(91) #

(92) # 節の時間のヒット表計算を用いた素朴な時系列パターン照合アルゴリズムでは，総計算時間が時間になる．そのため，本節では次元実数ストリーム上の不等式の論理積で表される幾何制約のクラス

(93) に対して、二分探索を用いた ! 時間のヒット表計算アルゴリズムを与える．さらに、次元実数ストリーム上のクラス

(94) に対して、表一瞥方式を用いた時間のヒット表計算アルゴリズムを与える．. 整数ストリームに対するヒット表 . 図有限可変長ギャップをもつパターンに対する 67. . . . . このとき，表に，値の集合 F " に対するヒット表をあらかじめ計算したものを示す．各欄は順に，値と，が満たすヒット集合，そのビットマスク表現である．ただし，簡単のため # - を #- のように表記する．. . 手続き

(95) は，幾何制約のクラス

(96) に対して，制約集合に対するヒット表計算問題を，前処理時間と領域を用いて，各入力点 Æ 個あたり，時間で解く．ここに， " は，のサイズである．定理. . 整数ストリームに対するヒット表の構築. 図に，クラス

(97) に対する，次元整数ストリーム上のヒット表計算アルゴリズム

(98) を与える．前処理では，次元整数ストリームに対して，とりうる全ての値に対して，あらかじめヒット表を計算しておく．具体的には，値の集合 F " 上の全ての値に対して，あらかじめヒット集合を表すビットマスクを計算し，ビットマスク配列 %) " %) %) に格納しておく．実行時には，配列の添字によるランダムアクセスによって，ヒット表を表すビットマスクを取り出す．. . . . 補題 # から，次の系がただちに成立する．系幾何制約のクラス

(99) 上に対して，次元実数ストリーム上の幾何時系列パターン照合問題は，前処理時間と領域を用いて，時間で解ける． " は，パターンのサイズであり， " はストリームの長さである．. . .

(100) Æ

(101)

(102) ：ビットマスク配列 . . %) %).

(103) .

(104) F . 入力：制約集合 & 値の集合 F．出力：ビットマスク配算

(105) . % ) E. 列. の. 計. 入力：制約集合．出力：ビットマスク配列の計算

(106) . のすべての線形不等式の端点を，数直線上. . 上のすべての端点と極小開区間に対してビッ.

(107). にプロットする．.

(108). " % ) % ) E

(109) .

(110) . GG実行時手続き. . . %) %). . GG前処理手続き. GG前処理手続き. . ：ビットマスク配列 % ). (. トマスクを計算し，表 # のようなヒット表の配列を構築する．この配列の要素は，端点の昇順にソートする． GG実行時手続き. . . 入力：F " 上の点 " Æ ．出力：入力点 " に対するビットマスク % )

(111). % ) E. . . . 入力：次元実数空間上上の点 " Ê．出力：入力点 " に対するビットマスク. % )

(112). を含む区間を配列から二分探索し，対応するビットマスクを見つける． E. 入力点. 図整数ストリームに対するヒット表計算アルゴリズム

(113). . 実数ストリームに対するヒット表の構築. 図 ( に，クラス

(114) に対する，次元実数ストリーム上のヒット表計算アルゴリズムを与える．実数ストリームのとりうる値は無限集合であるため先の手法が使えない．そこで，次の方法を用いる．. . 初めに，先の図のように，が含む総計個の線形不等式 & " の端点をすべて数直線上にプロットする．このとき，次が成立する．. 補題任意の線形制約を充足する値の集合は上の端点と極小開区間の集合和として一意に表現できる．証明. 上の端点と極小開区間の集合和のうち，ど. の区間も，その区間内で満足される制約は同じである．よって補題が成り立つ． ¾ これより，節 '

(115) がすべての値に対するビットマスクを計算したのと同様に，あらかじめ上のすべ. . 図 ( 実数ストリームに対するヒット表計算アルゴリズムての端点と極小開区間に対してビットマスクを計算し，表 # のようなヒット表を構築する．実行時に，入力点 Ê が含まれる区間をこの表から探索することで，に対応するビットマスクを計算できる．. . 例例の不等式制約集合に対して，図に，のすべての不等式制約をプロットしたものを示す．この図では，数直線がすべての端点と極小開区間に分割されていることがわかる．表 # に，すべての端点と極小開区間に対するヒット表をあらかじめ計算したものを示す．各欄は順に，端点または極小開区間の値と，が満たすヒット集合，そのビットマスク表現である．ただし，簡単のため # - を #- のように表記する．. . . は高々個の端点と極小開区間しか持たない.

(116) . . 表. #. y. 実数ストリームに対するヒット表 q1y.

(117) " $ " $ - $ #-' " - #-' # - #-'$ " # #'$ # #'$. q2 q0x. q1x. x. q2x. 多次元ストリームに対する効率よいヒット表計算：次元間に相関のない. q2 =q4. 幾何制約の場合. 3. q5. 2. . q0. q2y. . q3. 5. 図. q0y. 図軸平行な幾何制約と軸と軸に分離された制約. q1 7. q1. 制約集合の数直線上の表現. ので，節 '

(118) と同様の議論で，計算量は次のようになる．定理手続きは，幾何制約のクラス

(119) に対して，制約集合に対するヒット表計算問題を，前処理時間と領域を用いて，各入力点 Ê 個あたり， ! 時間で解く．ここに， " は，のサイズである．. . . 補題 # から，次の系がただちに成立する．系幾何制約のクラス

(120) 上に対して，次元実数ストリーム上の幾何時系列パターン照合問題は，前処理時間と領域を用いて， ! 時間で解ける． " は，パターンのサイズであり， " はストリームの長さである．. . . 本章では，ストリームを次元に拡張し，次元実数ストリーム上の時系列パターン照合問題を考察する．クラス

(121) 上の，パターンが次元間に相関のない制約からなる場合のヒット表計算アルゴリズムを与える．説明の簡便のため，入力点の空間として # 次元実数空間 Ê を考える．. 前章の手法を次元ストリームに単純に適用すると，に関して指数サイズの領域のビットマスクを要する．そこで，次元間に相関がない制約に特化した手法を与える．. . 変数分離形のパターン. . 制約中の線形不等式 & . がすべて各次元間に相関のない制約 & " ' であるとき，変数分離形であるという．ここに， % である．即ち， & " であり， " # 次元空間上では，図のように軸または軸に平行な直線からなる制約である．変数分離形の制約のみからなるパターンを変数分離形のパターンという．. . . . 変数分離形のパターンに対するヒット表計算. 図 # に，変数分離形のヒット表計算アルゴリズムを与える．幾何制約集合で用いられる線.

(122) Æ

(123)

(124) * *. " Ê. ' ' 上で座標に関する探索を行い，を含む垂直な帯状の領域 * を見つける．端点のリスト上で , 座標に関する探索を行い，を含む水平な帯状の領域 % 3 を見つける．それぞれのビットマスクとを取り出す． " ? E. 端点のリスト. . . 図. #. のヒット表計算. 形制約が変数分離形の制約のみで定められる場合には，図のように，軸平行な幾何制約集合 . を軸と軸に平行な制約からなる部分集合に分離し，各次元毎に前処理を行い，実行時に入力点 " に対して各次元のヒット表の論理積を求めることで扱える．これは，ヒット表のビットマスク表現のビット積 " & で高速に求めることができる．これにより，ビットマスクの検索処理の著しい簡素化と高速化が可能である．. . . . まず，. 中の線形不等式で軸に平行なもの（垂直線）の全体を考える．これらの垂直線全体を座標で昇順にソートしたリストを 4 " 5 ' 5 とおく．次に，これらの垂直線を用いて，平面 Ê を互いに交わらない，垂直な帯状の領域 Ê " に分割する．各領域 * に，その領域との共通部分が存在する制約すべての集合を表すビットマスクを関連付ける．同様に，軸に平行な直線（水平線）の全体を用いて，互いに交わらない水平な帯状の領域 Ê " に平面 Ê を分割し，各領域 % 3 に，それを満たす制約集合を表すビットマスク . を関連付ける．. . . . . . . . . 算問題を，前処理時間と領域を用いて，各入力点 Ê 個あたり， ! 時間で解く．ここに， " は，のサイズである．. . に対して，座標と , 座標それぞれに対して領域のリスト上の探索を行い，それぞれに対応づけられたビットマスクをビット積で結合したものを返す．各次元に個の制約が含まれているとする．各次元に関して，のリストを探索してビットマスクを返すので，変数分離形のアルゴリズムの計算量は次のようになる．定理手続きは，幾何制約のクラス

(125) に対して，制約集合に対するヒット表計. . 補題 # から，次の系がただちに成立する．系幾何制約のクラス

(126) 上に対して，次元実数ストリーム上の次元間に相関のない幾何時系列パターン照合問題は，前処理時間と領域を用いて， ! 時間で解く． " は，パターンのサイズであり， " はストリームの長さである．. . . . 変数分離形でない制約集合への適用. ' というような変数分離形でない制約は，新しい仮想的な変数 " ' を各時点で計算することで，変数分離形の制約に帰着することができる．また，変数の前の値との比較 67 のような制約についても，変数 " 67 の導入によって実現できる．. . まとめ. 本節で述べた変数分離形の場合のヒット表計算は， - の場合にもそのまま適用できる．これは次章で述べるスラブ法と比べて，構造と前処理の簡単さに利点がある．とくに，- 次元以上の高次元データの場合に有利である．. . . 多次元ストリームに対する効率よいヒット表計算：次元間に相関のある幾何制約の場合. . は，与えられた入力点 " . . 本節では，複数次元間に相関がある場合のクラス. の幾何制約集合に対するヒット表計算の効率. 良いアルゴリズムを与える．. . 手法の概要. 議論の簡便のため，入力点の空間として # 次元実数空間 Ê を考える．いま，# 次元平面 Ê 上の線形幾何制約の集合 " が与えられたと仮定する．以後，中に含まれるすべての線形不等式からなる集合を . で表し，その総数を " . で表す．すなわち， " である．. . . . . . .

(127) . #. GG実行時手続き. Ê. ". . . . E.

(128). &

(129). & " E. .

(130)

(131) . E. . 図.

(132) . -. R0,6. Ͱ1. R2,6. R4,6. R2,4. R4,4. R6,6. R0,4 R6,4. R2,2 R4,2. 素朴な方法によるヒット表計算アルゴリズム. Ͱ3 R0,0. 素朴な方法. R2,0. S0. 素朴な方法として，前処理を行わず，入力が与えられるたびに，集合の制約を逐次的に評価する方法が考えられる．図に，素朴なヒット表計算手続き

(133) を示す．定理手続き

(134) は，幾何制約のクラスに対して，制約集合に対するヒット表計算問題を，前処理時間と領域を用いて，各入力点 Ê 個あたり，時間で解く．ここに， " は，のサイズである．. . 補題 # から，次の系がただちに成立する．系幾何制約のクラス上に対して，次元実数ストリーム上の次元間に相関のない幾何時系列パターン照合問題は，手続き

(135) を用いて前処理時間と領域で， ! 時間で解ける．ここに， " はパターンのサイズであり， " はストリームの長さである．. . . y. R0,2.

(136) . Ͱ2. . スラブ法. 本節では，スラブ法を用いたヒット表計算アルゴリズムを与える．スラブ法は，あらかじめ前処理でビットマスクを計算しておき，入力毎のビットマスクを表引きで高速化する方法である．アルゴリズムは，時点幾何パターン集合が与えられると，次のように前処理を行う．. 図. '. R6,2 R6,0. R4,0. S1 S2 S3. S4. S5. S6 x. スラブ法：帯状領域と台形領域. 前処理初めに，. 中のすべての線形不等式から二つずつとった組み合わせ & & . を考えて，それらの交点 & & 全体の集合 + " & & & & . Ê を求める．次に交点の座標をと昇順にソートして並べる．これらの点を通って軸に平行な直線（垂直線）を引いて区切り，平面 Ê を互いに交わらない垂直な帯状の領域と，垂直線のみからなる領域 Ê " に分割する．ここに， * に対して，# 番目の帯は " . Ê であり， # 番目の帯は " % ) Ê である．ただし， " " と定義する．. . . . . . . . 各 " #* に対して，垂直な帯と，を横切る . のすべての直線を考える．を横. 切る直線で区切り，台形領域と，直線のみからなる領域 " 8

(137) 8

(138) に分割する．の内部ではどの . の直線も交わらないので，台形領域 8

(139) 8

(140) は軸の向きに一意に順序づけることができる．各台形領域 8

(141) の内部では明らかに満足される制約は同じなので，各 8

(142) に，満足される制約すべての集合を表すビットマスクを関連付ける．図 ' に，- つの線形制約 & & による帯状領域と台形領域の分割を示す．. . . . 検索処理図

(143) - に，スラブ法を用いて実行時に入力点に対するビットマスクを計算する手続きを与える．このアルゴリズムは，入力点 " が与えられると，座標に関して二分探索を行い，を.

(144) Æ

(145)

(146) * *. Ê. . ! .> /H. ". . . . 座標に関する二分探索を行い，を含む帯状の領域 #* を見つける．に含まれる台形領域に関する二分探索を行い，を含む台形領域 8

(147) % #3 を見つける． E. . 図. $. y NΔ R1,N. …. RN,N. …. RN,1. スラブ法におけるヒット表の計算. Δ. R1,1. 計算量集合 . 中の本の直線の交点数は最大で，9 " 箇所なので，領域の数 * 3 は高々9 で抑えられる．計２回の ! 9 " ! 時間の二分探索を行うので，計算量は次のようになる．定理手続きは，幾何制約のクラスに対して，制約集合に対するヒット表計算問題を，前処理時間と領域を用いて，各入力点 Ê 個あたり， ! 時間で解く．ここに， " は，のサイズである．. . . 補題 # から，次の系がただちに成立する．系幾何制約のクラス上に対して，次元実数ストリーム上の次元間に相関のない幾何時系列パターン照合問題は，手続きを用いて前処理時間と領域で， ! 時間で解ける．ここに， " はパターンのサイズであり， " はストリームの長さである．. . . これは素朴な場合に比べて，指数的なスピードアップである．. . 次元が - の高次元データの場合にも，再帰的な拡張でスラブ法を適用可能である．しかし，索引構造の複雑さから，実際には # が実用的だと思われる．. バケット法. 実際的な高速化技法として，式の定数や交点の座標が，微小長さ F Ê を単位として離散化されてお. . …. …. 含む帯状の領域を見つける．次に，の内部を座標に関して二分探索を行い，を含む台形領域 8

(148) を見つける．最後に，台形領域 8

(149) に対応づけられたビットマスクを返す．. . -. NΔ x. Δ 図. . バケット法. . り，入力値が上下限をもつ有限な実数区間 %' ) Ê から与えられる場合が重要である．この場合は，スラブ法における二分探索を行わず， # 次元配列上のバケットを用いた表引きによる高速化が可能である．本節では，バケット法を用いたヒット表計算アルゴリズム

(150) を与える．本節で述べる手法は，'

(151) 節の次元整数ストリームのヒット表計算を，次元実数ストリームへ拡張した手法と考えることができる．. . 問合せ可能な領域を %F F %F F Ê とする．# 次元配列 % ) 上に，一辺が F の直方体状の小領域 8

(152) " % F F %% F % F を表すバケット % % ) % を配置する．その小領域 8

(153) 上で満足される制約集合を表すビットマスク

(154). をバケットに直接格納する．直線がバケットを斜めに横断する場合には，

(155) を検索後に個々の制約を順に検査する事後チェックが必要である．前処理. . . . . 検索処理図

(156) ' に，実行時に入力点に対するビットマスクを計算する手続きを示す．

(157) は，入力点 " が与えられると， " :F と % " :F に対して，バケット % % ) を直接表引きし，関連付けられたビットマスク

(158). を返す．.

(159). .

(160).

(161) . '. * *.

(162)

(163) " Ê. " :F

(164) E % " :F

(165) E バケット % % ) を直接表引きするE 関連付けられたビットマスク

(166) . . . 実験. 本節では，提案アルゴリズムするための計算機実験を行う．を. 返す．. . の性能を評価. 実験１. 章の次元実数ストリームと次元整数ストリームに対するアルゴリズムと， $ 章の変数分離形に対するアルゴリズムの性能を評価する実験を行った． '. 図. . バケット法におけるヒット表の計算. 計算量定理手続き

(167) は，幾何制約のクラスに対して，制約集合に対するヒット表計算問題を，前処理時間と領域を用いて，各入力点 Ê 個あたり，時間で解く．ここに， " は，のサイズ，は事後チェックに要する時間である．. . . 補題 # から，次の系がただちに成立する．系幾何制約のクラス上に対して，次元実数ストリーム上の次元間に相関のない幾何時系列パターン照合問題は，手続き

(168) を用いて前処理時間と領域で，時間で解ける．ここに， " は，パターンのサイズであり，はバケットの分割数， " はストリームの長さ，は事後チェックに要する時間である．. . . の時間計算量は理論的にはだが，ランダムな制約データの場合は定数とみなせると期待できる．また，事後チェックを行わないことで， " となる近似的なパターン照合の実装とすることができる． . まとめ. 本節では，一般的な線形制約に対する高速なヒット表計算のアルゴリズムとして，バケット法とスラブ法を与えた．バケット法はスラブ法と比べて，# 次元空間上で検索領域が離散的かつ有界な場合に，構造の簡単さと検索速度で著しい利点がある．一方で， - 次元以上の高次元では，データが疎になりほとんどのバケットが無駄になることから実用性は低いと思われる．. 実験では，以下に示される種類のアルゴリズムを I言語で実装し用いた．時間の素朴なパターン照合アルゴリズム %#) の実数ストリーム版．. !"#$ %$. 12. %$. 32. 手法 %) の実数ストリーム版である .* %) と /* ら %-) の 4#5 アルゴリズムの実装．手法 %-) の実数ストリーム版であるの 5#4 アルゴリズムの実装．. .* %). ' 章のを用いた 3/ アルゴリズムで，ヒット表計算を配列上の二分探索 %) で行うもの．. &' $. ' 章のの二分探索を線形探に置き換えた 3/ アルゴリズム．. &' $ 索. %). ' 章の

(169) を用いた整数ストリームに対する 3/ アルゴリズムで，ヒット表計算を表引きで実現したもの．. &' $.

(170) 次元の実験については， & & を $ と同様の議論で次元に拡張したアルゴリズム & & をそれぞれ代替として用いた．. . データ " % ) Æ 上の一様分布で独立に生成した個の次元上の点からなるストリームデータと，ランダムパターン ". を用いた．ここにパラメータ 1 に対して，独立なランダム整数 '. % 1) に対し， " * * かつ * "

(171) ' . ' 1 ととった．とくに指定しない限り， " とし， " " " - とした．. . . . . . . .

(172) Æ

(173)

(174) 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. 10000000. 0. L ength of Data. 0. 図. . 2. 4 6 Length of P attern. 8. 10. データサイズと計算時間図. (. パターン長と計算時間. . . 実験結果. 5. NAÏV E L2R R 2L. 4 T ime (s ec). 方法実験は，I（ 2

(175) -J.K，レジスタ長 -#H ，572 J3，I,!L， !-

(176) '

(177) '）上で行った．パラメータを変えて生成したストリームデータに対して，各アルゴリズムの計算時間を計測した．ストリームデータは主記憶上に読み込み実験を行った．計算時間には，データの読み込み時間は含めていない．. B P S _bin B P S _lin. 3. B P S _tab. 2 1 0 0. データサイズに対する規模耐性．データサイズに対するアルゴリズムの規模耐性を評価するため， 5#4 と，3/ ，3/ H に対して，を個から個まで変化させて，それぞれの計算時間を測定した．計算時間は - 回の平均である．結果を図に示す．3/ アルゴリズムの計算時間はに比例し，-

(178) - 節の定理 # から予測されるふるまいと整合する．具体的には， " " のとき，3/ H の計算時間は

(179) 秒程度であり，十分高速だった．パターン長と計算時間．パターン長の変化に対するふるまいを評価するため，実装したつのアルゴリズムに対して，をからまで変化させたときの計算時間を測定した．計算時間は - 回の平均である．結果を図 ( に示す．3/ H の計算時間は，の値によらず

(180) 秒前後であり，つのアルゴリズムの中で最も高速であった．67=M と， 4#5，5#4 の計算時間はパターン長によらず

(181) $ 秒前後で一定だった．3/ は， ' では 67=M と，4#5，5#4 より高速だったが， $ ではこれらのアルゴリズムより低速だった．3/ H は，同様の傾向を持つがより低速だった．. . &' のデータ幅に対する耐性．整数ストリームに対するアルゴリズム 3/. H は，ストリームの. 4. 図. 8. #. 12 16 R ange of Data. 20. 24. データ幅と計算時間. 値域に比例するサイズのマスク配列を用いるため，が大きい場合の有効性は未知である．そこで，パターンの相対幅 / " #$N を一定に保ったまま，を # " から # " # まで変化させて計算時間を測定した．結果を図 # に示す．ビット整数程度のデータ幅までは，3/ H は他のアルゴリズムの #

(182) $ 倍高速であり，十分使用に耐えることがわかった．複数パターン照合． - つの 3/ アルゴリズムを複数パターン照合へ拡張し（-

(183) ' 節参照），パターン数 . をからまで変化させて計算時間を測定した． 67=M と，4#5，5#4 は複数パターンへの拡張が自明でないため，各パターンの照合にかかった計算時間の和を用いた．結果を図 # に示す．3/ H の計算時間は，パターン数によらず一定で，

(184) 秒程度だった．3/ H と 3/ の計算時間は，パターン数の増加にともない増加したものの， . # では， 67=M と，4#5，5#4 よりも高速だった．たとえば，パターン数では，5#4 と比較して，3/ H は倍程度，3/ H と 3/ は #

(185) $ 倍程度高速であった．. .

(186) . . 12. NAÏ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. 図. #. 2. 図. #-. 3. 4. 5. 6. 7. 8. 次元数に対する計算時間. R ange of P attern 0 0. 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 " ; とした．全アルゴリズムの計算時間はに比例し，とくに，は他のアルゴリズムと比較して #$ 倍程度高速だった．. 2. . ' では 3/ が， $ では 4#5 しては，や 5#4 が高速だった．また，3/ アルゴリズムはパターンの内容によらず比較的安定した性能であった．. 1. 図. 1. パターン数と計算時間. Naïve L2R R 2L d-B P S _bin d-B P S _lin d-B P S _tab. 3. Number of Variables. 0. 8. 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. 程度の整数ストリームで実験のまとめ． # は 3/ H が最も高速だった．実数ストリームに対. . 実験２. 章の，次元空間上の線形制約クラスの時系列幾何パターンを扱うためのヒット表計算の実行速度を比較するため，合成データ上で実験を行った．ここでは，節 #

(187) '

(188) - の例 ' で述べたような凸多角形からなるパターンに対応するヒット表構築アルゴリズムを，自明なアルゴリズム

(189) と& スラブ法を用いたアルゴリズム，バケット法を用いたアルゴリズム

(190) として実装した．なお，今回実験で用いた

(191) は，ひとつのバケット内に複数の領域がある場合の事後チェックを行わない簡易な実装である．また，バケットの分割は $# $# とした．. . 実験 # は，I（I * # 9 ># #

(192) J.K，レジスタ長 -#H ，572 J3，MI #）上で行った．. . データ. . . 二次元平面 8 " % ) % ) Ê 上にランダムに生成した 7 " 個の点 8 に対する凸包を計算した．図 #' に凸包の例を示す．生成した凸包を個連結したものを長さのパターンとした．ランダムに生成した # 次元座標上の長さの点列 " 8£ を # 次元実数ストリームとした．. . .

(193) Æ

(194)

(195) 3000. y. d-HT-naive d-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. 図. . #'. ランダムな 7 点の凸包. 方法. 生成したパターンに対応するヒット表を，各アルゴリズムを用いて構築した．これらのヒット表に対して点列を入力として与え，ビットマスクを計算するために必要とした総計算時間を計測した．. . 実験結果. パターン長をからまで変化させたときの各アルゴリズムの計算時間を図 #$ に示す．

(196) の計算時間はに比例して増大した．の計算時間はが大きくなるにつれ対数的に増大したものの， " ' で

(197) に比べて ' 倍程度高速であった．

(198) の計算時間はの値に関わらず一定であり， " ' で

(199) に比べて #$ 倍程度高速であった．これらの振舞いは，章で述べた計算量に合致している．また，

(200) が事後チェックを行わないことにより誤ったビットマスクを返す割合を調べたところ， " ' 7 " のとき $N 程度であった．. . #$. パターン長に対する計算時間. x. 次元実数ストリーム上の時系列パターン照合のモーション検索への応用. 本節では，アルゴリズムの実データへの応用実験として，モーションデータからの検索実験を行う．. . データ. モーションデータとして， GG LLL

(201)

(202) で HO 形式で公開されている歩行モーションデータ L * K

(203) HO を用いた．今回データに用いた HO 形式は，スケルトン階層記述部と各関節のモーションデータ記述部からなるファイル形式である．スケルトン階層記述部には，モデルの関節と関節間の長さが階層構造で記述されている．モーションデータ記述部には，各時点での姿勢が，各関節について - 次元の絶対座標と - 次元の回転角による相対座標の計次元データで記述されている．モーションデータファイル L * のスケルトン階層記述部の一部抜粋を図 # に，モーションデータ記述部の一部抜粋を図 # にそれぞれ示す．L * K

(204) HO では，腰を根とした ( 関節の木構造で人体モデルを記述している．このモーションデータは，$ 歩程度歩いて度方向転換することを # 往復繰り返した動きのデータである． K

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

(206) . .