大量データストリームの類似探索手法

全文

(1)Vol. 48. No. SIG 7(TOD 33). Mar. 2007. 情報処理学会論文誌：データベース. 大量データストリームの類似探索手法藤. 原. 靖. 宏†. 櫻. 井. 志†. 保. 山. 室. 雅. 司†. 現在データストリームを利用したアプリケーションに対する注目が様々な分野で集まっている．データストリームを処理するには今までにない新しいアプローチが必要である．本論文は複数のデータストリームの中から任意の長さで正確に類似したシーケンスの組合せを探索する問題を対象とする．我々は，(1) シーケンスの特徴量をメモリ内で保持し，(2) 圧縮されたシーケンスをディスク内に保持する手法 DAPSS（DAta stream Processing for Store and Search）を提案する．DAPSS を検証した結果ナイーブな手法と比較して高速に処理が行えることを確認した．. A Similarity Search Method for Multiple Data Streams Yasuhiro Fujiwara,† Yasushi Sakurai† and Masashi Yamamuro† There is much interest in the processing of data streams for applications in the several fields. The key characteristic of stream data demands a new approach. This paper focuses on the problem to detect exactly similar pairs among multiple data streams with similarity queries of arbitrary length. We propose DAPSS (DAta stream Processing for Store and Search), an efficient method to detect similar streams, which keeps (1) the feature data of each sequence in memory space and (2) the compressed data of the original sequences in disk space. Experiments show DAPSS is significantly faster than the naive method.. 処理する．. 1. まえがき. (2). 問合せ処理と更新処理を高速に計算する．. 現在データストリームを利用したアプリケーション. 既存研究では上記の要求条件を満たすため，データ. に対する注目が金融，環境，モバイル，ウェブアプリ. は処理後に廃棄されてきた．しかしこのような手法は. ケーション，製造などの分野で集まっている．これらの. 精度が犠牲になってしまう．そのため本論文ではこの. アプリケーションでは複数の時系列データが時間が経. 欠点をなくすため，データストリーム処理の要求条件. 過するごとに増大していく．一般的にデータストリー. として新たに以下の条件を加える10) ．. ムは高いビットレートで長い期間にわたって流入してくるため，潜在的に非常に大きなサイズになりうる．. ( 3 ) データストリームの処理結果が正確である．我々の知る限り，本論文はデータストリームにおけ. そのためデータストリームを利用したアプリケーショ. るシーケンスの類似探索問題において，メモリの有限. ンを実現するためには，この大きくなり続けるデータ. 性と処理結果の正確性を考慮した初めての取り組みで. を扱うことが必要となる．しかしシステムのリソース. ある．本論文では，複数の流入するシーケンスの中から，. は限られているため，流入してきた時系列データをすべてメモリに保存することは不可能であり，また時系. 未知で任意長の問合せに対して，正確に類似している. 列データがメモリになければ高速な問合せ処理はでき. シーケンスのペアを求める問題を扱う．この問題の典. ないというトレードオフが発生する．. 型的な問合せとして，「次々と流入する売上げデータ. 大きくなり続けるデータを高速に扱うために，その. から似た売上げトレンドを示す商品を見つける」，「群. 処理手法の要求条件として以下のようなものがあげら. 衆の中から似た移動軌跡を示している人を高速に見つ. れる．. ける」，「地震時に似た揺れ方をしている地点を見つけ. (1). る」などがある．このように本論文で扱う問題は様々. 膨大なデータストリームを限られたメモリ量で. なアプリケーションに適用が可能である．しかしデータストリームは非常に大きなサイズになりうるという. † 日本電信電話株式会社 NTT サイバースペース研究所 NTT Cyber Space Laboratories, NTT Corporation. 特徴があるため，ナイーブにこの問題を解くには非常 1.

(2) 2. 情報処理学会論文誌：データベース. Mar. 2007. らの手法は蓄積されたシーケンスを J-sliding window. に大きな計算量とメモリ量を要する．本論文ではシーケンスの距離近似のための新手法だ. に，探索するシーケンスを J-disjoint window に分割. けでなく，(1) データストリームの圧縮格納，(2) デー. する．Faloutsos らの手法が分割したシーケンスをま. タストリームの特徴量の更新，(3) 特徴量を用いた問合. とめて格納していたのに対して Moon らは分割した. せ処理，という 3 つを組み合わせたデータストリーム. シーケンスごとに格納することによって，さらなる高. 処理のフレームワークを提案する．本論文では DAPSS. 速化を達成している．. （DAta stream Processing for Store and Search）を提案する．DAPSS には以下のような特徴がある．. • 高速処理：大量のストリームを効率的に処理し，類似するシーケンスの組合せを高速に検出. 現在，データストリームを対象とした研究がさかんである．Zhu らはデータストリームの相関関係を高速に検出する手法を提案した20) ．Zhu らの手法はシーケンスを basic window に分割することによって，DFT. • 正確：探索されたシーケンスの組合せは正確 • 省メモリ：探索処理は少ないメモリで実行可能. に基づく特徴量を高速に更新する．探索のときは特徴. • 蓄積：流入したシーケンスを少ない容量で高速にディスクに格納 • 任意長：任意の長さの問合せシーケンスに対して. 速に解を絞りこむ．しかし彼らの手法は固定長の問合. 量空間にシーケンスをマッピングすることによって高せシーケンスに対して類似探索をするものでありまた処理結果は正確でない．Bulut らは流入するシーケンスの相関関係などを様々な長さの window に対して計. 探索可能処理結果の正確性と探索処理の高速化の両方を達成. 算する手法について研究した5) ．Bulut らの手法では. するため，DAPSS は近似手法を用いてほとんどの非. 様々な長さの window に対応するために R*-tree の. 類似シーケンスペアの枝刈りを行った後に，ディスクにあるオリジナルのシーケンスを用いて類似候補が解. MBR を用いて階層的な特徴量の計算を行う．探索は R*-tree を用いることによって高速に行うことができ. であるかを判定する．本論文では DAPSS について性. る．彼らの手法は任意長の問合せシーケンスに対して. 能評価を行った．評価実験ではナイーブな手法と比較. 類似探索をするものであるが，処理結果は正確でない．. し，探索処理の大幅な高速化を確認した．本論文の構成は以下のとおりである．2 章で関連研究をあげる．3 章で本論文における問題の定式化を行い，提案手法 DAPSS について説明する．4 章で DAPSS の評価実験の結果を示す．5 章で本論文をまとめる．. 3. 提案手法 3.1 前準備 Babcock ら2) は，データストリームに対する問合せを 2 つの観点から分類している．最初の分類は，単一. 2. 関連研究. 問合せ（one-time query）と連続問合せ（continuous. 過去，データストリームに関する研究は数多く行わ. 本論文では，連続問合せを単一問合せの繰返しととら. query）である．シーケンスマッチングの問題を扱う. れてきたが，1 章にあげた要求条件を満たす手法は存. える．第 2 の分類は次のとおりである．. • 事前定義問合せ（predefined query）：問合せ結. 在しない．蓄積されたシーケンスを対象とした研究については様々な手法が提案されている．Agrawal らは whole. matchig（等しい長さのシーケンスが対象）について研究した1) ．Agrawal らの手法はシーケンスを DFT を用いて近似し，R*-tree 3) に格納することによって類似. 果に関連するデータを受信する前に，システムに与えられるような問合せ. • アドホック問合せ（ad hoc query）：データストリームの受信を開始した後にオンラインでシステムに与えられる問合せ. シーケンスの高速な探索を可能とする．Faloutsos らは. 事前定義問合せよりアドホック問合せの処理の方が. Agrawal らの研究を subsequence matching（異なる. 技術的に困難である．事前定義問合せにおいては，問. 長さのシーケンスが対象）に拡張した9) ．Faloutsos ら. 合せが与えられてからデータ処理を開始すればよい. の手法は蓄積されたシーケンスを sliding window に，. が，アドホック問合せの処理は，過去のデータの特徴. 探索するシーケンスを disjoint window に分割しそれ. 量，もしくは過去のデータそのものを参照しなければ. ぞれの window に対して DFT による近似を行う．蓄. ならないためである．しかし事前定義問合せよりアド. 積されたシーケンスを R*-tree に格納することによっ. ホック問合せのほうが明らかにシステムとして柔軟性. て高速に探索する．Moon らは Faloutsos らの研究に. が高い．そのため本論文ではアドホック問合せを対象. おけるシーケンスの分割手法を一般化した. 17). ．Moon. とした．.

(3) Vol. 48. No. SIG 7(TOD 33). 大量データストリームの類似探索手法. 表 1 主な記号の定義 Table 1 Definition of main symbols.. ケンスの特徴量を用いてほとんどの類似シーケンスのペアを求めた後に，ディスク内に保持した圧縮された. Symbols. Definitions. xt. Value of data sequence X at time t (1 ≤ t ≤ n) Sequence length of X Number of data sequences Subsequence of X from n − l + 1 to n Threshold for similarity queries Euclidean distance between sequences X and Y. n m Xl D(X,Y ) ˆ X. Approximation of X. ˆ Yˆ ) L(X,. Lower bound of D(X,Y ). ˆ Yˆ ) U(X, r Ri. Upper bound of D(X,Y ) Number of reference points Reference point (1 ≤ i ≤ r). 3. シーケンスを用いてメモリ内の特徴量からは求められない類似シーケンスのペアを求める．DAPSS においてディスクの利用は必要最小限にとどめられ，効果的な探索が可能になる．DAPSS は以下の 3 つの手法から構成されている．. 3.2.1 可逆圧縮 DAPSS は解の正確性を保証するが，正確な解は近似されたシーケンスからは求めることができない．そのため DAPSS は近似されたシーケンスによる解の結果を補うためにオリジナルのシーケンスデータを用いる．限られたメモリ量に対して流入したシーケンスデー. 本論文ではシーケンス間の距離関数としてユー. タすべてを保持することは実用的に不可能であるた. クリッド距離を用いる．2 つのシーケンス X =. め，DAPSS はシーケンスデータをディスクに格納す. (x1 , x2 , . . . , xn ) と Y = (y1 , y2 , . . . , yn ) のユークリッ. る．しかしディスクにアクセスするための高い I/O コ. ド距離 D(X, Y ) は. ストを考慮に入れなければならない．DAPSS は I/O. n. (xt − yt )2 となる．本論文が対象とする問題は以下のとおりである．問題 1 問合せの長さ l，閾値が与えられたとき， t=1. m 個のシーケンスの中から以下の条件を満たすシーケンスのペアの集合を探索する．. n D(Xl , Yl ) = (xt − yt )2 ≤ . コストを減らすためにオリジナルのシーケンスを圧縮する．データストリームに対しては高速な処理が求められる．しかし多くの既存の圧縮手法においては確率に応じた符号化が行われるため，その計算コストは高い．. (1). t=n−l+1. 本論文で用いる主な記号の定義を表 1 に示す．直感的にこの問題は，任意の長さ l の問合せに対して，長さが n となるシーケンス m 個から，探索時刻からの長さ l である部分シーケンスのユークリッド距離が閾値以下になるものの組合せを探索するものである．本論文における問題は多次元空間内の探索問題であるが，従来の多次元空間内の探索問題3),13),19) とは. そこで本論文ではシーケンスのデータ値をバイトごとに再構成し，ランレングス符号化を用いてワンパスで高速に圧縮する．. 3.2.2 PSA 過去の研究において，DFT，Chebyshev approximation 7) ，SVD（Singular Value Decomposition）16)，. DWT 18) ，APCA（Adaptive Piecewise Constant Approximation）14) など，様々なシーケンス近似手法が提案されてきた．本論文では新しい近似手法として. シーケンスが流入するたびに n が増加する点が異なる．. PSA（Piecewise Statistical Approximation）を提案. この問題をナイーブに解く場合における技術的課題. する．PSA は複数のセグメントに分割された部分シー. は 2 つある．1 つ目は多くのメモリ量が必要になることである．これは特にシーケンスが長いことに起因し，. ケンスの平均と標準偏差を特徴量として用いる．. PSA には 3 つの利点がある．まず PSA は後に述べ. アドホック問合せにおいては問合せの長さが未知であ. るように 1 つのデータストリームに対して O(1) で更. るので，すべてのシーケンスをメモリ上に保持しなけ. 新が可能である．これは複数のセグメントを結合した. ればならず，O(mn) のメモリが必要になる．2 つ目. ときに，結合後の平均と標準偏差は容易に計算できる. は多くの計算量が必要になることである．これは特に. からである．これは既存の近似手法が蓄積されたシー. シーケンスの数が多いことに起因し，すべてのシーケ. ケンスを対象とし，逐次的に更新できないため計算量. ンスの組合せを計算するには O(m2 l) の計算量が必要. が大きくなること（たとえば DFT は O(l)，SVD は. になる．. O(l2 )）を考えれば，大きな利点である．さらに PSA により，シーケンス間の距離の上限値. 3.2 DAPSS の概要 DAPSS は問題 1 を解くためにメモリとディスクを効率的に用いる．すなわちメモリ内で保持したシー. と下限値を求めることができる．上限値は過剰探索（類似していないシーケンスを類似していると判定す.

(4) 4. Mar. 2007. 情報処理学会論文誌：データベース. ること）を発生させず，下限値は探索漏れ（類似してるシーケンスを類似していないと判定すること）を発生させない．探索処理において上限値と下限値を組み合わせて用いることにより，ディスクアクセスをともなう厳密な距離計算の回数を抑制し，類似ペアを高速に検出することができる．. PSA の 3 つ目の利点として，様々な長さの問合せシーケンスに対して誤差は相対的に同等であることがあげられる．これはアドホック問合せにおいて，問合. 図 1 システム構成 Fig. 1 System architecture.. せのシーケンス長が未知であることを考えれば，非常に有用な特徴である．. 3.2.3 索. 引. ジュール，蓄積モジュールから構成される．更新モジュールがシーケンスデータを受信するたび. データシーケンスは多次元空間内の 1 つの点として考えることができる．そのためデータシーケンスは Rtree に代表される SAM（Spatial Access Methods）. にシーケンスデータはシーケンスバッファに保持され. によって索引付けが可能である．しかし SAM を本論. され，データストレージに格納される．ユーザやアプ. 文で考える問題に適用することは，2 つの理由から難. リケーションが問合せを発行すると，クエリプロセッ. しい．まず SAM の性能は次元数が 8–12 以上になる. サは PSA から索引を作成し，非類似なシーケンスの. と劣化することは知られているが，PSA の係数はそ. ペアを枝刈りする．もし必要であれば，類似シーケン. れ以上の数である．後に示すように PSA の係数の数. スペアの候補について，蓄積モジュールにあるシーケ. は長さ n のシーケンスに対して O(log n) となる．そ. ンスデータを用いてその距離が計算される．. る．そして PSA 更新モジュールによりシーケンスの. PSA が計算される．シーケンスデータは定期的に圧縮. のため O(log n) 個の係数に対する索引手法が必要で. 3.4 可逆圧縮. ある．また SAM は典型的には階層構造を有しており，. 本論文では，オリジナルのシーケンスを圧縮して，. その構造を高速に更新することが難しい．. ディスクへアクセスするときの I/O コストを低減さ. そこで，本論文では新しい索引手法を提案する．シー. せる．新手法では，圧縮率を向上させるためシーケン. ケンスの特徴量を用いるのではなく，多次元空間内の. スデータをバイト単位に分割して並べ替える．ブロッ. 複数の基準点からの距離を用いて類似シーケンスを絞. クソーティング6) のように圧縮する前にデータの並べ. り込む．提案する索引手法は非階層構造であり，また. 替えをするが，圧縮するデータそのものを分割するこ. 基準点からの距離は PSA により高速に計算する．基準. とを特徴とする．. 点からの距離に基づいて索引付けを行うため，任意の. 3.4.1 前処理. 長さの問合せに対して高速に索引を構築することがで. 前処理として，データを分割して並べ替える．図 2. きる．さらに提案する索引手法は SAM と同様に探索. に示すように計算機の内部においてはシーケンスの. 漏れなく類似ペアの候補を求めることができる．PSA. データ値は複数バイトの集合として表現される（たと. によって高速な距離計算をすることができるが，シー. えば 16.84 は，IEEE-754 形式で 01000001 10000110. ケンスの数が増加すると急激に距離計算の回数が増大. 10111000 01010010 となる）．1 つのデータ値におい. し，探索コストの上昇を招く．そこで，シーケンスを. ては隣り合うバイトは似ていないため，データ値をそ. 索引付けすることにより非類似ペアを高速に枝刈りす. のまま圧縮してもそれほど効果は期待できない．しか. る．このことにより，距離計算の回数を減らし，PSA. しシーケンスにおいてはデータ値が漸次的に変化す. の効果を高める．. るという特徴があるため，複数データ値の符号部と仮. 3.3 システム構成 DAPSS はシーケンスの類似問合せをメモリとディスクを効率的に用いることによって処理する．すなわ. 数部は似ているという特徴がある（たとえば 16.84 と. ちメモリ内に保持された特徴量のみでほとんどの類. ト単位に分割し，並べ替えたバイト列に対して圧縮を. 似シーケンスのペアを求め，ディスク内のデータを用. 行う．圧縮のためのアルゴリズムを図 3 に示す．. いるのはわずかなペアのみに限定される．DAPSS のシステムは図 1 に示すように更新モジュール，探索モ. 17.03 と 17.35 の符号部と仮数部はすべて 01000001 である）．そのため，T 時間ごとにシーケンスをバイ. 3.4.2 圧縮・格納符号化にはランレングス符号化（RLE）を用いる．.

(5) Vol. 48. No. SIG 7(TOD 33). 5. 大量データストリームの類似探索手法. 図 2 データ値の内部表現 Fig. 2 Inner expression of data values.. Algorithm StoreData(XT ) //B is the number of bytes of sequence values for i = 1 to B do concatenate the i-th bytes of XT ; //XT is a subsequence of X from n − l + 1 to n end for compress the concatenated data by RLE; append the compressed data to the sequential file on the disk;. 図 4 シーケンスのセグメント化 Fig. 4 Sequence segmentation. ti+1 −1. µi =. 1 si. ここで n =. ti+1 −1 1 xj , σi = x2j − µ2i si. j=t. S i i=1. j=ti. si であり，ti は i 番目のセグメン. トの開始時刻とする．セグメントを結合したときの平均と標準偏差が容易. 図 3 可逆圧縮のアルゴリズム Fig. 3 Algorithm for the lossless compression.. に計算できることは PSA の利点であるが，この利点の使い方は後に説明する．. 符号化にはほかにハフマン符号化11) や LZ77 符号化21) などがあるが，ランレングス符号化はワンパスで実行できるので高速処理に向いている．更新処理において圧縮されたデータはシーケンスごとにシーケンシャルファイルの形で格納する．これは探索処理においてシーケンスを参照するときに高速な. 3.5.2 距離の下限値と上限値の計算 ˆ Yˆ ) と上限値正確な距離 D(X, Y ) の下限値 L(X, ˆ Yˆ ) について説明する．下限値または上限値は U (X, 図 4 に示すとおり，問合せの長さより短いまたは長いセグメントを用いて計算する．定理 1 長さが l である 2 つのシーケンス Xl =. シーケンシャルアクセスができるようにするためであ. (xn−l+1 , . . . , xn ) と Yl = (yn−l+1 , . . . , yn ) が与えら. る．また圧縮されたデータは一定の大きさにはならな. れたとき，. いため，参照するときに用いるオフセットとともに格納される．. 3.5 PSA PSA はシーケンスの平均と標準偏差を特徴量として用いる距離の近似計算手法である．. 3.5.1 PSA における特徴量. ˆ l , Yˆl ) ≤ D(Xl , Yl ) L(X となる．ここで. S X Y 2. Y 2 ˆ ˆ L(Xl,Yl ) = si µX + σi −σi i −µi i=Slb. PSA ではシーケンスを S 個の特定の長さのセグメントに分割し，セグメントにおける平均と標準偏差を特徴量として距離の近似計算を行う．PSA を以下のように定義する．. (3).

(6) S

(7). Slb = min j

(8). si ≤ l. i=j. である．. 定義 1 （PSA）シーケンス X の i 番目のセグメントの平均を µi ，標準偏差を σi ，i 番目のセグメントの長さを si とすると，PSA における特徴量を以下. 定理 1 の証明は付録に示す．. ˆl , Yˆl ) 補助定理 1 （lower bounding lemma）L(X を用いれば探索漏れは発生しない．この補助定理は過去すでに研究されている1) ．. のように定義する．. ˆ = (µ1 , σ1 , s1 ,µ2 , σ2 , s2 ,. . .,µS , σS , sS ) X (2). 定理 2 2 つのシーケンス Xl = (xn−l+1 , . . . , xn ) と Yl = (yn−l+1 , . . . , yn ) が与えられたとき，. ˆ l , Yˆl ) ≥ D(Xl , Yl ) U (X. (4).

(9) 6. Mar. 2007. 情報処理学会論文誌：データベース. となる．ここで. S X Y 2. Y 2 ˆ ˆ U (Xl,Yl ) = si µX + σi +σi i −µi i=Sub. (5). Sub.

(10) . S

(11) = max j

(12) si ≥ l i=j. である．定理 2 の証明も付録に示す．. ˆl , Yˆl ) 補助定理 2 （upper bounding lemma）U (X を用いれば過剰探索は発生しない．証明：過剰探索が発生しないことを証明するには ˆl , Yˆl ) > であること D(Xl , Yl ) > であれば U (X. 図 5 セグメントの更新 Fig. 5 Updating segments.. を示せばよい．ここで式 (4) より D(Xl , Yl ) > であ ˆl , Yˆl ) となるので，過剰探れば < D(Xl , Yl ) ≤ U (X 索は発生しない．. 2. 3.5.3 セグメント長さの管理方法 PSA では 1 つのシーケンスにおいて各セグメントの長さは異なる．しかしすべてのシーケンスにおいて対応するセグメントの長さは同じであり，i 番目のセグメントの長さは同じである．セグメントの長さを決定するために処理時刻からの経過時間によってセグメントのレベル分けを行う．図 4 に示すようにセグメントの長さ si はレベル h に依存し，h が大きくなるに従って大きくなる．レベル h のセグメントの長さは 2h である．このようにするのは任意の長さの問合せシーケンスに対応するためである．すなわち問合せシーケンスが短い場合も長い場合も PSA で下限値と上限値を計算したときの相対的な誤差は同等になる．. Algorithm UpdatePSA(xn+1 ) compute the (S + 1)-th segment from xn+1 ; S = S + 1; i = S − c0 ; c0 = c0 + 1; //H is the maximum number of h for sequence X for h = 0 to H do if ch > C then combine the i-th and (i + 1)-th segments (compute a new segment for level h + 1); ch = ch − 2; S = S − 1; i = i − ch+1 ; ch+1 = ch+1 + 1; else break; end if end for 図 6 PSA の更新アルゴリズム Fig. 6 Algorithm of update PSA.. 特徴量の更新は各レベル h のセグメントの個数が. C より大きくなるときに結合することでインクリメンタルに行う．C = 2 であるときの具体的な更新方法を図 5 を用いて説明する．ci をレベル i におけるセグ. 示す．. DAPSS においてはセグメントごとにそれに対応す. メントの個数とする．更新前のセグメントは c0 = 2，. るデータシーケンスが格納されている．そのためセグ. c1 = 2，c2 = 1 である．ここでシーケンスデータ xn+1 が流入してくると c0 = 3 となる．C = 2 であるので，. メントを結合するときは，シーケンシャルファイルの中のデータシーケンスの位置も更新する．すなわち i. レベル 0 のはじめの 2 つのセグメントを結合してレベ. 番目と i + 1 番目のセグメントを結合したとき，新し. ル 1 のセグメントを作成する．すると c1 = 3 となる. いセグメントのオフセットとして i 番目のセグメント. ので，同様に処理する．結果として更新後のセグメン. のオフセットを用いる．. トは c0 = 1，c1 = 1，c2 = 2 となる．. 圧縮格納されたシーケンスにはオフセットを用いて. セグメントは容易に結合できる．すなわち i 番目と. 参照する．圧縮格納データの参照アルゴリズムを図 7. i+1 番目のセグメントを結合したとき，新しいセグメントの特徴量 µi , σi , si はそれぞれ µi = (µi +µi+1 )/2，. に示す．参照アルゴリズムでは圧縮されたデータを Slb. . 2 σi = (σi2 + σi+1 )/2 + (µi − µi+1 )2 /4，si = 2si となる．特徴量の更新方法のアルゴリズムを図 6 に. 番目のセグメントからファイルの終わりまで取り出す．そして図 3 の圧縮アルゴリズムを逆にたどることによってデータを解凍する．後に述べるようにメモリに.

(13) Vol. 48. No. SIG 7(TOD 33). 7. 大量データストリームの類似探索手法. Algorithm LoadData(Xl ) fetch the compressed data starting from the offset of the Slb -th segment; decompress the fetched data by RLE; while decompressed file is not end do for i = 1 to T do combine decompressed B bytes to recover the original sequence value; end for end while join the decompressed data and latest (t mod T ) values of Xl ; 図 7 圧縮格納データの参照アルゴリズム Fig. 7 Algorithm for loading compressed data.. R1. R2. R3. ˆ X. 3. 3. 4. R4 3. Yˆ. 4. 5. 3. 7. ˆ Z. 1. 3. 2. 3. =3 図 9 データ構造の例 Fig. 9 Example of data structure.. Algorithm CreateIndex select r reference points Ri (1 ≤ i ≤ r) randomly from the PSA set; //compute the index elements ˆ do for each PSA X for i = 1 to r do ˆ Ri ); compute L(X, end for end for 図 10 索引要素の計算アルゴリズム Fig. 10 Algorithm for computing index elements.. 3.6.2 フィルタリング ˆ と Yˆ をシーケンス X と Y の PSA 補助定理 3 X とし R を基準点とすると，以下のことが成り立つ． ˆ R) − L(Yˆ , R)| ≤ D(X, Y ) |L(X, 図 8 2 つの基準点による距離空間 Fig. 8 Metric space formed by two reference points.. 証明：三角不等式から以下のことが成り立つ. は最近 (t mod T ) 個のデータ値が保持されているため，解凍されてデータとメモリのデータを結合する．. 3.6 索. 引. 本論文では，複数の基準点とシーケンスの PSA の距離を索引付けし，非類似なシーケンスのペアを効率的に枝刈りする．これは，M-tree. 8). や mvp-tree. 4). (6). の. ように距離の公理に基づく距離関数を利用しているが，構造は非階層型である．データ構造がシンプルであるのは高速に索引を構築するためである．. 3.6.1 データ構造図 8 に示すように，PSA で近似後の多次元空間上に複数の基準点 Ri （1 ≤ i ≤ r，r = log(m)）を設定する．基準点はシーケンスの中からランダムに選択 ˆ Ri ) が付与さする．各シーケンスには r 個の値 L(X,. ˆ R) − L(Yˆ , R)| ≤ L(X, ˆ Yˆ ) |L(X, また式 (3) から以下のことが成り立つ. ˆ Yˆ ) ≤ D(X, Y ) L(X, よって. ˆ R) − L(Yˆ , R)| ≤ D(X, Y ) |L(X, が成り立つ．. 2. 補助定理 1 には距離の下限値を用いれば探索漏れを発生させずに探索できることが示されているが，補助定理 3 により索引を用いたフィルタリングが探索漏れを発生させないことが分かる．図 11 のアルゴリズムを用い，非類似なシーケンス. ˆ Ri ) は近似後のシーケンス X ˆ と Ri と距れる．L(X,. ペアのフィルタリングを行う．フィルタリングでは， ˆ Ri ) − L(Yˆ , Ri )| ≤ すべての基準点に対して |L(X,. 離の下限値である．図 8 のように，これらの値は基準. が成り立つかを計算する．図 9 の例では，シーケンス. 点によって形成される距離空間の中で r 個の円（中 ˆ Ri )）となる．図 9 に示す心点が Ri で半径が L(X, ˆ と Ri の距離の配列である．ように，データ構造は X. 似である．しかしシーケンス X と Z はすべての基準 ˆ Ri ) − L(Yˆ , Ri )| ≤ が成り立つた点に対して |L(X,. 索引を作成するためのアルゴリズムを図 10 に示す．. め類似候補となる．. X と Y は R4 において |3 − 7| > となるため非類. 3.7 更新処理 DAPSS はシーケンスの新しいデータ値を受信する.

(14) 8. Mar. 2007. 情報処理学会論文誌：データベース Algorithm IndexFiltering input: Yˆ. Algorithm Update input: new values at t for m data sequences X1 ,· · ·,Xm for each data sequence X do if t mod T = 0 then StoreData(XT ); end if ˆ =UpdatePSA(xt ); X end for. Algorithm Search input: threshold , query length l output: all similar subsequences pairs CreateIndex; for each data sequence Xl do ˆ l ); S =IndexFiltering(X if S = ∅ then for each data sequence Yˆl ∈ S do ˆl , Yˆl ) ≤ then if L(X ˆl , Yˆl ) ≤ then if U(X report Xl and Yl as a similar pair; else LoadData(Xl ); LoadData(Yl ); if D(Xl , Yl ) ≤ then report Xl and Yl as a similar pair; end if end if end if end for end if end for. 図 12 更新アルゴリズム Fig. 12 Update algorithm.. 図 13 探索アルゴリズム Fig. 13 Search algorithm.. output: the candidate set S S = ∅; for each PSA Yˆ do ˆ is the PSA of data sequences //X ˆ i )−L(Y,R ˆ i )| ≤ then if ∀ Ri : |L(X,R ˆ to S; add X end if end for 図 11 フィルタリングアルゴリズム Fig. 11 Filtering algorithm.. と更新処理を行う．更新処理のアルゴリズムを図 12. 補助定理 5 DAPSS に必要なメモリ量は. に示す．DAPSS は受信したデータから PSA の特徴. O(m log(n) +l) である．証明：m 個のシーケンスの PSA を保持するには. 量を更新する．さらにシーケンスデータは一定時間 T ごとに可逆圧縮されてからディスクに格納される．メモリに保持されるのは (t mod T ) 個のデータ値のみとなる．. 3.8 探索処理探索処理のアルゴリズムを図 13 に示す．まずデー. O(m log(n)) のメモリ量が必要である．また基準点が r（= log(m)）個の索引で長さが l の問合せを処理するにはそれぞれ O(m log(m)) と O(l) のメモリ量が必要である．m n であるので，DAPSS に必要なメモリ量は O(m log(n) +l) となる．. 2. タシーケンスの PSA から索引を作成し，探索解の候. メモリ使用量において DAPSS は時間が経過するご. 補を索引を用いて求める．求めた解候補に対し，PSA. とに長くなっていくシーケンスの影響を緩和できてい. によって距離の下限値と上限値を計算して類似判断を. ることが分かる．. する．もし下限値が閾値より大きければ，その解候. 補助定理 6 DAPSS の更新処理の計算量は平均 O(m) である．. 補は非類似ペアと判断する．距離の下限値が以下であり，かつ距離の上限値が以下であれば，その解候. 証明：レベル h におけるセグメントの PSA の特徴. 補を類似ペアと判断する．距離の下限値が以下であ. 量は 2h （h = 0, · · · , log n）時刻ごとに計算される．. り，かつ距離の上限値がより大きければ，ディスク. 1/2h = 2 であるので，DAPSS は m 個のシーケンスに対して時刻ごとに平均 O(m) 回特徴量を計算する．m 個のシーケンスに対する可逆圧縮において. に格納されたシーケンスを解凍参照し，正確な距離を計算し類似判断を行う．. 3.9 理論的分析 DAPSS は効果的に類似ペアを計算できることを示す．m を長さ n のデータシーケンスの数とし，l を問合せの長さとする．補助定理 4 ナイーブな手法には O(mn) のメモリ. log n h=0. RLE によるデータ値の圧縮は T 時刻ごとに O(mT ) だけ必要である．結果的に更新処理における計算量は平均 O(m) である．. 2 すなわち DAPSS の更新処理の計算コストはシーケンスの長さ n にかかわらず一定なコスト O(m) とな. 量と O(m2 l) の計算量が必要である．. る．一方，問合せの計算コストは索引や PSA の枝刈. 証明：ナイーブな手法はメモリ内に長さ n のシーケ. りの性能に依存する．そのため問合せの計算コストは. ンスを m 個保持する．そしてすべての m 個のシー. 複数のデータセットを用いて次の章で検証した．. ケンスの組合せに対して距離を計算する．. 2.

(15) Vol. 48. No. SIG 7(TOD 33). 9. 大量データストリームの類似探索手法. (a) Traffic. (b) FinTime. (c) Temperature. (d) Trajectory. 図 14 実験で用いたデータセット．それぞれのデータセットに対して 1 つのシーケンスを示す Fig. 14 Sequence data sets for the experiments. We plot one sequence out of each data set.. 4. 評価実験 DAPSS の有効性を検証するために実験を行った．. と Y 軸）のデータである．これらのデータセットは図 14 に示す．類似探索の閾値は問合せの長さ l に応じて増加さ. 実験ではナイーブな手法と比較を行った．ナイーブな. せ，Traffic に対して = 1.0 · l，FinTime に対して. 手法に必要なメモリ使用量は O(mn) であり，DAPSS に必要なメモリ量はそれより少ない O(m log(n) +l). = 0.1 · l，Temperature に対して = 0.02 · l，Trajectory に対して = 0.05 · l とした．またシーケンス. である．またナイーブな手法はすべてメモリ上で行わ. を圧縮する時刻間隔は T = 64 とし，各レベルのセグ. れるが，提案手法は I/O コストが発生する．実験は. メントの最大個数は C = 32 とした．. CPU が Pentium4 の 3.2 GHz，メインメモリが 1 GB のマシンで行った．実験には以下のデータセットを用いた．. の性能はデータ送受信の速度に依存する．データの送. • Traffic ：Peer-to-Peer ネットワーク内でのトラフィックから 400 個のデータを採取した．トラ. 実験はストリーム処理を模倣して行った．システム受信が遅いとそれが妨げになり，正しくシステムの性能を計測することが困難となる．そのため実験ではオフラインでメモリにデータをロードしてから処理速度. フィックデータはパケットを受信するたびに得ら. を計測した．またナイーブな手法と異なり，DAPSS. れるが，3 秒ごとに集約をした．. の探索処理はディスクアクセスをともなう．ディスク. • FinTime ：これは株価データのベンチマークである. 12). ．400 個の株価データの終値をデータとして. 用いた．. • Temperature ：複数の建物内で 55 のセンサで測定した温度データを用いた．それぞれのセンサは 30 秒ごとに測定を行う．40 個のシーケンスを実験に用いた．. のキャッシュの効果は DAPSS の処理速度を向上させることが考えられるが，キャッシュの効果はマシン環境に依存する．そこで DAPSS における探索時間はディスクのキャッシュをすべて消去した後に計測した．. 4.1 探索時間ナイーブな手法と DAPSS について探索時間の比較を行った．なお実験ではシーケンスの長さ n = 10000. • Trajectory ：ある展示会で計測された移動軌跡. とし，シーケンスの数は Traffic と FinTime で 400，. データのうち 80 人分を用いた．移動軌跡は 0.1. Temperature で 40，Trajectory で 80 とした．まず問合せシーケンスの長さを変化させて実験した．. 秒ごとに測定され，長さが 10000 の 2 次元（X 軸.

(16) 10. Mar. 2007. 情報処理学会論文誌：データベース. (a) Traffic. (b) FinTime. (c) Temperature. (d) Trajectory. 図 15 問合せの長さを変化させたときの探索時間 Fig. 15 Wall clock time versus query length.. (a) Traffic. (b) FinTime. (c) Temperature. (d) Trajectory. 図 16 データシーケンスの数を変化させたときの探索時間 Fig. 16 Wall clock time versus the number of data sequences.. 実験結果を図 15 に示す．DAPSS はナイーブな手法. が増加しても O(log(l)) 個の特徴量を用いて計算を行. と比較して最大 54 倍の高速な探索が行えた．ナイー. うため，探索コストが線形に増加せず，問合せ長の増. ブな手法では探索時間は問合せの長さ l が増加すると. 加の影響は抑えられている．. O(l) で増加する．しかし DAPSS では問合せの長さ. 次にシーケンスの数を変化させて実験した．探索時.

(17) Vol. 48. No. SIG 7(TOD 33). 大量データストリームの類似探索手法. 11. 間の実験結果を図 16 に示す．なお実験では問合せシー. 既存の近似手法としては PAA（Piecewise Aggregate. ケンスの長さ l = 8000 とした．DAPSS はナイーブな. Approximation）15) を選んだ．PAA は特徴量として. 手法と比較して最大 34 倍の高速な探索が行えた．ナ. シーケンスを等分に分割したセグメントの平均値を用. イーブな手法では探索時間はシーケンスの数 m が増. いる．PAA を既存の近似手法として選んだのは，(1). 2. 加すると O(m ) で増加する一方，DAPSS の計算コ. 探索漏れが発生せず非類似ペアを確実に枝刈りできる，. ストは図 16 に見られるように非常に O(m) に近い．. (2) 特徴量が高速に計算できデータストリームの処理. これは索引により類似シーケンスの候補を絞り込んで. に向いている，(3) セグメントを統合することにより. いるので，シーケンスの数の増加の影響は抑えられる. データストリームに対しても高速に更新できるためで. ためである．. 4.2 探索処理における絞り込み精度. ある．ほかの近似手法（SVD，DWT，DFT など）にはこのような特徴はない．. 正確な距離計算は高い計算コストと I/O コストを引. データセットとして Traffic を用いたが，ほかのデー. き起こすので，DAPSS の探索時間は正確な距離の計. タセットも同様の実験結果となった．提案手法と既存. 算回数に依存する．そのため探索処理における正確な. 手法を比較するために，PAA を直接 DAPSS の探索. 距離の計算回数を問合せシーケンスの長さを変化させ. アルゴリズム（図 13）に適用した．すなわちオリジナ. て検証した．実験結果を図 17 に示す．図 17 において. ルの PAA においてはシーケンスを等分に分割したセ. “Answer ” とあるのは，{Xl , Yl |D(Xl , Yl ) ≤ } を満. グメントの平均値を用いるが，性能比較を行うために PAA においても PSA と同様にシーケンスをべき乗. たす正解集合に含まれるシーケンスのペア数である．. DAPSS では，PSA の下限値と上限値によるフィルタリングの後，ディスクに格納されているオリジナルのシーケンスを用いて正確な距離を計算する．“Ex-. の大きさのセグメントに分割した．PSA に対して各レベルのセグメントの最大個数は C = 32 とした．また PAA に対しては C = 32（セグメントの数が PSA. act” とあるのは，正確な距離演算を行ったペアの数である．実験では Traffic を用い，シーケンスの長さ. と同じ）と C = 64（特徴量の数が PSA と同じ）の. n = 10000，シーケンスの数 m = 400 とした．結果を見ると，問合せシーケンスの長さにかかわらず正解集合の数と比較して正確な距離の計算回数を大. 図 18 は下限値による PSA と PAA の枝刈り効果を示している．“Answer ” とあるのは図 17 と同様に正. 幅に低減できていることが分かる．距離の上限値が . とあるのは近似手法に PSA を用いたときの類似ペア. 2 つの設定をした．. 解集合に含まれるシーケンスのペア数である．“PSA”. 以下であれば，類似ペアの候補は正確な距離を計算せ. 候補の数である．“PAA-32” とあるのは近似手法に. ずに類似ペアとして判断される．すなわち上限値の効. C = 32 の PAA を用いたときの類似ペア候補の数である．“PAA-64” とあるのは近似手法に C = 64 の. 果により，DAPSS は図 15 と図 16 にみられる高速な. 4.3 PSA による枝刈り効果と探索コスト PSA の有効性を既存手法と比較することで明らか. PAA を用いたときの類似ペア候補の数である．図 18 より，PSA は正解集合より平均 10%しか候補ペア数が多くないが，PAA は C = 32 のとき正解集合より. にする．実験では距離の下限値と上限値の近似精度. 平均 25%，C = 64 のとき平均 15%候補ペア数が多. を調べた．近似精度が高いほどデータシーケンスの. くなることが分かる．C = 64 の PAA は C = 32 の. 中から類似ペアをより高速に計算することができる．. PSA よりシーケンスが半分のサイズにセグメントに. 探索を行える．. 図 17 正確な距離の計算回数 Fig. 17 Number of exact distance computations.. 図 18 PSA の枝刈り効果 Fig. 18 Pruning power of PSA..

(18) 12. Mar. 2007. 情報処理学会論文誌：データベース. 図 19 PSA の探索コスト Fig. 19 Search time of PSA.. 図 20 更新時間 Fig. 20 Update time.. 分割されるが（図 4 参照），PSA は PAA より高い近似精度を有していることが分かった．. PSA が PAA より近似精度が高いのは平均値のみでなく標準偏差でもシーケンスを近似しているからである．たとえば FinTime のようにシーケンスのデータ値の分散が大きい場合，PSA では平均値からの差を標準偏差で表すことができるので近似誤差が小さくなる．また Trajectory のようにシーケンスのデータ値の分散が小さい場合，平均値のみでほぼシーケンスを表すことができるので近似誤差が小さくなる．このと. 図 21 圧縮率 Fig. 21 Compression rate.. き分散が小さいのでセグメントを大きくしてもそれほど近似精度に影響はない．図 19 は問合せの長さを変えたときの探索時間を示. 場合の処理時間であり，“Traffic(store)” と “Trajec-. tory(store)” は圧縮格納も行う場合の処理時間である．. している．“PSA” とあるのは近似手法に PSA を用. ほかのデータセットの結果は Traffic と Trajectory と. いたときの探索時間である．“PAA-32” とあるのは近. 似ているため省略した．. 似手法に C = 32 の PAA を用いたときの探索時間. 更新時間は探索時間と比較して非常に小さい．さら. である．“PAA-64” とあるのは近似手法に C = 64. に更新時間はシーケンスの長さ n に対してほぼ一定で. の PAA を用いたときの探索時間である．図 19 から. あることが分かる．これは 3.9 節で議論したように，. PSA は PAA よりおよそ 3 倍高速に探索できることがいることより，正確な距離計算の回数を低減化するこ. DAPSS の更新時間はシーケンスの長さにかかわらず O(m) であることを裏付ける結果となっている．また Trajectory は 2 次元のシーケンスであるにもか. 分かる．図 17 に示されるように，距離の上限値を用とができる．しかし PAA では距離の上限値を計算で. かわらず，“Trajectory(store)” の更新コストは “Traf-. きないので，下限値で求めた類似ペアの候補すべてに. fic(store)” より小さくなった．これは図 21 に示すと. 対して正確な距離を計算しなければならない．また，. おり，Trajectory に対してランレングス符号化による. 図 19 より，PAA を用いたときは C = 32 であっても C = 64 であっても探索時間はそれほど変わらない. 圧縮が効果的であったためである．実験に用いた Trajectory においてしばしば移動体が停止することがあっ. ことが分かる．C = 64 であるときの方が C = 32 で. たため，シーケンスデータがより効果的に圧縮され，. あるときよりも距離の下限値による枝刈り効果が高い. 高速にディスクに格納することができた．. ものの，C = 64 であるときの方が近似距離の計算に時間がかかるため，このような結果が得られる．. 4.4 更新時間. 5. まとめ本論文では流入する複数の任意長のシーケンスのう. Traffic と Trajectory の 1 つのデータ値を受信したときの 1 つのシーケンスあたりの更新時間について. ち，類似した組合せを探索する問題について取り組ん. 調査した．実験結果を図 20 に示す．図 20 において. 理を高速，正確，省メモリで行えることを示した．. “Traffic” と “Trajectory” は PSA の更新のみを行う. だ．本論文では DAPSS を用いることによってこの処. DAPSS については，3 つの手法を提案した．可逆.

(19) Vol. 48. No. SIG 7(TOD 33). 大量データストリームの類似探索手法. 圧縮手法により，高速に流入するシーケンスを高速かつ小容量で格納できる．PSA はシーケンスが長くなっても高速に類似シーケンスの候補を絞り込める．距離配列に基づく索引を用いることにより，シーケンスが多くなっても高速に類似シーケンスの候補を絞り込むことができる．実データを用いた実験を行うことにより，DAPSS の性能を検証しその有効性を示した．. 参. 考文. 献. 1) Agrawal, R., Faloutsos, C. and Swami, A.N.: Efficient Similarity Search In Sequence Databases, FODO, pp.69–84 (1993). 2) Babcock, B., Babu, S., Datar, M., Motwani, R. and Widom, J.: Models and Issues in Data Stream Systems, PODS, pp.1–16 (2002). 3) Beckmann, N., Kriegel, H.-P., Schneider, R. and Seeger, B.: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles, SIGMOD Conference, pp.322–331 (1990). ¨ 4) Bozkaya, T. and Ozsoyoglu, Z.M.: DistanceBased Indexing for High-Dimensional Metric Spaces, SIGMOD Conference, pp.357–368 (1997). 5) Bulut, A. and Singh, A.K.: A Unified Framework for Monitoring Data Streams in Real Time, ICDE, pp.44–55 (2005). 6) Burrows, M. and Wheeler, D.J.: A blocksorting lossless data compression algorithm, Technical Report 124, SRC Research Report (1994). 7) Cai, Y. and Ng, R.T.: Indexing SpatioTemporal Trajectories with Chebyshev Polynomials, SIGMOD Conference, pp.599–610 (2004). 8) Ciaccia, P., Patella, M. and Zezula, P.: Mtree: An Efficient Access Method for Similarity Search in Metric Spaces, VLDB, pp.426–435 (1997). 9) Faloutsos, C., Ranganathan, M. and Manolopoulos, Y.: Fast Subsequence Matching in Time-Series Databases, SIGMOD Conference, pp.419–429 (1994). 10) Fujiwara, Y., Sakurai, Y. and Yamamuro, M.: DAPSS: Exact Subsequence Matching for Data Streams, DASFAA, pp.80–94 (2006). 11) Huffman, D.: A method for the construction of minimum redundancy codes, Proc.IRE, Vol.40, pp.1098–1101 (1952). 12) Jacob, K.J. and Shasha, D.: FinTime — A Financial Time Series Benchmark, SIGMOD Record, Vol.28, No.4, pp.42–48 (1999). 13) Katayama, N. and Satoh, S.: The SR-tree: An. 13. Index Structure for High-Dimensional Nearest Neighbor Queries, SIGMOD Conference, pp.369–380 (1997). 14) Keogh, E.J., Chakrabarti, K., Mehrotra, S. and Pazzani, M.J.: Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases, SIGMOD Conference, pp.188–228 (2001). 15) Keogh, E.J., Chakrabarti, K., Pazzani, M.J. and Mehrotra, S.: Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases, Knowl. Inf. Syst., Vol.3, No.3, pp.263–286 (2001). 16) Korn, F., Jagadish, H.V. and Faloutsos, C.: Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences, SIGMOD Conference, pp.289–300 (1997). 17) Moon, Y.-S., Whang, K.-Y. and Han, W.-S.: General match: A subsequence matching method in time-series databases based on generalized windows, SIGMOD Conference, pp.382–393 (2002). 18) pong Chan, K. and Fu, A.W.-C.: Efficient Time Series Matching by Wavelets, ICDE, pp.126–133 (1999). 19) Sakurai, Y., Yoshikawa, M., Uemura, S. and Kojima, H.: The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, VLDB, pp.516–526 (2000). 20) Zhu, Y. and Shasha, D.: StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time, VLDB, pp.358–369 (2002). 21) Ziv, J. and Lempel, A.: A Universal Algorithm for Sequential Data Compression, IEEE Trans. Information Theory, Vol.23, No.3, pp.337–343 (1977).. 付. 録. A.1 PSA の距離関数の証明 ˆl , Yˆl ) ≤ D(Xl , Yl ) ≤ U (X ˆl , Yˆl ) となることの L(X 証明を示す． ˆl , Yˆl ) ≤ D(Xl , Yl ) となることを証明 1 まず L(X 示す．. D(Xl , Yl ) はユークリッド距離なので k ≥ 1 とすると明らかに以下のことが成り立つ．. n (xi −yi )2 i=n−l+k. S si = (xi:j −yi:j )2 ≤ D(X, Y ) i=Slb j=1.

(20) 14. Mar. 2007. 情報処理学会論文誌：データベース. ここで xi:j は i 番目のセグメント化されたシーケンスの j 番目の値とする．∆xi:j = µi − xi:j とすると. si. ∆xi:j = 0 であるので， j=1. 2001 年早稲田大学理工学部電気電子情報工学科卒業．2003 年同大. si . 学大学院理工学研究科修士課程修了．. (xi:j − yi:j )2. 2003 年日本電信電話株式会社入社． DEWS2006 優秀論文賞受賞．時系. j=1 Y 2 = si (µX i −µi ) si . si . j=1. j=1. +. 藤原靖宏. {(∆xi:j )2+(∆yi:j )2 }−2. ∆xi:j ∆yi:j. Y 2 = si (µX i −µi ). . +si (σiX )2+ (σiY )2−. si 2. si. 列データ処理の研究開発に従事．電子情報通信学会，. ∆xi:j ∆yi:j. j=1. ∆xi:j はベクトルの 1 つの要素と見なせるので，内積の定義より 1 ∆xi:j ∆yi:j = σiX σiY cosθi si si. j=1. 日本データベース学会各会員．櫻井保志（正会員）. 1991 年同志社大学工学部電気工学科卒業．1991 年日本電信電話（株）入社．1999 年奈良先端科学技術大学院大学情報科学研究科博士後期課程修了．博士（工学）．2004∼2005 年カーネギーメロン大学客員研究員．本会平成 16 年度論文賞受賞．索引技術，データストリーム処理の研究開発に従事．ACM，電子情報通信学会，日本デー. となる．ここで θi はベクトル ∆xi と ∆yi の角度と. タベース学会各会員．. する．cosθi ≤ 1 なので，. S X Y 2. Y 2 ˆ ˆ L(X, Y ) = si µX + σi −σi i −µi i=Slb. n ≤ (xi − yi )2 ≤ D(X, Y ) i=n−l+k. となる．同様に k ≤ 1 で cosθi ≥ 1 とすれば ˆ Yˆ ) であることも証明できる． 2 D(X, Y ) ≤ U (X,. (平成 18 年 9 月 20 日受付) (平成 19 年 1 月 9 日採録) （担当編集委員. 片山紀生）. 山室雅司（正会員）. 1987 年早稲田大学大学院理工学研究科数学専攻修了．1987 年日本電信電話（株）入社．1990 年コロンビア大学大学院電気工学専攻修了．ディジタル情報流通，データベース設計法の研究開発に従事．本会平成 5 年度学術奨励賞受賞．博士（工学）．IEEE-CS，日本ソフトウェア学会，電子情報通信学会，日本データベース学会各会員．.

(21)