日本データベース学会 データドリブンスタディーズ
一般論文

Vol. 2, Article No. 1, 2024 年 3 月

複合的ストリーム処理に対するト

トリーム処理においても同様の傾向がある．そうした複合的スト

レーサビリティの研究を説明するために重要な情報であるため，従来の入力データのみ

リーム処理では，AI/ML 処理の判断根拠が分析結果の導出理由を提示する Lineage だけでは十分にトレーサビリティを保証する

山田 真也 1

ことができない問題がある．ここで以下のような例を考える．

北川 博之 2

Salman Ahmed Shaikh3

例 1 図 1 はストリーム処理を用いたリアルタイムレビュー分析

天笠 俊之 4を示している．この分析処理は 4 つの属性（製品 ID，顧客 ID，

的野 晃整 5

レビューコメント，タイムスタンプ）から構成されるタプルを受け取ると，タプルの検証，感情分類モデルの適用，製品ごとのPositive/Negative 数のカウントを行ったのち，最後に分析結果をデータ来歴（Lineage）とは分析結果の元になった入力データ

次のシステムに送信する．

を提示することを指し，分析処理のトレーサビリティを保証する

ここであるユーザが分析結果 ⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩ がなぜ導出さため活用されている．しかし，近年の AI や機械学習モデルを用れたのか知りたいと考えたとする．従来の Lineage を用いると，いた処理（AI/ML 処理）を伴う分析を考えると Lineage だけでは{⟨1, 𝐶001, “Wrong one . . .” , 10000⟩, ⟨1, 𝐶002, “This toy . . .”,10005⟩, ⟨1, 𝐶003, “Some parts . . .” , 10010⟩} の 3 タプルをその問題がある．これまで著者らは，AI/ML 処理を伴う複合的データ分析処理では単に Lineage を提示するだけでなく，AI/ML 処理の分析結果の元になったデータとして提示することができる．しか分析結果の導出理由を説明する判断根拠も併せて提示する必要があることに着目し，拡張来歴について研究してきた．しかしながしこの 3 つのタプルを提示するだけでは，なぜ感情分類モデルがら従来の拡張来歴は静的なデータモデルである関係モデルに基づ

それらのタプルを Negative と判定したのか理解することができないという問題が生じる．つまりこのことは複合的ストリーム処

いており，近年広く活用されているストリーム処理に対して適用

理において，従来の Lineage だけではトレーサビリティを保証すできないという問題があった．そこで本稿では，複合的ストリーることができないという問題を表している．

ム処理に対して拡張来歴を導出する枠組みについて説明する．

この問題を解決するために本研究では，感情分類モデルがな

1

ぜそれらのタプルのコメントを Negative と判断したのか説明すはじめにるために，AI/ML 処理の判断根拠を併せて提示するというアプ

スマートフォンやセンサ等の IoT 機器の普及により，日々，膨ローチをとる．具体的には「タイムスタンプが 10000 の入力タ

大なストリームデータが生成されている．ストリームデータから

プルは 1 ワード目に “Wrong” という単語があったため Negative

リアルタイムに知識を抽出するために，ストリーム処理エンジンと判定し，10005 の入力タプルは 4 ワード目に “broken” というが広く用いられているが，そうして抽出されたデータや知識を信単語があったため Negative と判定し，10010 の入力タプルは 4–5

頼して活用するためには，データ分析のトレーサビリティが不可

ワード目に “not arrived” があったため Negative と判定した」と欠である．そのためには分析処理の利用者になぜその分析結果がいう判断根拠の情報を，従来の Lineage と併せて提示することで得られたかを説明することが重要である．

複合的ストリーム処理におけるトレーサビリティの保証を可能に

分析結果のトレーサビリティはこれまで，データベースシス

する．

テム，科学ワークフロー，ビッグデータ処理システムなど様々

著者らはこれまで AI/ML 処理を伴う複合的データ分析処理にな領域で研究が行われてきている [1–3]．その中でも，データ来対して，通常の Lineage に加えて AI/ML 処理の判断根拠を提示

歴（Lineage）は分析結果のもとになった入力データを提示する

する拡張来歴について研究してきた [8, 9]．しかしながら従来のことを指し，特にデータベースの分野において研究が行われてき拡張来歴は，関係データやファイルデータのような静的なデータ

た [4, 5]．さらにストリーム処理を対象にした Lineage 導出シス

モデルを前提としており，動的なストリーム処理に対して適用すテムの検討も始まっている [6, 7]．

ることができないという問題があった．

近年，社会で活用されているデータ分析処理は AI や機械学習

そうした背景から著者らは複合的ストリーム処理のトレーサビ

モデルを用いた処理（AI/ML 処理）を伴うことが増えており，ス

リティを保証するため，ストリーム処理を対象に拡張来歴を導出する枠組みを提案した [10]．本稿ではその内容に基づき複合的

1 学生会員

筑波大学大学院理工情報生命学術院システム情報工学研究群／産業
技術総合研究所人工知能研究センター

ストリーム処理に対して拡張来歴を導出するシステムを説明する
が，1) 導出手法をより理解しやすい例の使用，2) 導出アルゴリズ

yamada@kde.cs.tsukuba.ac.jp
2 正会員

筑波大学国際統合睡眠医科学研究機構／産業技術総合研究所人工知能
研究センタームの詳細な説明の追加，3) Traversal 時間に関する実験データの追加，4) 従来の分析結果のより適切な統計的手法を用いた比較 のkitagawa@cs.tsukuba.ac.jp
3 正会員

産業技術総合研究所人工知能研究センター

4 点で拡張を行っている．本稿で説明するシステムは，ストリー

shaikh.salman@aist.go.jp
4 正会員

ム処理に対して Lineage 導出を行うフレームワーク GeneaLog を

筑波大学計算科学研究センター

ベースとした．Apache Flink 上で実行される複合的ストリーム処amagasa@cs.tsukuba.ac.jp
5 正会員

産業技術総合研究所人工知能研究センター理に対して拡張来歴を導出するプロトタイプシステムの開発を行

a.matono@aist.go.jp

1

日本データベース学会 データドリブンスタディーズ
一般論文

Vol. 2, Article No. 1, 2024 年 3 月

製品ID

顧客ID

レビュー
コメント

タイム
スタンプ

製品ID

顧客ID

レビュー
感情

タイム
スタンプ

1

C001

Wrong one wasarrived, and…

10000

1

C001

Negative

10000

C002

This toy was
broken when…

1

C002

Negative

10005

1

C003

Some parts were
not arrived.

10010

1

C003

Negative

10010

…

…

…

…

…

…

…

…

1

タプル入力

10005

タプル検証

感情分類

カウント

タプル出力

製品ID

レビュー
感情

カウント

1

Negative

3

…

…

…

図 1 複合的ストリーム処理の例．感情分類モデルを用いたリアルタイムレビュー分析．点線で囲われているタプルは分析結果⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩ の Lineage を表す．

い，プロトタイプシステムを用いた評価実験を行った．実験では義する必要がある．しかしながら，実行する分析処理に応じて多本稿で説明したシステムがレイテンシ／スループットの点で非常様なオペレータが組み合わせられる近年のストリーム処理においに小さいコストで拡張来歴を導出することを示す．

て，全ての入出力関係をあらかじめ定義することは容易でない．

本稿の構成は以下の通りである．まず 2 節で関連研究について[6] と [7] はよりモダンなストリーム処理エンジンに対して説明する．次に 3 節で本稿が使用するストリーム処理モデルとLineage を導出する研究である．Ariadne [6] は処理を記述する各

GeneaLog の説明を行い， 4 節でストリーム処理に対して拡張来オペレータを拡張し，導出されるタプルに元になったタプルを識歴を導出する手法を説明する．そして 5 節でプロトタイプシステ

別するアノテーションを付与することで Lineage を求める枠組み

ムを用いた評価実験の結果を示す．最後に 6 節で結論と今後の課である．しかしながら [7] でも示されているように，タプルに付題を述べる．

与されるアノテーションのサイズがタプルに貢献した入力タプ

2

関連研究

2.1

データベース問い合わせにおける来歴研究

ルの数に比例するため，分析処理によっては非常に大きなオーバ
ヘッドが発生することがある．そうした背景から GeneaLog [7]ではタプルにアノテーションを付与する際，アノテーションのサ

これまでデータベース問い合わせの来歴を導出する手法がいく

イズを，入力タプル数に依存しない固定サイズにする手法を提案

つも提案されている [5, 11, 12]．[5, 11] は関係データモデルでモした．さらに評価実験を通して GeneaLog が Ariadne より小さい

デル化された問い合わせに対して，タプルレベルの来歴を導出す

オーバヘッドで Lineage を導出することを示した．このことからる研究である．[5] は Tracing Query と呼ばれる逆クエリを用い本稿の手法の実装は GeneaLog に基づいている．GeneaLog の概て分析結果の Lineage を求める手法であり，[11] は全ての入力タ

要については次節で説明する．

プルに識別子を事前に割り当て，識別子を分析結果まで継承する

ストリーム処理モデルと Lineage

3

ことで元になったタプルを提示する手法である．より一般的な問い合わせに対する来歴研究も存在しており，[12] は XQuery に対

3.1

ストリーム処理モデル

して来歴を導出する枠組みを提案している．さらに MapReduce

ストリーム 𝑆 は無限長のタプルのシーケンスで構成され，タや Spark のようなビッグデータ処理システムにおける来歴を対象

プル 𝑡 はタイムスタンプ 𝜏 と属性値をもつ (𝑡 = ⟨𝜏, 𝑎 1 , . . . , 𝑎 𝑚 ⟩)．

とするものも存在する [3, 13]．しかしながらこれらの枠組みは単ストリーム処理はノードがオペレータ，エッジがデータフローのに分析結果の元になった入力データを提示するもので，AI/ML 処

DAG 構造として表すことができ，オペレータは 1（または 2）入理を伴う複合的データ分析処理に対して十分なトレーサビリティ

力ストリームを受け取ると 1 出力ストリームを出力する．

を保証することができない．こうした背景から著者らは [8, 9] でストリーム処理を構成するオペレータはいくつも存在するが，従来の Lineage に加えて AI/ML 処理の判断根拠を併せて提示す

それらは 3 種類に分類できる [7]．1 つ目は I/O で，具体的なオる拡張来歴を提案した．しかしながら [8, 9] で提案した枠組みはペレータしては Source と Sink オペレータがこれに該当する．こ静的データに対する問い合わせを対象としており，ストリーム処

れらのオペレータは，ストリーム処理に対して外部のシステムか理には適用することができないという問題がある．

らデータを取り込む，または外部のシステムにストリーム処理結

2.2

果を送信する役割を持つ．2 つ目は Transformer で，具体的にはストリーム処理における来歴研究ストリーム処理に対して来歴を導出する枠組みの研究はまだ十Map や Filter，Union，Aggregate，Join オペレータが該当する．

分に行われていない．初期の研究として [14] は，出力ストリーム

ここで Aggregate や Join オペレータは，入力ストリームをウインにどの入力ストリームが貢献しているのかを提示することができドウに分割し，それぞれのウインドウごとに集約/結合処理を実行

るが，提示可能な来歴の粒度が非常に粗いという問題がある．そするようなオペレータを指している．3 つ目は Send と Receiveのためこの手法では，どのタプルが分析結果に貢献したのか提示

オペレータで，これらはスレッド間でタプルをやり取りするためすることはできない．[15] はタプルのタイムスタンプに基づいてに用いられる．

元になった入力タプルを提示する研究であるが，全てのオペレー

図 2(a) は，2 つの Source オペレータ，3 つの Transformer，1タに対して入力タプルと出力タプルの対応関係を表すルールを定つの Sink オペレータで構成されるストリーム処理を表している．

2

日本データベース学会 データドリブンスタディーズ
一般論文

Vol. 2, Article No. 1, 2024 年 3 月…
…

Sourceオペレータの
出⼒タプル

…

U1

…

<latexit sha1_base64="F7IJMlZsGyqyBuQIFEqkCZ4Jw2Y=">AAACZnichVFNSwJBGH7cvsw+tCIKukhi2EXGkIpOUpeOfuQHmMjuNtriurvsroJJfyDomodOBRHRz+jSH+jgPyg6GnTp0Ou6ECXVO8zMM8+8zzvPzEiGqlg2Y12PMDI6Nj7hnfRNTc/M+gNz8zlLb5gyz8q6qpsFSbS4qmg8ayu2yguGycW6pPK8VNvr7+eb3LQUXTuwWwYv1cWqplQUWbSJykTE9XIgxKLMieAwiLkgBDeSeuAWhziCDhkN1MGhwSasQoRFrYgYGAziSmgTZxJSnH2OU/hI26AsThkisTUaq7QquqxG635Ny1HLdIpK3SRlEGH2xO5Yjz2ye/bCPn6t1XZq9L20aJYGWm6U/WfLmfd/VXWabRx/qf70bKOCbcerQt4Nh+nfQh7omyedXmYnHW6vsWv2Sv6vWJc90A205pt8k+LpS/joA2I/n3sY5Daisc1oPBUPJXbdr/BiBauI0HtvIYF9JJGlc6s4xwU6nmdhVlgUlgapgsfVLOBbCMFPuLyKTw==</latexit>

Mapオペレータの出⼒タプル<latexit sha1_base64="I5epLVbt3LLr0r5HxpCJj+9o5Us=">AAACZnichVFNSwJBGH7cvsw+tCIKukhi2EXGkIpOUpeOfuQHmMjuNtriurvsroJJfyDomodOBRHRz+jSH+jgPyg6GnTp0Ou6ECXVO8zMM8+8zzvPzEiGqlg2Y12PMDI6Nj7hnfRNTc/M+gNz8zlLb5gyz8q6qpsFSbS4qmg8ayu2yguGycW6pPK8VNvr7+eb3LQUXTuwWwYv1cWqplQUWbSJykSk9XIgxKLMieAwiLkgBDeSeuAWhziCDhkN1MGhwSasQoRFrYgYGAziSmgTZxJSnH2OU/hI26AsThkisTUaq7QquqxG635Ny1HLdIpK3SRlEGH2xO5Yjz2ye/bCPn6t1XZq9L20aJYGWm6U/WfLmfd/VXWabRx/qf70bKOCbcerQt4Nh+nfQh7omyedXmYnHW6vsWv2Sv6vWJc90A205pt8k+LpS/joA2I/n3sY5Daisc1oPBUPJXbdr/BiBauI0HtvIYF9JJGlc6s4xwU6nmdhVlgUlgapgsfVLOBbCMFPur2KUA==</latexit>

(a)

(b)

U1
Next

U1

U2

Aggregateオペレータの
出⼒タプル

S

…

U1
Next

S

R

S

R

…

S

R

S

R

図3

…

貢献グラフ

…
S

例 2 ウインドウに含まれるタプル 𝑡 𝑖𝑛1 , . . . , 𝑡 𝑖𝑛𝑛 を受け取ると<latexit sha1_base64="MMDwUVGHCc6Xdw9DdWDdkgsukxk=">AAACZnichVFNSwJBGH7cvsw+tCIKukhi2EXGkIpOUpeOfuQHmMjuNtriurvsroJJfyDomodOBRHRz+jSH+jgPyg6GnTp0Ou6ECXVO8zMM8+8zzvPzEiGqlg2Y12PMDI6Nj7hnfRNTc/M+gNz8zlLb5gyz8q6qpsFSbS4qmg8ayu2yguGycW6pPK8VNvr7+eb3LQUXTuwWwYv1cWqplQUWbSJykTk9XIgxKLMieAwiLkgBDeSeuAWhziCDhkN1MGhwSasQoRFrYgYGAziSmgTZxJSnH2OU/hI26AsThkisTUaq7QquqxG635Ny1HLdIpK3SRlEGH2xO5Yjz2ye/bCPn6t1XZq9L20aJYGWm6U/WfLmfd/VXWabRx/qf70bKOCbcerQt4Nh+nfQh7omyedXmYnHW6vsWv2Sv6vWJc90A205pt8k+LpS/joA2I/n3sY5Daisc1oPBUPJXbdr/BiBauI0HtvIYF9JJGlc6s4xwU6nmdhVlgUlgapgsfVLOBbCMFPvL6KUQ==</latexit>(c)𝑡 𝑜𝑢𝑡 を返す Aggregate オペレータを考える．Lineage 導出のため

図 2 ストリーム処理フローの表記． (a) 論理表記． (b) 物理表に拡張された Aggregate オペレータは，通常の集約結果を求める記． (c) Send (S) / Receive (R) オペレータの導入．

と同時に下記のように入力／出力タプルのメタデータをセットする．

1. 𝑡 𝑜𝑢𝑡 .𝑇 𝑦 𝑝𝑒 = 𝐴𝑔𝑔𝑟𝑒𝑔𝑎𝑡𝑖𝑜𝑛

この表記はストリーム処理を論理的に記述したもので，本稿では

2. 𝑡 𝑜𝑢𝑡 .𝑈1 = 𝑡𝑖𝑛𝑛 ，𝑡 𝑜𝑢𝑡 .𝑈2 = 𝑡𝑖𝑛1

ストリーム処理の論理表記と呼ぶ．しかしストリーム処理が実際

3. 𝑡𝑖𝑛𝑖 .𝑁𝑒𝑥𝑡 = 𝑡𝑖𝑛𝑖+1 (𝑖 = 1, . . . , 𝑛 − 1)にストリーム処理エンジン上で実行されるとき，各オペレータは複数のオペレータインスタンスに展開され，それぞれが並列に処

他のオペレータに対する Operator instrumentation は，基本的理を行う．図 2(b) は展開されたオペレータインスタンスを表しに Type と元になった入力タプルに U1 と U2 ポインタをセットており，ストリーム処理の物理表記と呼ぶ．ストリーム処理エンするよう拡張する．詳細は [10] を参照いただきたい．

ジンではスレッドが処理の実行単位になり，図中の四角が 1 ス

貢献グラフを用いた Lineage 導出: Operator instrumentation でレッドを指している．実行するストリーム処理が複数スレッド拡張されたストリーム処理の分析結果 𝑡 は，直前のオペレータにで実行される場合には，タプルをスレッド間でやり取りする必おける入力タプルを， 𝑡 のメタデータに含まれるポインタで参要がある．そのために Send オペレータがスレッドの最後のオペ

照することができる．さらにその入力タプルもまた，直前のオペ

レータの後ろに挿入され，Receive オペレータがスレッドの先頭

レータにおける入力タプルをポインタで参照できる．そのために挿入される (図 2(c))．Send と Receive オペレータはタプルをLineage はタプルのポインタを再帰的に辿ることで得ることがで

スレッド間でやり取りする際，タプルのシリアライズ／デシリア

きる．例えば図 1 に示したストリーム処理の分析結果は，図 3 のライズも併せて行う．

ように，タプルがノード，ポインタがエッジのグラフ構造を得る

3.2

ことができる．これを貢献グラフと呼ぶ．図 3 の下のノードは分GeneaLog

本節で，本稿の拡張来歴導出手法や実装のベースになっている析結果 (⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩) を表し，そこからポインタでつながる

GeneaLog [7] を説明する．GeneaLog はストリーム処理に対してノードは Map（感情分類）オペレータの出力タプル，一番上のLineage を導出する State-of-the-art の枠組みで，各オペレータがノードは Source オペレータの出力タプル（分析処理における入生成する全てのタプルにメタデータを追加する．そして Lineage

力タプル）を表している．そのため貢献グラフを用いて Lineage

を求める際にはこのメタデータを手がかりに，元になった入力を求めるためには，辿ったタプルの Type が Source になるまで再タプルを導出する．Lineage を導出するためにはこのメタデータ

帰的にグラフを辿ればよい．

をセットするようにオペレータを拡張する必要があり，これをクラスタ環境における Lineage 導出: クラスタ環境のように 1

Operator instrumentation と呼ぶ．これから GeneaLog の概要をつのストリーム処理が複数のスレッドにまたがって実行される

説明する．

ケースで Lineage を導出する際には，スレッド間通信についてもメタデータ: 全てのタプルに追加されるメタデータは，Type,考慮する必要がある．タプルが異なるスレッドに送られた場合，

U1, U2, Next の 4 つの属性で構成されるデータオブジェクトであ

そのタプルの U1，U2 ポインタは入力タプルを指し示すポインタ

る．Type はメタデータが生成されたオペレータを識別する属性

として無効になるという問題がある．なぜならば U1 と U2 はタである．U1，U2，Next はポインタで，オペレータの出力タプル

プルを送信したスレッドが持つメモリ領域を参照するポインタでに貢献したオペレータの入力タプルを指す．

あるが，その領域はタプルを受け取ったスレッドから参照するこ

Operator Instrumentation: GeneaLog で拡張された処理フとができないからである．これを解決するために，GeneaLog でローの各オペレータは，単にタプルを処理するだけでなく，処理は Explicit アプローチと Implicit アプローチの 2 つを提案してい結果の Lineage が求められるようメタデータを適切にセットする

るが，本研究では Implicit アプローチを採用しており，以下の説必要がある．ここでは Aggregate オペレータを例にとって説明を明もそれに基づいている．

行う．

Send と Receive オペレータはスレッド間でタプルをやり取り
3

日本データベース学会 データドリブンスタディーズ
一般論文

Vol. 2, Article No. 1, 2024 年 3 月するためのオペレータである．Implicit アプローチでは Send オ

lineage object は 4 つの属性 (OPid, Input, Output, Reason) で構成

ペレータがタプルを送信するとき，まず送信タプルの Type をされるデータオブジェクトであり，Reasoning lineage の構成要素“REMOTE” にセットする．そして送信タプルの貢献グラフを辿である．

り送信タプルの Lineage を求めた上で，送信タプルと Lineage を

Operator Instrumentation: RL は Map 処理で AI/ML 処理がシリアライズして送信する．Receive オペレータではタプルと実行されるとき，他のメタデータと同様に下記のようにセットさLineage を受け取ると，下記で示すようにタプルのメタデータをれる．

Instrumented Map: 入力タプル 𝑡𝑖𝑛 を受け取り，𝑡𝑖𝑛 に AI/ML 処

セットし，貢献グラフを再構築する．

Receive オペレータが，タプル 𝑡 𝑜𝑢𝑡 とその入力タプル集合（Lin-理を適用したのち 𝑡 𝑜𝑢𝑡 を返す Map オペレータを考える．𝑡 𝑜𝑢𝑡 .𝑣

eage） 𝑡 𝑠1 , . . . , 𝑡 𝑠𝑛 を受け取る場合を考える．このとき，Receive

は AI/ML 処理によって導出された分析結果を表し，そのときのオペレータは下記のように 𝑡 𝑜𝑢𝑡 のメタデータをセットし，貢献グ判断根拠を 𝑅𝐸 𝐴𝑆𝑂𝑁 を表記する．このとき Map オペレータはラフを再構築する．そして 𝑡 𝑜𝑢𝑡 が次のオペレータに送られる．

下記のように出力タプルのメタデータをセットする．

1. 𝑡 𝑜𝑢𝑡 .𝑈1 = 𝑡 𝑠𝑛 ，𝑡 𝑜𝑢𝑡 .𝑈2 = 𝑡 𝑠1

1. 𝑡 𝑜𝑢𝑡 .𝑇 𝑦 𝑝𝑒 = 𝑀𝑎 𝑝

2. 𝑡 𝑠𝑖 .𝑁𝑒𝑥𝑡 = 𝑡 𝑠𝑖+1 (𝑖 = 1, . . . , 𝑛 − 1)

2. 𝑡 𝑜𝑢𝑡 .𝑈1 = 𝑡𝑖𝑛
3. 𝑡 𝑜𝑢𝑡 .𝑅𝐿 = {⟨𝑀𝑎 𝑝, 𝑡 𝑖𝑛 , 𝑡 𝑜𝑢𝑡 .𝑣, 𝑅𝐸 𝐴𝑆𝑂𝑁⟩}

4

ストリーム処理における拡張来歴

4.1

定義

実装システムは，AI/ML 処理の判断根拠を RL に登録するためのインタフェースをストリーム処理の開発者に提供している．こ

本節ではストリーム処理における拡張来歴を定義する．分析のインタフェースを利用することで，ストリーム処理フローの開結果 𝑡 の拡張来歴とは，Source lineage と Reasoning lineage の 2

発者は次の 1 行を Map オペレータの関数定義に追加するだけで，種類の Lineage のペアのことである．Source lineage とは分析結

AI/ML 処理実行時の判断根拠を登録することができる．

果 𝑡 の導出に貢献した入力タプルの集合のことであり，これは
従来の Lineage と同じものを指す．一方，Reasoning lineage とは// t_in/t_out: Map オペレータの入力/出力タプル

分析結果 𝑡 を導出したときの AI/ML 処理の判断根拠オブジェク// output/reason: AI/ML 処理の実行結果/判断根拠ト（Reasoning Lineage Object, RLO）の集合のことである．具体

Reason.registerReasonInfo("Map", t_in,
output, reason, t_out);

的には RLO は 4 つの属性で構成される：OPid，Input，Output，Reason．OPid は AI/ML 処理を実行し判断根拠を生成したオペ

拡張来歴を求めるために，Send と Receive オペレータの拡張

レータを指す識別子で，Input と Output はそれぞれオペレータも併せて行う．Send オペレータは Lineage の代わりに拡張来歴の入力タプルと出力タプルを指す．Reason は入力タプルからなを求め送信し，Receive オペレータは従来のメタデータのセット

ぜ AI/ML 処理が出力タプルを導出したのかの説明を保存するに加えて RL に Reasoning lineage object 集合を登録する処理を属性である．例えば，図 1 に示したストリーム処理の分析結果追加で行う．

⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩ の拡張来歴は図 4 になる．Reasoning lineage を用いることで，どのオペレータがどの入力データからどのような拡張貢献グラフを用いた拡張来歴導出: メタデータとして RL判断根拠で分析結果を導出したのかを提示することができるようを加えたことで従来の貢献グラフに RL が追加される．具体的には，図 1 の分析結果 ⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩ の貢献グラフは，図 5 のよになる．

うに従来の貢献グラフに RL ポインタが追加されたようなデータ

Reasoning lineage を提示するためには，AI/ML 処理の設計者

構造になる．これを拡張貢献グラフと呼ぶ．

が AI/ML 処理結果の判断根拠をシステムに登録するための機能

この拡張貢献グラフに対して，アルゴリズム 1 を適用するこを提供している必要がある．そこでプロトタイプシステムの実装とによって拡張来歴を求めることができる．このアルゴリズム

では，AI/ML 処理の設計者が AI/ML 処理結果の判断根拠を簡単

は，RL が Reasoning lineage object を参照していない場合 nullに登録するためのインタフェースを提供しており，その詳細は値を取ることを仮定している．𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐼 𝑓 𝑁𝑜𝑡𝑉𝑖𝑠𝑖𝑡𝑒𝑑 はタプル，

4.2 節で述べる．
4.2

キュー 𝑞 ，タプル集合 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 を受け取ると，タプルが 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 に

拡張来歴の導出

含まれているかを確認し，もしタプルが 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 に含まれていな

本節では GeneaLog をベースに拡張来歴を導出するシステムのければ（そのタプルにまだアクセスしたことがなければ），キュー

説明を 1) 追加メタデータ， 2) Operator instrumentation， 3) 拡張にタプルをエンキューする関数である．またタプルが既に含まれ貢献グラフを用いた拡張来歴導出の 3 つに分けて行う．説明を簡ていた場合には何も行わず，そのまま処理がアルゴリズムに戻っ単にするため，本稿では AI/ML 処理は Map オペレータのみで実てくる．このアルゴリズムは GeneaLog のものに基づいており，行すると仮定しているが，実際には説明する手法はその他のオペ

拡張来歴を求めるための拡張は 4 行目，5 行目である．ここではレータで AI/ML 処理が実行されても拡張来歴を導出可能である．

アクセスしたタプルが Reasoning lineage object を持っていれば

追加メタデータ: 拡張来歴を導出するために，新しいメタデー

それを 𝑅𝐿 に追加する処理を行なっている．この拡張によってアタ RL を従来のメタデータに追加する．RL は Reasoning lineage

ルゴリズムは拡張来歴を導出することができるようになる．

object 集合を指すポインタである．前述したように Reasoning4

日本データベース学会 データドリブンスタディーズ
一般論文

Vol. 2, Article No. 1, 2024 年 3 月
893>> h Map, h 1, C001, “Wrong one . . . ”, 10000 i, >
>
>
>
68
9 >
>
7
Negative, “1st word is ‘Wrong’.” i>
6< h 1, C001, “Wrong one . . . ”, 10000 i = >
>
>
<
=7
6
7
h
Map,
h
1,
C002,
“This
toy
.
.
.
”,
10005
i,
6 h 1, C002, “This toy . . . ”, 10005 i
7,
6:
7
Negative, “4th word is ‘broken’.” i>
6 h 1, C003, “Some parts . . . ”, 10010 i ; >
>
>
7
>
>
>
>
4
5
h
Map,
h
1,
C003,
“Some
parts
.
.
.
”,
10010
i,
>
>
>
>
:
;
Negative, “4–5th words are ‘not arrived’.” i2<latexit sha1_base64="h8dnq1k6lHr9SEesGo5nuhEKeSw=">AAAFgHicpVJNb9NAEJ02BEr4aAoXBJcVUUmR0rAuLaCeKnrhAup3K9VVunYmjlVn11pvgoqVA1f+AAdOIKEKcYHfwIU/wKE/AXEsEhcOjJ2Uqi1tgjqWd2ffznt+O2snDPzIcL47MJg5lz1/Yehi7tLlK1eH8yPXViLV1C4uuypQes0REQa+xGXjmwDXQo2i4QS46mzNJvurLdSRr+SS2Q5xoyE86dd8VxiCKiOZm4zCDrBm1tPRjnMp4qDny9gIpxkI3Y6DdgceswMhvQDtu8wqsVnOadzcXNVKekxJZHZVmahYLDGLUyT1er/etk+QmEgklup+xIzaPqww1Z/C/URhUTWQhUKb6JCG9W8XKKt/T8ds7Xt1Y7dL/9mCpyIsnaUnpX039SgULsYWNtrP0KO7aWGiYUWGPVe6yqg3HcFiuVjs1ZMTXPXb5l6mJk39wJSj1RbKM7jq/+p6+hofn+pai5jQyDalMpRo2q8edXjKT5DrJBu5Sr7AyzwNdjyxukkBujGn8jtgQxUUuNCEBiBIMJQHICCiZx0s4BAStgExYZoyP91HaEOOuE2qQqoQhG7R6NFqvYtKWieaUcp26SsBvZqYDEb5N/6B7/Gv/CP/zn+fqBWnGomXbZqdDhfDyvCrG4u/erIaNBuoH7BO9WygBo9Srz55D1MkOYXb4bdevN5bnF4Yje/wd/wH+X/Ld/kXOoFs/XTfz+PCG0guwDra7uPJykTZelCenJ8szDzuXsUQ3ILbMEb9fggz8ATmYBnczMvMTuZT5nN2MDuWvZe1OqWDA13OdTgU2ek/YHd+pg==</latexit>

図 4 分析結果 ⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩ の拡張来歴

Sourceオペレータの
出⼒タプル

null

U1

Mapオペレータの
出⼒タプル

U1
Next
RLO1

U1

Aggregateオペレータの
出⼒タプル

null

タプルは RL が RLO3 を指しているため 5 行目で 𝑅𝐿 に RLO3

nullを追加する．その後 8 行目に制御が移り， ⟨1, 𝐶003, ..., 10010⟩

U1が 𝑞 にエンキューされる．𝑖𝑛𝑡 2 と 𝑖𝑛𝑡 1 についても同様に行

Next
RLO2

うと，RLO2 と RLO1 が 𝑅𝐿 に追加される．その時点で 𝑞 には

RLO3

U2

⟨1, 𝐶003, ..., 10010⟩ ，⟨1, 𝐶002, ..., 10005⟩ ，⟨1, 𝐶001, ..., 10000⟩ のnull

3 タプルがあり，それらの Type はすべて Source である．そのためこれらは 7 行目で 𝑆𝐿 に追加され，その後 𝑞 は空であるから

図 5 拡張来歴のための拡張貢献グラフ

𝑆𝐿 と 𝑅𝐿 が返される．結果として拡張来歴が導出され，その内
容は図 4 に示したものとなる．

Algorithm 1 拡張来歴の導出
入力: 分析結果のタプル 𝑡 𝑜𝑢𝑡
1: キュー 𝑞 を {𝑡 𝑜𝑢𝑡 } で初期化し，𝑣𝑖𝑠𝑖𝑡𝑒𝑑 と 𝑆𝐿 ， 𝑅𝐿 を空集合

本節では Flink 上に実装したプロトタイプシステムを用いたクで初期化．

ラスタ環境における性能評価の結果を述べる．

2: while 𝑞 に要素があるとき do3:𝑡 = 𝑞.𝑑𝑒𝑞𝑢𝑒𝑢𝑒()4:

if 𝑡.𝑅𝐿 ≠ 𝑛𝑢𝑙𝑙 かつ 𝑡.𝑅𝐿.𝑠𝑖𝑧𝑒 > 0 then

実験5

出力: 𝑡 𝑜𝑢𝑡 の拡張来歴

5.1

データセット

実験ではストリームデータとして，Amazon レビューデー
タ [16] に基づいた 2 種類のデータを使用した．Amazon レビュー

5:

𝑅𝐿 = 𝑅𝐿 ∪ {𝑡.𝑅𝐿}

データは Amazon の商品 ID とそのレビューコメントなどが記録

6:

if 𝑡.𝑇 𝑦 𝑝𝑒 が Source then

されているデータセットである．事前の調査で Amazon レビュー

7:
8:
9:
10:

𝑆𝐿 = 𝑆𝐿 ∪ {𝑡}

データには商品の出現回数や入力タプルサイズの点で，データにelse if 𝑡.𝑇 𝑦 𝑝𝑒 が Map then

偏りがあることがわかっていた．そこでデータの偏りによる実験

𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐼 𝑓 𝑁𝑜𝑡𝑉𝑖𝑠𝑖𝑡𝑒𝑑 (𝑡.𝑈1, 𝑞, 𝑣𝑖𝑠𝑖𝑡𝑒𝑑)

結果への影響を排除するために，元の Amazon レビューデータを

else if 𝑡.𝑇 𝑦 𝑝𝑒 が Join then

修正した人工データセットと元の Amazon レビューデータをそ

11:

𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐼 𝑓 𝑁𝑜𝑡𝑉𝑖𝑠𝑖𝑡𝑒𝑑 (𝑡.𝑈1, 𝑞, 𝑣𝑖𝑠𝑖𝑡𝑒𝑑)のまま使用するリアルデータセットを用意した．人工データセッ

12:𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐼 𝑓 𝑁𝑜𝑡𝑉𝑖𝑠𝑖𝑡𝑒𝑑 (𝑡.𝑈2, 𝑞, 𝑣𝑖𝑠𝑖𝑡𝑒𝑑)

トでは商品 ID が一様分布に従い，全ての入力タプルのサイズが13:

else if 𝑡.𝑇 𝑦 𝑝𝑒 が Aggregate または REMOTE then14:

𝑡 𝑡 𝑚 𝑝 = 𝑡.𝑈2

15:

while 𝑇𝑟𝑢𝑒 do

同じになるようにした．
5.2

複合的ストリーム処理フローと AI/ML 処理の実装

実験の複合的ストリーム処理フローは，レビューコメントを受

16:

𝑒𝑛𝑞𝑢𝑒𝑢𝑒𝐼 𝑓 𝑁𝑜𝑡𝑉𝑖𝑠𝑖𝑡𝑒𝑑 (𝑡 𝑡 𝑚 𝑝 , 𝑞, 𝑣𝑖𝑠𝑖𝑡𝑒𝑑)

け取るとそのコメントが Positive か Negative かを判定する感情

17:

if 𝑡 𝑡 𝑚 𝑝 == 𝑡.𝑈1 then

判定 AI/ML 処理を活用する．実際にはリアルタイム処理フロー

𝑏𝑟𝑒𝑎𝑘

18:

とウインドウ処理フローの 2 つの処理フローを用いて実験を行っ

19:

𝑡 𝑡 𝑚 𝑝 = 𝑡 𝑡 𝑚 𝑝 .𝑁𝑒𝑥𝑡

た．どちらの処理フローも，Apache Kafka から入力タプルを受

20: return[𝑆𝐿, 𝑅𝐿]

け取り，Kafka に分析結果を送信する．
リアルタイム処理フローは以下に示すオペレータで構成され

例3

る：Source-Map-Filter-Map-Sink．入力タプルを受け取ると，そアルゴリズム 1 を用いて，図 1 の分析結果 ⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩のコメントが Positive か Negative かを判定する分析を行う．は（対応する拡張貢献グラフは 図 5）の拡張来歴を求める様子

じめの Map オペレータは，文字列型入力タプルを Java オブジェを説明する．まず 1 行目で 𝑞 を {⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩} で初期化

クトのタプルに変換する．Filter オペレータは直前の Map で変換

し，他変数は空集合で初期化する．すると 𝑞 には要素があるたされた際に欠損値を持つタプルを削除するが，実際にはここで削

め，3 行目で 𝑡 = ⟨1, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 3⟩ となる．𝑡 の RL は null であ除されるタプルはほとんどなかった．2 つ目の Map オペレータ

り 𝑡.𝑇 𝑦 𝑝𝑒 は Aggregate であるため 13 行目に移り，19 行目まは感情判定処理を実行し，タプルに Positive または Negative をでの処理の間で 𝑞 に 𝑖𝑛𝑡 3 = ⟨1, 𝐶003, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 10010⟩ ，𝑖𝑛𝑡 2 =割り当てる．

⟨1, 𝐶002, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 10005⟩ ，𝑖𝑛𝑡 1 = ⟨1, 𝐶001, 𝑁𝑒𝑔𝑎𝑡𝑖𝑣𝑒, 10000⟩ が一方，ウインドウ処理フローは以下のオペレータで構成されエンキューされる．次に 2 行目に戻ると 𝑡 = 𝑖𝑛𝑡 3 となり，この5日本データベース学会 データドリブンスタディーズ
一般論文

Vol. 2, Article No. 1, 2024 年 3 月

る：Source-Map-Filter-Map-Aggregate-Sink．リアルタイム処理

るウインドウサイズは「-」で表記する．

フローの分析の内容に加えて，商品ごとに Positive/Negative なコ

図 6 は人工データを用いた評価実験のレイテンシと Traversal

メントの数をカウントする分析を行う．そのため Aggregate オペ

時間を，図 7 はスループットを表している．図中の ** と * は，

レータでは，商品 ID ごとにウインドウ内の Positive/Negative な

SAL を Baseline または Lineage と比較したときにそれぞれ有意

コメントをカウントする処理を行う．

差 1 % もしくは 5 % で統計的な差があることを示している．図 6

感情判定 AI/ML 処理に関して，今回の実験では 2 つの実装をの Traversal 時間のバーにおける ** もしくは * の上には，SAL の用意した．まず 1 つ目は人工データを用いた実験で使用する，ダTraversal 時間が Lineage の Traversal 時間と比較して何倍になっミーの感情判定モデルを用いた実装である．ダミーの感情判定モ

たかを示している．なお Baseline 手法では Lineage を求めるた

デルは，処理時間の変動を抑えることで安定した実験結果を得る

めの Traversal 時間が発生しないため，Traversal 時間は示していことを目的にしており，入力データを受け取ると事前に定義したない．差の有無の確認には Welch の t 検定 [18] を用い，必要に固定時間処理をアイドルしたあと，Positive の分析結果と固定長応じてボンフェローニ補正を適用した結果に基づいている．

文字列を判断根拠として返す．2 つ目はリアルデータを用いた実まずリアルタイム処理フローを用いた結果について説明する．

験で使用する，IBM が提供している実際のモデル [17] を用いた

レイテンシとスループットに関しては感情判定モデルの処理コス実装である．

トが大きいとき，拡張来歴の導出によって発生するオーバヘッド

ここまでに説明したデータセットと処理フロー，感情判定モデは非常に小さいことが示された．図 6(a)，7(a) の処理コストが大ルの実装を組み合わせて以下の実験を行った：人工データを用い

きい場合を見ると，レイテンシは H/S/- ，スループットは H/L/- のた 2 つの処理フローの実験（ダミー感情判定モデル使用）と，リ

とき統計的な差があるもののその差は非常に小さい．実際 H/S/-

アルデータを用いた 2 つの処理フローの実験（IBM の感情判定の SAL のレイテンシは Baseline と比較して 1.0002 倍，Lineage

モデル使用）．

と比較して 1.0001 倍であり，H/L/- の SAL のスループットは5.3

比較手法と比較指標

Baseline の 0.98 倍，Lineage の 0.99 倍である．またモデルの処各実験では 3 つの比較手法を評価した：1) Lineage を導出しな理コストが大きいとき，レイテンシ全体に対する Traversal 時間

いケース（Baseline, Base）, 2) GeneaLog を用いて Lineage のみの割合は非常に小さいことも示された．これらの理由はダミーの導出するケース（Lineage, Lin）, 3) 拡張来歴を導出するケース

感情判定モデルの処理コストが大きい時，モデルの処理時間が全（SAL）．SAL が本稿で説明した手法である．

体の処理時間のほとんどを占め，拡張来歴を求めるための追加処比較指標としてはレイテンシとスループットに加え，拡張来歴

理にかかるオーバヘッドが相対的に小さくなったからと考えら

導出時の貢献グラフを辿るためにかかる時間（Traversal 時間）のれる．一方で処理コストが小さいときは，レイテンシやスルー

3 つを用いた．レイテンシと Traversal 時間は実験を 1 回実施しプットの性能が大きく低下した．SAL のレイテンシは Baseline

た際に出力された分析結果の平均値を使用し，スループットは 5の 8.4 倍，Lineage の 1.6 倍となり，スループットは Baseline の回実験を行った時の平均値を使用している．なお実験はクラスタ

0.14 倍，Lineage の 0.72 倍だった．この時の SAL の Traversal 時

環境で実行した．クラスタは 2 ノード Apache Flink クラスタ（1間は SAL のレイテンシのうち約 52% を占めており，このことはジョブマネージャー，1 タスクマネージャー）と 3 ノード Apache

拡張来歴を求めるための追加処理が性能に大きく影響を与えるこ

Kafka クラスタ（1 Zookeeper，2 ブローカノード）で構成され，とを示していると考えられる．加えて Traversal 時間に関しては，各ノードは 128 GB メモリと 10 CPU コアを持つ．

図 6(a) で示すように拡張来歴の追加情報を導出する SAL の方が5.4

人工データを用いた評価実験

Lineage と比べて，Traversal 時間が長くなることを示した．

人工データを用いた実験では入力データや処理フローの特性が次にウインドウ処理フローを用いた際の結果を説明する．レイ

性能に与える影響を検証するために，リアルタイム処理フローとテンシに関しては処理コストが大きい場合でも入力タプル長が長ウインドウ処理フローのそれぞれに対して，データの特性や処理い場合，レイテンシへの影響は非常に小さいが，入力タプル長がパラメータの組み合わせを複数試すことで多角的な評価を行っ

短い場合は性能差が現れる結果となった．またスループットはリた．具体的には，以下の 3 つの特性を変化させた際のレイテンシ

アルタイム処理フローの場合と同様，処理コストが大きい場合はとスループット，Traversal 時間を測定した．

拡張来歴を導出したとしても性能の低下がほとんど見られなかった（図 7(b) ）．H/L/S のケースで統計的な差は見られたが，この• ダミー感情判定モデルの処理コスト：実行時のアイドル時間
を変更．Light：アイドル無し，Heavy：200 ms．

時の SAL のスループットは Baseline の 0.996 倍でその差は非常に小さい．一方，感情判定の処理コストが小さい場合は，SAL の• 入力タプル長：レビューコメントの長さを変更．Short：1

L/S/S のレイテンシが Baseline の 2.8 倍，Lineage の 1.03 倍とbyte, Long：35,094 bytes．

なった．Traversal 時間に関しては，処理コストの大小に関わら• ウインドウサイズ：Small：1 秒，Large：100 秒．

ずレイテンシ全体に占める Traversal 時間の割合は非常に小さく，多くの場合で SAL の方が Lineage と比べて Traversal 時間が長く

3 つの特性の組み合わせを x/x/x のように表記し，それぞれがなることが示された．

処理コスト，入力タプル長，ウインドウサイズに対応している．
例えば H/L/S は，処理コスト Heavy，入力タプル長 Long，ウイ

人工データを用いた実験では，処理コストが小さい場合には拡ンドウサイズ Small を表す．またリアルタイム処理フローにおけ

張来歴を求める際のオーバヘッドが大きくなる結果になった．し6

日本データベース学会 データドリブンスタディーズ
一般論文

Vol. 2, Article No. 1, 2024 年 3 月**
処理時間 [s]

**

**

1E-1

**
+54%

1E-3

**

1E-5

+106%

*

**

+90%

1E-7
Base

Lin

SAL

Base

Lin

L/S/レイテンシ**
処理時間 [s]

**

**

1E+2

SAL

Base

Lin

H/S/-

SAL

H/L/-

Traversal時間<latexit sha1_base64="F7IJMlZsGyqyBuQIFEqkCZ4Jw2Y=">AAACZnichVFNSwJBGH7cvsw+tCIKukhi2EXGkIpOUpeOfuQHmMjuNtriurvsroJJfyDomodOBRHRz+jSH+jgPyg6GnTp0Ou6ECXVO8zMM8+8zzvPzEiGqlg2Y12PMDI6Nj7hnfRNTc/M+gNz8zlLb5gyz8q6qpsFSbS4qmg8ayu2yguGycW6pPK8VNvr7+eb3LQUXTuwWwYv1cWqplQUWbSJykTE9XIgxKLMieAwiLkgBDeSeuAWhziCDhkN1MGhwSasQoRFrYgYGAziSmgTZxJSnH2OU/hI26AsThkisTUaq7QquqxG635Ny1HLdIpK3SRlEGH2xO5Yjz2ye/bCPn6t1XZq9L20aJYGWm6U/WfLmfd/VXWabRx/qf70bKOCbcerQt4Nh+nfQh7omyedXmYnHW6vsWv2Sv6vWJc90A205pt8k+LpS/joA2I/n3sY5Daisc1oPBUPJXbdr/BiBauI0HtvIYF9JJGlc6s4xwU6nmdhVlgUlgapgsfVLOBbCMFPuLyKTw==</latexit>

(a)

**

**

**

1E+0
1E-2

+32%

-29%

**

+35%

**

*

+72%

1E-4

**

1E-6
Base

Lin

SAL

Base

Lin

L/S/S

SAL

Base

Lin

H/S/S
レイテンシ

SAL

Base

Lin

H/L/S

SAL

H/S/L

Traversal時間<latexit sha1_base64="I5epLVbt3LLr0r5HxpCJj+9o5Us=">AAACZnichVFNSwJBGH7cvsw+tCIKukhi2EXGkIpOUpeOfuQHmMjuNtriurvsroJJfyDomodOBRHRz+jSH+jgPyg6GnTp0Ou6ECXVO8zMM8+8zzvPzEiGqlg2Y12PMDI6Nj7hnfRNTc/M+gNz8zlLb5gyz8q6qpsFSbS4qmg8ayu2yguGycW6pPK8VNvr7+eb3LQUXTuwWwYv1cWqplQUWbSJykSk9XIgxKLMieAwiLkgBDeSeuAWhziCDhkN1MGhwSasQoRFrYgYGAziSmgTZxJSnH2OU/hI26AsThkisTUaq7QquqxG635Ny1HLdIpK3SRlEGH2xO5Yjz2ye/bCPn6t1XZq9L20aJYGWm6U/WfLmfd/VXWabRx/qf70bKOCbcerQt4Nh+nfQh7omyedXmYnHW6vsWv2Sv6vWJc90A205pt8k+LpS/joA2I/n3sY5Daisc1oPBUPJXbdr/BiBauI0HtvIYF9JJGlc6s4xwU6nmdhVlgUlgapgsfVLOBbCMFPur2KUA==</latexit>

(b)

**
**

1000000****

スループット [/s]スループット [/s]図 6 (a) リアルタイム処理 (b) ウインドウ処理 におけるレイテンシ／ Traversal 時間

10000
100
1

L/S/Baseline<latexit sha1_base64="F7IJMlZsGyqyBuQIFEqkCZ4Jw2Y=">AAACZnichVFNSwJBGH7cvsw+tCIKukhi2EXGkIpOUpeOfuQHmMjuNtriurvsroJJfyDomodOBRHRz+jSH+jgPyg6GnTp0Ou6ECXVO8zMM8+8zzvPzEiGqlg2Y12PMDI6Nj7hnfRNTc/M+gNz8zlLb5gyz8q6qpsFSbS4qmg8ayu2yguGycW6pPK8VNvr7+eb3LQUXTuwWwYv1cWqplQUWbSJykTE9XIgxKLMieAwiLkgBDeSeuAWhziCDhkN1MGhwSasQoRFrYgYGAziSmgTZxJSnH2OU/hI26AsThkisTUaq7QquqxG635Ny1HLdIpK3SRlEGH2xO5Yjz2ye/bCPn6t1XZq9L20aJYGWm6U/WfLmfd/VXWabRx/qf70bKOCbcerQt4Nh+nfQh7omyedXmYnHW6vsWv2Sv6vWJc90A205pt8k+LpS/joA2I/n3sY5Daisc1oPBUPJXbdr/BiBauI0HtvIYF9JJGlc6s4xwU6nmdhVlgUlgapgsfVLOBbCMFPuLyKTw==</latexit>

H/S/Lineage

H/L/SAL

1000000

**
**

**

10000
100
1

L/S/S
Baseline

(a)

H/S/S

H/L/S

Lineage<latexit sha1_base64="I5epLVbt3LLr0r5HxpCJj+9o5Us=">AAACZnichVFNSwJBGH7cvsw+tCIKukhi2EXGkIpOUpeOfuQHmMjuNtriurvsroJJfyDomodOBRHRz+jSH+jgPyg6GnTp0Ou6ECXVO8zMM8+8zzvPzEiGqlg2Y12PMDI6Nj7hnfRNTc/M+gNz8zlLb5gyz8q6qpsFSbS4qmg8ayu2yguGycW6pPK8VNvr7+eb3LQUXTuwWwYv1cWqplQUWbSJykSk9XIgxKLMieAwiLkgBDeSeuAWhziCDhkN1MGhwSasQoRFrYgYGAziSmgTZxJSnH2OU/hI26AsThkisTUaq7QquqxG635Ny1HLdIpK3SRlEGH2xO5Yjz2ye/bCPn6t1XZq9L20aJYGWm6U/WfLmfd/VXWabRx/qf70bKOCbcerQt4Nh+nfQh7omyedXmYnHW6vsWv2Sv6vWJc90A205pt8k+LpS/joA2I/n3sY5Daisc1oPBUPJXbdr/BiBauI0HtvIYF9JJGlc6s4xwU6nmdhVlgUlgapgsfVLOBbCMFPur2KUA==</latexit>

H/S/L

SAL

(b)

図 7 (a) リアルタイム処理 (b) ウインドウ処理 におけるスループット

かし本研究で想定しているような AI/ML 処理の処理コストは一処理時間 [s]般に大きいため，実際に本研究が使用される状況においては拡
張来歴を求める際のコストはそれほど問題にならないと考えられる．
5.5

リアルデータを用いた評価実験

**

1E+1

**

**

1E-1
+30%

1E-3

+31%

**

**

1E-5
Base

リアルデータを用いた評価実験では，IBM が提供するネット

Lin

SAL

Base

Realtime

ワークベースの感情判定モデルと，元の Amazon レビューデー

レイテンシ

Lin

SAL

Window
Traversal時間

タを使用した．感情判定モデルの処理コストは前節の処理コスト
スループット [/s]Heavy に相当し，元の Amazon レビューデータのタプルサイズには Short〜Long の範囲で様々なサイズのタプルが存在している．
またウインドウサイズは 1 秒ウインドウを使用した．そのため本
実験は，リアルタイム処理フローでは前節の H/S/- と H/L/-，ウ
インドウ処理フローでは H/S/S と H/L/S に対応している．
図 8 が実験の結果である．本実験は前節の処理コスト Heavy

30
20
10
0
Realtime
Baselineの場合に対応しているため，リアルタイム処理フローではレイテ
ンシ，スループットの両方で非常に小さいコストで拡張来歴が導図8

Window
Lineage

SAL

リアルデータを用いた性能評価

出でき，レイテンシに占める Traversal 時間は非常に小さいという結果になった．レイテンシで統計的な差は見られたものの，その時の SAL のレイテンシは Baseline の 0.996 倍 で，ほとんど影

レイテンシは SAL は Baseline の 3.6 倍，Lineage の 1.9 倍 にな

響ないことが示された．

るという結果となった．これは元の Amazon レビューデータでまたウインドウ処理フローにおけるスループットや Traversal

はサイズ小のタプルの割合が大きいため，前節の処理コスト大，時間の傾向はリアルタイムの場合と同様となった．一方 SAL のタプルサイズ小の時と同様の傾向が現れたと考えられる．

7

日本データベース学会 データドリブンスタディーズ
一般論文

6Vol. 2, Article No. 1, 2024 年 3 月

nance semirings. In Proceedings of the Twenty-Sixth ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems,
pages 31–40, 2007.
[12] J. Nathan Foster, Todd J. Green, and Val Tannen. Annotated xml:
Queries and provenance. In Proceedings of the Twenty-Seventh ACM
SIGMOD-SIGACT-SIGART Symposium on Principles of Database
Systems, pages 271–280, 2008.
[13] Matteo Interlandi, Kshitĳ Shah, Sai Deep Tetali, Muhammad Ali
Gulzar, Seunghyun Yoo, Miryung Kim, Todd Millstein, and Tyson
Condie. Titian: data provenance support in spark. In Proceedings of
the VLDB Endowment International Conference on Very Large Data
Bases, volume 9, pages 216–227, 2015.
[14] Nithya N. Vĳayakumar and Beth Plale. Towards low overhead provenance tracking in near real-time stream ﬁltering. In Provenance andAnnotation of Data, pages 46–54, 2006.
[15] Min Wang, Marion Blount, John Davis, Archan Misra, and Daby
Sow. A time-and-value centric provenance model and architecture
for medical event streams. In Proceedings of the 1st ACM SIGMOBILE International Workshop on Systems and Networking Support for
Healthcare and Assisted Living Environments, pages 95–100, 2007.
[16] Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly-labeled reviews and ﬁne-grained aspects. In
Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference
on Natural Language Processing (EMNLP-ĲCNLP), pages 188–197,
2019.
[17] IBM. MAX-Text-Sentiment-Classiﬁer. https://github.com/IBM/MAX-Text-Sentiment-Classifier.
[18] Bernard L Welch. The generalization of student’s problem whenseveral diﬀerent population varlances are involved. Biometrika, 34:28–
35, 1947.

結論
本稿では AI/ML 処理を伴う複合的ストリーム処理において，従来の Lineage に加えて AI/ML 処理の判断根拠を提示する，拡
張来歴導出手法の説明を行った．さらにシステムを最新手法である GeneaLog に基づいて Apache Flink 上に実装し，偏りのない
人工データとリアルデータを用いた評価実験の結果を示した．実験結果から，説明した手法は AI/ML 処理のコストが大きい場合には小さなコストで拡張来歴が導出可能である傾向を示した．今回説明した枠組みによって，AI/ML 処理を伴う複合的ストリー
ム処理の分析結果として得られるデータの信頼性を一層高められることが期待される．
今後の課題としては，より多様なデータセットや処理フローにおける評価実験の実施や，現実のストリーム処理アプリケーショ
ンへの適用，Apache Flink 以外のストリーム処理エンジンでの実装が挙げられる．さらに，導出された拡張来歴の情報をデータベース等を用いて永続化かつクエリ可能にするシステムの提案も重要なトピックである．

謝辞
本 研 究 の 一 部 は ，JSPS 科 研 費 (JP23H03399，JP22K19802,

JP20K19806，JP22H03694)，JST CREST (JP-MJCR22M2)，NEDO(JPNP20017)，AMED (JP21zf0127005)，SKY 株式会社共同研究，
JST 次世代研究者挑戦的研究プログラム (JPMJSP2124) による.

参考文献
[1] Melanie Herschel, Ralf Diestelkämper, and Houssem Ben Lahmar. A
survey on provenance: What for? what form? what from? The VLDB
Journal, 26(6):881–906, 2017.
[2] Susan B. Davidson and Juliana Freire. Provenance and scientiﬁcworkﬂows: Challenges and opportunities. In Proceedings of the 2008
ACM SIGMOD International Conference on Management of Data,
pages 1345–1350, 2008.
[3] Sherif Akoush, Ripduman Sohan, and Andy Hopper. Hadoopprov:
Towards provenance as a ﬁrst class citizen in mapreduce. In 5th
USENIX Workshop on the Theory and Practice of Provenance, 2013.
[4] Yingwei Cui and Jennifer Widom. Practical lineage tracing in data
warehouses. In Proceedings of 16th International Conference on Data
Engineering, pages 367–378, 2000.
[5] Yingwei Cui, Jennifer Widom, and Janet L. Wiener. Tracing thelineage of view data in a warehousing environment. ACM Trans.
Database Syst., 25(2):179–227, 2000.
[6] Boris Glavic, Kyumars Sheykh Esmaili, Peter Michael Fischer, andNesime Tatbul. Ariadne: Managing ﬁne-grained provenance on data
streams. In Proceedings of the 7th ACM International Conference onDistributed Event-Based Systems, pages 39–50, 2013.
[7] Dimitris Palyvos-Giannas, Vincenzo Gulisano, and Marina Papatriantaﬁlou. Genealog: Fine-grained data streaming provenance incyber-physical systems. Parallel Computing, 89, 2019.
[8] Masaya Yamada, Hiroyuki Kitagawa, Toshiyuki Amagasa, andAkiyoshi Matono. Augmented lineage: Traceability of data analysis
including complex udfs. In Database and Expert Systems Applications, pages 65–77, 2021.
[9] Masaya Yamada, Hiroyuki Kitagawa, Toshiyuki Amagasa, andAkiyoshi Matono. Augmented lineage: traceability of data analysis including complex udf processing. The VLDB Journal, 32(5):963–983,
2023.
[10] Masaya Yamada, Hiroyuki Kitagawa, Salman Ahmed Shaikh,Toshiyuki Amagasa, and Akiyoshi Matono. Streaming augmented
lineage: Traceability of complex stream data analysis. In Information
Integration and Web Intelligence, pages 224–236, 2022.
[11] Todd J. Green, Grigoris Karvounarakis, and Val Tannen. Prove-8