DEIM Forum 2017 E3-3

クラウドソーシング環境における実行プラン処理方式の提案
水澤健†

田島 敬史††

森嶋厚行†††† 筑波大学情報学群情報メディア創成学類 〒 305-8550 茨城県つくば市春日 1-2†† 京都大学大学院情報学研究科 〒 606-8051 京都市左京区吉田本町 36-1††† 筑波大学 知的コミュニティ基盤研究センター 〒 305-8550 茨城県つくば市春日 1-2
E-mail: †ken.mizusawa.2016b@mlab.info, ††tajima@i.kyoto-u.ac.jp, †††mori@slis.tsukuba.ac.jp
あらまし

本稿では，クラウドソーシング環境におけるデータ処理を記述した実行プランを，効率よく処理する方法について提案する．単純に実行プランをボトムアップに処理すると，場合によっては無駄なタスク処理を大量にクラウドソースすることが必要になる．一方，完全にトップダウンに処理すると，最小限のタスクのクラウドソースで済む可能性があるが，クラウドソーシングの特徴である大量の人を投入した並列処理が困難になる．また，商用のクラウドソーシングサービスを利用した処理を行いたい場合には，各サービス毎に，最小限のタスク数等，利用の際に満たすべき制約がある．本稿では，これらの問題を考慮した実行プラン処理方式を提案する．
キーワード クラウドソーシング, 問合せ処理"

1. は じ め に
近年，ネットワーク技術の発達と普及に伴い，ネットワーク%

上の人々に問題解決のための一部の作業を割り振って，人々の知を利用することが可能となった．このような背景のもと，ク#ラウドソーシングが注目を集めている [1]．クラウドソーシングとは，ネットワーク上にいる不特定多数の人 (以下，ワーカ) に作業を委託することをいう．このクラウドソーシングにおいて，!

ワーカに委託する作業の単位を一般に「タスク」と呼ぶ．また，$作業をクラウドソーシングを利用して依頼する場合、一般的に
図 1 簡単な実行プランの例

はクラウドソーシングプラットフォームを通して行う。依頼者
は，プラットフォームに用意されたタスクテンプレートに作業内容を入力，あるいは，対応するプログラムを記述することで，えば，まず結合判定タスクを一つ発行し，もし結合条件を満た

タスクをプラットフォーム上に掲載し，ワーカに依頼する．

せば，その結果に対して選択判定タスクを一つ発行する，と言

本稿では，宣言型クラウドソーシングにおける実行プラン

うことを順次繰り返す．しかし，この方法では，タスク処理のの処理時のタスク発行制御の問題を取り扱う．宣言型クラウド

並列性が落ちるため，クラウドソーシングの強みである人海戦

ソーシングとは，DBMS による宣言型問合せ処理と同様に，ク術を利用できない．一方，実行プランの下位ノードから全てボ

ラウドソーシングの宣言的な記述を元にタスク発行などの制御

トムアップに実行 (図 1 では，R 1 S のタスクを全て実行) しを行うものである [2] [3]．通常の DBMS の問合せ処理と同様，ていくと，タスクの並列性は最大限活用できる．これは，一般

実行プランを用意する．図 1 は，簡単な実行プランの例である．

的なクラウドソーシングサービスを利用するときによく行われ

R と S にそれぞれ含まれる 100 タプルのデータからクラウドている手順ではあるが，余計なタスク発行を行う可能性が高く

ソーシングを通して，目標となる Z のタプルを 10 タプル集め

なる．

る．図 1 において，実行プランのオペレータが四角で囲まれてまた，一般的に用いられている商用のクラウドソーシングプ

いる作業を，マイクロタスクとして発行し，クラウドソーシン

ラットフォームを利用したい場合には，プラットフォームごとグ処理を行う事とする．例えば，図 1 の選択演算のタスクでは，に満たすべき制約がある．例えば タスクを依頼する場合には，提示されたデータが，選択条件を満たしているか否かを判定す

最低 50 タスクは一度に発行し，まとめて掲載する必要があるるタスクを発行する．R と S の結合演算タスクでは，提示されプラットフォーム上のタスクの掲載期間は 2 週間以内など

た R と S のタプルのペアが，結合条件を満たしているか否かの制約が挙げられる．したがって，必ずしも任意の並列処理がを判定するタスクを発行する．

可能なわけではない．さらに，クラウドソーシングで得られる

このとき，どのようにタスクを発行するかは，様々な手法が存在する．発行するタスク数を最小化するには，1 つずつタスクを発行し，必要な結果を得られた時点で終了すればよい．例

結果は必ずしも予想ができないため，どれだけのタスクを発行
すると，十分な結果が得られるかが不明である．
本稿では，以上の問題を考慮したクラウドソーシング実行プ

ラン処理方式を提案する．具体的には，与えられた実行プラン

Eddies [11] は，データベースにおけるクエリ問合せ処理の最の元で，並列で処理するタスクの数を制御し，余計なタスク

適化を，処理を行いながら実行プランを変化させることで同時を行わないようにしながら，できるだけ並列性を高める．具に実行している．本研究では実行プランは変更せず，タスクの体的には，演算子のイテレータの実装において，非同期プル

発行数を制御することで処理の最適化を図ることを目標として(Asynchronous Pull) [4] の発行個数を制御する事によって，こいる．

の目的を実現しようとするものである．
提案手法では，最初に作業目標が与えられた宣言から，目標

3. イテレータモデル

達成のために必要な最低タスク発行数を逆算する．次に，発行

本節では，DBMS の問合せ処理で広く知られているイテレー

したタスクから得られた結果を元に，データの選択率等のパラ

タモデル [12] を説明する．イテレータモデルでは，各オペレー

メータを見積もる．続いて，これらのパラメータから目標達成

タに，Open(), GetNext(), Close() という 3 つの実行プラン中に必要な最低タスク数を再計算し，次のタスク発行数を動的のメソッドを用意する．ルートノードから処理を開始し，親のオに変化させる．この必要な最低タスク発行数，および，各パラ

ペレータが子のオペレータの Open() をコールし，GetNext()

メータを計算し，次のタスクの発行数を変化させるということを結果が得られるまでコールし，最後に Close() をコールする，を繰り返すことで，目標達成のために必要十分な数のタスクのという処理を再帰的に行う．

発行でクラウドソーシングを実行することを目指す．
本研究の貢献は次のとおりである．(1) クラウドソーシングの実行プランにおけるタスク発行数の制御を，クラウドソーシ
ングの特徴である並列性に着目しながら制御する手法を提案す3. 1 3 つのメソッド
イテレータモデルにおける．各オペレータに用意する３つのメソッドについて説明する．

•

Open(): 最初にコールするメソッド．初期設定をする．

る．(2) シミュレーションにより，提案手法が，無駄になるタ

例えば，オペレータが選択演算の場合には，結果を格納する出スク発行の増加を抑えつつ，並列性を増大させる事ができる可力バッファをオープンし，子オペレータの Open() メソッドを能性があることを示す．

コールする，といった操作が考えられる．

本稿の構成は以下のとおりである．第 2. 節では関連研究に•

GetNext(): 次のタプルを読み出すメソッドである．例

ついて述べる．第 3. 節では，DBMS の問合せ処理で用いるイ

えば，オペレータがリレーション選択演算の場合には，自分よテレータモデルについて述べる．第 4. 節では，クラウドソー

り下の GetNext() を，選択条件を満たすタプルが現れるまで繰

シング実行プランの表現のために，イテレータモデルを拡張しり返しコールし，結果を出力バッファに格納するといった事がたモデルについて述べる．第 5. 節では，プラットフォーム制約

考えられる．

について述べる．第 6. 節では，クラウドソーシング実行を効•

Close(): 全てのタプルを読み終えたら呼び出すメソッド．

率的に行うための提案手法について述べる．第 7. 節ではシミュ終了処理をする．例えば，オペレータが選択演算の場合には，レーションを行い，提案手法について評価をする．第 8. 節では出力バッファをクローズし，自分の子の Close() を呼び出すとまとめと今後の課題について述べる．

いった操作が考えられる．

2. 関 連 研 究

イテレータモデルの利点は，様々な実行方式を一つの枠組
みで表現可能である事である．例えば，オペレータが結合演算

人と計算機を組合わせた処理を効率よく実行するための様々なの場合には，Open() メソッドで，2 つの子オペレータ (結合対問題は以前から知られており [5]，これまでいくつかの研究が行象) をオープンし，GetNext() を可能なだけ呼び出して結合演

われてきた．CrowdDB [6]，CrowdOp [7] では宣言的なクラウ算を行い，全ての結果をバッファに全て格納し，クローズする

ドソーシングについて研究がなされている．どちらも Amazonという方法が考えられる．このとき，GetNext() メソッドは，Mechanical Turk [8](以下，MTurk) で，プログラム記述を通単にバッファにある結果を順に上位に渡すだけの操作になる．

してタスクの発行を行っている．Qurk [9] はタスク表現とタス

これは，完全なボトムアップ処理を実現する事になる．逆に，ク処理を扱えるクエリ文を用いて，Mturk 上での処理方式を構

GetNext() を最低数だけ呼び出して結果の処理を行うというこ

築し問合せ処理を行うことで，タスクを発行する．

と再帰的に繰り返す実行方式も表現することが可能である．

Deco [3] は同じく宣言的なクラウドソーシングであり，独自のルールの記述によりクラウドソーシング実行が可能である．

Deco では，非同期プル [4] を利用したタスクの発行制御を行っ

4. クラウドソーシング実行プランとイテレータ
モデルている．ただし，Deco で採用されている制御は単純なものであ

本節では，通常のリレーショナル演算子におけるイテレータ

り，最初に必要最低数のタスクを発行した後，得られた結果がモデルを拡張する．拡張する点は，タスクの表現を許すこと，十分でない間，一つずつタスクを発行する [10]．また，MTurk

演算子の追加，および，イテレータモデルのメソッドの追加でを通じて独自のプラットフォームを対応させる事を前提としてある．

いる．本研究では，結果が十分でない場合，タスクの発行数を変化させることでクラウドソーシングの特徴である複数のワーカによる作業の並列性を確保する．

4. 1 タスクの表現
実行プランにおいてタスクを表現するための記法を導入する．具体的には，オペレータを四角で囲うことにより，そのオペレータの処理をクラウドソーシングのタスクとして発行する

%

"

$

事とする．オペレータが選択演算の場合には，子オペレータから得られた各タプル毎にタスクを発行し，そのタプルが，選択条件を満たすかどうかを判定することを依頼する．図 2(i) は，!

R からタプルを得て，選択条件を満たすかどうか判定するタス

!

!

#

クを表している．結合演算の場合には，二つの子オペレータから得られたタプルの組合せ毎に，結合条件を満たす解かを判定
図 2 タスク表現の例

する事を依頼するタスクを発行する．図 2(ii) は，R，S からタプルを得て，結合条件を満たす解かを判定するタスクを表して

,$

いる．

(

''-.#'$

4. 2 演算子の追加" #$クラウドソーシングのタスクとしてデータ入力が一般的であ!

/$ることを考え，データ入力演算子 δattrs (T ) を導入する．これは，T の各タプルの attrs 属性の内容を入力させるタスクであ

%$& '

%$+ '
(

(

る．T は省略可能であり，その場合は，任意個のタプルを入力'')*'+$'')*'&$

できる事になる．これは，タスク指定 (四角で囲む) することを

図 3 処理の流れの例

前提とした演算子である．図 2(iii) は，R の attrs 属性を入力するデータ入力演算子 δattrs (R) を表している．

4. 3 非同期プルの追加出力したタプルの集合を Outi = {outi1 , outi2 , . . . , outik } とする．(二項演算子の場合には，右上に L,R を付けて区別する).

GetNext() を行う際に，返り値を待たずに複数を発行できる

また，各 ti 毎における r 回目の依頼時の，タスクの結果としように拡張する．これは非同期プルと呼ばれ，論文 [4] でそのて欲しいタプルの数を Di , それを得るために同時に投げるタス考えが提案されたものである．非同期プルでは，GetNext() は

ク数を Mi ，そのタスク数を結果として欲しい個数発行するた

すぐに結果を返さずに，非同期で上位のオペレータに結果を返めに，子ノードに対して呼び出す GetNext() の数を Gi とする

すことになる．本研究ではこの非同期プルの発行数を制御する(これも同様に二項演算子の場合には，右上に L,R を付けて区ことで，効率的なクラウドソーシングを行うことを目標として

別する)．

いる

5. プラットフォーム制約

次に発行数の初期化・更新を行うための変数について説明し，提案手法の流れを確認する．

6. 1 変クラウドソーシングプラットフォームには，利用する際に満数

タスクの発行数の初期化や更新には次の変数を用いる．

たさなければならない制約が存在する場合がある．例えば，タスクの発行数に関しての制約が決められている場合がある．本【目標タプル】クラウドソーシングによる処理で最終的に求稿では，同時にワーカが作業が行えるように，発行されたタス

める目標タプルを z とする，実行プランのルートノードに相当

クをまとめてプラットフォームに掲載する行為を Run と呼ぶ．

する．

この 1 度の Run で掲載できるタスクの数には上限と下限が存在し得る．したがって，タスク発行数について制約が存在する
場合には，この指定された範囲に収まるように発行数を決定しなければならない．
掲載期間にも制約が存在する場合がある．発行したタスクを
長期間プラットフォーム上に掲載したままにはできず，掲載し【増加タプル】Outi において，前回の Run の時点での結果

Out′i から増加したタプル集合を ∆Outi (= Outi − Out′i ) とする．
【総タスク発行数】Di を得るためにこれまでタスク ti で発行したタスク数の総数を Mtotal i とおく．

てから 2 週間が経過すると，掲載が終了される．この場合には，同じタスクを再び掲載するといった処理が必要になると考えら【選択率 : si 】選択条件，及び，結合条件におけるこれまでれる．

の選択率である si は, これまで発行したタスクが，どれだけ欲しいタプルを得られたかどうかを示す値である．したがって，

6. 提 案 手 法
提案手法を説明するために，図 3 の記号と説明を用いる．まず，実行プランが与えられた時，そこに含まれるタスクノードの集合を T = {t1 , t2 , . . . , tn } とする．実行プラン処理の過程のある時点において，これまでに行った Run の回数を r とし，

r 回目依頼したタスクを処理した結果，これまで ti が入力として得たタプルの集合を Ini = {ini1 , ini2 , . . . , inij }，これまで

タスク ti の選択率 si について，

si =|Outi |
Mtotal i(0 <= 1)= si <
が成り立つ．この，選択率を求める処理を

si ← Set s(Outi , Mtotal i )と表現することにする．

* % &'* % &'【寄与率 : ci 】結合演算における結果への寄与率である c は，$, % &'$# % &'

親ノードである結合演算タスクの結果を生み出したタプルに，"#各子ノードがどれだけ寄与したタプルをもっていたかどうかを!

",)# % &'

示す値である．したがって，タスク ti の寄与率 ci ついて(L or R)

(L or R)=

|π(Outi ) ∩ |Ini|

(L or R)|(Ini)|
(L or R)

(0 <
= ci

), % &'-.-/, % 0-.-1, % 2(# % &'ci+

図 4 タスク発行数の初期化例<= 1)

表 1 寄与率の具体例

が成り立つ．例えば，図 4 において，表 1 に表されるようにR
tL
ij \ tij

1

2

3

R
L
R
L
R
ti (InL
i1 , Ini1 )，ti (Ini2 , Ini2 )，ti (Ini3 , Ini1 ) が Outi に含まれ

1

◯

-

-

たとすれば InL
i ,

2

-

◯

-

3

◯

-

-

4

-

-

-

InR
i の寄与率はそれぞれ (2/4 = 0.5,

2/3 =0.67) となる．
この，寄与率を求める処理を

ci ← Set c(Outi , Ini )と表現することにする．
このとき，本提案手法では，次の手順で処理を行う．

1 として値を決定する．また，結果への L の寄与率 cL と R の寄与率 cR が等しく 1 と仮定する．すなわち，上位のノードで必要なタプル数を N とすると，下記の様になる．

（ 1 ） 初期化： 全ての ti について，Di , Mi , Gi を計算し，•Di = Mi = N

Ini および Outi を空集合にする．

•

R
>
(GL
i , Ci ) = (x, y) ここで x, y は xy = N となり，x + y（ 2 ） ルートノードから GetNext() メソッドを Gi 個呼び出が最小となる組合せである．

し，タスクノードに関しては下記の処理を行う．

例えば，図 4(b) の選択ノード t2 の場合，N = 10 ならば D2 =（ a ） 子ノードからの GetNext() の結果が来るたびに，Iniに追加する．
（ b ） 子ノードからの結果がそろったら，タスクを Mi 個発
行する．
（ c ） タスクの結果が来る毎に，結果を Outi に追加する．

R
L
R
M2 = 10 となり (GLi , Gi ) = (4, 3) である．((Gi , Gi ) = (3, 4)

でも構わない)．

6. 3 タスク発行数の更新
生成したタスクの処理が終了した後，次のタスクの発行数の更新を行う．

（ d ） 発行したタスクの結果が全てそろったら，Ini , Outi

6. 3. 1 選 択 演 算の情報を元に，Di , Mi , Gi を更新する．

3 つのケースに分けることが出来る．

以上の手続きで，問題となるのは，Di , Mi , Gi の初期化とタスクの選択率 si ，寄与率 ci を用いた更新である．本提案手法では，次のようにタスク発行数を決定する．

•

最初に最も楽観的な仮定による最低限のタスク発行数を【ケース 1】|Outi | = Di
タスクを発行した結果，欲しいタプルが全て集まった場合である．このとき各種値について 0 にするということを行う．
したがって更新は初期化する．

•

Di , Mi , Gi ← 0

更新の際には，結果が全く得られなかった場合，タスク

発行数を 2 倍にする．得られた場合には，これまでの結果をもと行う．

とに選択率，寄与率を見積もり，欲しいタプル数 Di ，タスク

【ケース 2】 |Outi | <= Di であり，かつ，|Outi |/Mtotal i = 0

発行数 Mi , GetNext() の発行数 Gi を決定する．

タスクを発行したものの，欲しいタプルが 1 つも集まってい6. 2 タスク発行数の初期化ない場合である．このとき，更新は Di を変えず，Mi , Gi を倍

タスク発行数の初期化は，最も楽観的な仮定で行う．この楽増させるということを行う．

観的な仮定とは，発行したタスクを処理した結果，全てが欲ししたがって更新は，

い結果に値するタプルを取得できるという仮定である．

Mi ← 2Mi

6. 2. 1 選 択 演 算Gi ← 2Gi

選択演算では，選択条件の選択率 s を 1 としてタスクの発行数を決定する．上位のノードで必要なタプル数を N とすると，と行う．

Di = Mi = Gi = N とする．例えば，図 4(a) の選択ノード t1【ケース 3】 |Outi | <| 0= Di であり，かつ |Outi |/Mtotal i =の場合，N = 10 ならば D1 = M1 = G1 = 10 である．

タスクを発行した結果，いくつか欲しいタプルが集まったが，

6. 2. 2 結 合 演 算

まだ完全には欲しい数が集まっていないという場合である．こL と R の結合演算では，直積に関する結合条件の選択率 s をのとき更新は，集めたタプルの数だけ Di を削減，選択率 si を計算し，それを元に次に投げるタスク数となる Mi を計算する．

Algorithm 1 提案手法の流れしたがって更新は．

Input: タスクノード集合 : T, 目標タプル数 : dDi ← Di − |∆Outi |Output: 最終目標タプル取得結果 : Outd
1: for i = 1, . . . , T.length dosi = Set s(Outi , Mi )2:

Initialize(Di , Mi , Gi )2
Mi ← D i ×
1 + si

3:

Outi ← ϕ, Ini ← ϕGi ← Mi5: while d > Out.root node doと行う．

4: end for6:root node.Open()7:

for i = 1, . . . , T.length do

6. 3. 2 結 合 演 算

8:child node.GetN ext() ← ti .GetN ext()

選択演算の時と同様に，3 つのケースに分けることが出来る．

9:

if Ri == Ini then【ケース 1】 |Outi | = Di
タスクを発行した結果，欲しいタプルが全て集まった場合である．これは選択演算の時と同様にDi , Mi , Gi ← 0

10:
11:

【ケース 2】 |Outi | <= Di ，かつ，|Outi |/Mtotal i = 0
タスクを発行したものの，欲しいタプルが 1 つも集まっていOuti ← Ri .result12:

end if13:

end for14:

root N ode.Close()15:

for i = 1. . . . , T.length do

16:と更新を行う．

Run(Ri )17:

U pdatate(Di , Mi , Gi )end for

18: end while
19: return Outd

ない場合である．これも選択演算の時と同様にMi ← 2MiGi ← 2Giと更新を行う．
【ケース 3】 |Outi | <| 0= Di であり，かつ |Outi |/Mtotal i =タスクを発行した結果，いくつか欲しいタプルが集まったが，この範囲内に当てはまるように変更する．したがって，p maxMi ← Mi




p min

(p max < Mi )(p min <= Mi <= p max)(Mi < p min)

まだ完全には欲しい数が集まっていないという場合である．こと更新を行う．プラットフォーム制約がある場合には各ケース

Rの場合，選択演算と異なり，結合演算では，InL
i , Ini のどちらにおいて M の値について算出したあと，制約に当てはまる処がほしいタプルを集めることに貢献しているかを示す寄与率 ci

理をおこなった後に，G の発行数について算出する．

の計算をする必要がある点である．したがって更新は,Di ← Di − |∆Outi |【掲載期間制約 : duration 】
依頼したタスクがワーカによって処理されず，プラットフォー
ム上に残り続ける場合が存在する．このとき，プラットフォー

si = Set s(Outi , Mi )ム上にタスクを残しておける期間に制限がされる場合，再び同ci = Set c(Outi , Ini )じタスクを発行することで対応する．

2
2×
1 + si1 + c(tLi )22RMi ← Di ××
1 + si1 + c(tRi )MiL ← Di ×

6. 5 提案手法の流れ
各タスクノードで用意されたイテレータモデルのメソッドを

Algorithm1 に示す．
1 行目から 4 行目までは Open() の処理である．Open() でCiL ← MiL

は，タスク発行に使うためのタプルや，結果として得られたタ

CiR ← MiR

プルを格納するための Ini , Outi を，タプルを保存するためにと行う．

6. 4 プラットフォーム制約の確認
実行プラン処理の中でプラットフォーム制約が存在する場合には，それを考慮した変更を行う．
【発行数制約 : p max, p min】
タスクの発行数 M を決める際に，プラットフォーム制約により値が制限される場合，制約に基づいて M の値を変更する．
このプラットフォームによるタスクの発行数の上限と下限をそれぞれ p max，p min とする．タスクの発行数を更新した際に，オープンしておく．また，子ノードに対してタプルの要求ができるように，子ノードの Open() をコールする．

5 行目から 13 行目までは GetNext() の処理である．5 行目
から 10 行目までは，親ノードから GetNext() がコールされた場合の処理で，返すタプルがあれば適応したタプルを返し，なければ自身も GetNext() を子ノードにコールすることでタプルを要求する．

11 行目から 13 行目までは，子ノードからタスクの発行のために必要なタプルを要求した結果が得られた場合，タスクに必要なタプルを Ini に格納する．タスク結果が返されたら，結果"を Outi に格納する．14 行目から 20 行目までは Close() の処%理である．Ini , Outi をクローズし，各タスクノードにおける処理を終了する.

#

このとき提案する処理方式ではまず，各パラメータを初期化
し，ルートノードの Open() をコールすることから開始する．

%

%

!

$

ルートノードから必要分の GetNext() がコールされ，必要なタ
プルがあれば親ノードに返し，なければ子ノードに GetNext()
を再帰的にコールする．必要なタプルが発行され，すべての
図 5 シミュレーションにおける実行プランの概要図

タスク処理が終了したら結果を保存し，一度 Close() する．得られた結果をもとに各パラメータについて更新を行い，再び

表2

途中処理結果を用いた実行プランにおける相違点

GetNext() をコールする．という処理を目標タプルが取得できるまで繰り返す．

比較対象

Bottom up T op down Optimistic

Dynamic

また，処理の中でプラットフォームの発行数制約，掲載期間

タスク数

最大限

最小数

必要最低限

必要最低限

制約に触れた場合，手法に基づき各変数について変更を加える．

優先度

子ノード

親ノード

子ノード

子ノード

発行数制御

行わない

行わない

常に必要最低限

動的に変化

7. シミュレーション
実行プラン処理方式における，一般的な処理方式と提案手法

すように，(1) リレーション R あるいは S から取得できるタを用いた処理方式の違いを比較し，提案手法について評価すプル 1 つに対して，金髪であるかどうかを判定する選択タス

る．シミュレーションでは実際のクラウドソーシング作業を想ク:HairTask．(2)R, S から金髪だと判断されたタプルをそれ定し，人間の顔画像分類作業を取り上げる．画像の自動分類はぞれ１つ用いて，それらが同じ人間の画像であるかどうかを判

機械学習などの分野で研究が進められており，その場合に扱う

定する結合タスク:PersonTask の２つを用意する．これらの画像の教師用データセットの構築・評価などにクラウドソーシ

タスクを行った結果から異なる人間について選択し，目標であングを用いることがある [13]．本稿におけるシミュレーション

る 10 組分に相当するタプルを取得することを行う．

では，クラウドソーシングを通して，大量の顔画像から特定の

7. 2 使用した実行プラン処理方式

条件に当てはまるものを取得すること想定し，図 5 の実行プラ

本シミュレーションにおいて使用した実行プラン処理方式はンを用いて「金髪かつ同一人物のペア画像データを取得する」•

発行可能な最大数で発行する方式:Bottom upということを行う．

•

発行可能な最小数で発行する方式:T op down•

最低目標取得数を元にする方式:Optimistic•

本研究の提案手法を用いる方式:Dynamic

7. 1 設定

想定作業を行えるようなデータとタスクの設定を用いてシ
ミュレーションを行う．顔画像は 100 人の人間の顔画像がそれの 4 つであり，その違いについて比較したものを表 2 に示す．

ぞれ 5 枚ずつ計 500 枚集められているものが，2 組存在すると【Bottom up と T op down】

いうことを想定する．

Bottom up では，タスクを発行可能な最大数で発行する．例

7. 1. 1 デ ー タ

えば，HairTask の発行に関して，各リレーションには 500 タ

顔画像のデータは次のように定義する．まず，顔画像データ

プルずつ存在するので，最大数としてそれぞれ 500 タスクを一を保持するリレーション R, S を設定し，500 タプルずつ用意

度に発行する．これに対し，T op down では，タスクを発行可

する．各タプルは顔画像一枚についてのデータを表し次の要素

能な最小数で発行する．したがって，HairTask の発行に関しを持つ.

て，500 タプルが存在していても，発行は 1 タスクずつとなる．

•

id : 各画像を識別するための番号

また，発行するタスクの優先度が Bottom up では子ノードが•hair : 顔画像の髪色を表す

優先，T op down では親ノードが優先される．親ノード優先の•

person : 顔画像の人間を表す

T op down では HairTask により，PersonTask の発行が可能に設定からリレーション R，S に存在するタプルについて，id はなり次第，次に発行するタスクとして PersonTask を優先する．

1 から 500 までが割り振られているものとする．hair は髪色を

これより Bottom up では大量のタスク発行により，無駄な表し，この作業では金髪であるかないかがタスクにより挿入さタスク発行を行う可能性があるが，人間の作業の並列度が高くれる．person には 1 から 100 までの人間を識別するための値なる．逆に T op down では少量でのタスク発行により，一度にがタスクにより挿入される．ここで，各セットに含まれる人間

行えるタスクの数が減るために作業の並列度は低くなるが，タは同じ人間 100 人分とし，各セットから重複しない同一人物のスクの発行数を削減できる．

ペアが 100 組できることが約束されているものとする．

7. 1. 2 タ ス ク
このシミュレーションにおいて使用するタスクは，図 5 に示

【Optimistic と Dynamic】

Optimistic と Dynamic の２つは，前に記述した２つの処理方式が常に最大数，最小数での発行を行うのに対し，タスクの発行数が処理の中で変更される．このとき，発行数の変更に関

表 3 ケース 1 : 発行数と依頼回数の平均値

Bottom up T op down Optimistic Dynamic

して提案手法で説明した，必要な最低タスク発行数を基準にす
る．Optimistic では常に必要最低数で次のタスクを発行するの

Issue

3500

1143.61177.81222.1に対し，提案手法を用いた処理方式である Dynamic では，結Run

21016.5

595.7

263.2

果を用いて次のタスクの発行数を動的に更新する．

7. 3 概要

Bottom up
Top down
Optimistic
Dynamic

Bottom up (2 , 3500)

４つの処理方式について，次の２点で比較・評価を行う．まず，目標を達成するまでに全てのタスクノードで発行したタス
Issue

ク発行数の総数を「総タスク発行数 (以下，Issue)」とする．

Issue を比較することで，タスクをどれほど削減できているかどうかを評価する．同じ Run 回目において依頼されたタスク

1000

は，全て並列作業で処理されることで，同時に結果が得られるとここでは仮定する．各処理方式によって一度に発行するタス
ク数は異なるため，Issue が同じでも Run が異なることが発生する．このとき，一度に発行されるタスクが多いほど人間が

0

500

1000

1500

2000

Run

同時に作業が行えると考えられ，Run を比較することで作業の

図 6 ケース 1 : 金髪 10 人の場合のタスクの発行数と依頼回数

並列度をどれほど上げることができているかどうかを評価する．

表 4 ケース 2 : 発行数と依頼回数の平均値

シミュレーションでは各設定に基づいた違うデータを用いてBottom up T op down Optimistic Dynamic

複数回施行する．このとき，用意したデータに存在する金髪の人間の数により，目標タプルを取得する難易度は変化する．例
えば，金髪の人間が 10 人ならば，最終的に必要な数が 10 人分

Issue

16625

671.3

685.3

689.6

Run

2

618.9

238.1

131.1

であるので，このデータセットから取得できるペア画像データについて全種類取得しなければならない．25 人ならば，そのう

Bottom up
Top down
Optimistic
Dynamic

Bottom up (2 , 16625)

ちの 10 人分で足りるので，選択率として 10 人の場合よりも高10000

くなることが考えられる．このシミュレーションでは用意され場合の２つの場合について 50 回施行する．またワーカの回答
精度を 100%とし，タスクを行った結果，金髪であるのに，金Issue

た人間 100 人のうち，金髪の人間が (1)10 人の場合 (2)25 人の髪でないといった回答は発生しないものとする．

7. 4 結果

1000

シミュレーションの結果について，各ケースにおいて 50 回施行したときの，Issue と Run の平均値の表と散布図を用いて説明する．

0

200

400

600

800

1000

1200

Run

【ケース１: 金髪の人間が 10 人の場合】金髪の人間が 10 人の場合についてのシミュレーション結果についてまとめる (表3 は 50 回施行の平均値，図 6 は Issue と Run についての散布
図を示す)．Bottom up では Issue と Run について，設定から Issue = (500 × 2) + (50 × 50) = 3500，Run = 1 + 1 = 2が得られる．したがって，提案手法 Dynamic は Issue について約 Bottom up の 34%の値で作業を終了できたことが分かる．
図 6 から T op down , Optimistic , Dynamic について，Issue
について平均値としては T op down が最も少なく．Run は

Dynamic が最も少ない結果が得られた．また全体として，Issueの値がが多くなるほど，Run について差が開き，Dynamic がT op down や Optimistic に比べて並列性を確保していることが明らかになった．
【ケース２ : 金髪の人間が 25 人の場合】
金髪の人間が 25 人の場合についてのシミュレーション結果
についてまとめる (表 4 は 50 回施行の平均値，図 7 は Issueと Run についての散布図を示す)．10 人の場合であるケース１

図 7 ケース 2 : 金髪 25 人の場合のタスクの発行数と依頼回数に比べて全体的に Issue，Run の値は少なくなっている．結果の処理に応じてタスクを発行するので，必要なタプルを取得できる確率が高いほど，最終的な値が小さくなる結果が得られた．

Bottom up では Issue と Run について，設定から Issue =(500 × 2) + (125 × 125) = 16625，Run = 1 + 1 = 2 が得られる．したがって，提案手法 Dynamic は Issue について約

Bottom up の 4%の値で作業を終了できたことが分かる．
図 7 から T op down , Optimistic , Dynamic について，金髪の人間が 10 人の場合と同様に，Issue について平均値としては T op down が最も少なく．Run については Dynamic が最も少ない結果が得られた．ただし全体として，Optimistic とDynamic の結果がケース１に比べて近いものが得られた．取得目標であるタプルがケース１よりも取得しやすいために，発行数の更新を行う際の増加数の変化が少なくなったことが原因だと考えられる．

7. 5 考察

今回のシミュレーションではタスクの総発行数を示す Issueと依頼回数を示す Run の値について，提案手法を用いた処理方式である Dynamic と他の処理方式を比較した．結果としてDynamic が，Bottom up よりも Issue を削減し，T op downに比べて Run の値を抑え，作業の並列性を確保できていることが確認できた．また，動的にタスクの発行数を変化させる

Dynamic のほうが，常に最低数で発行する Optimistic より
も，発行数をさほど増加させることなく，並列性を上げていることも確認できた．
しかし，今回のシミュレーションは単純なクラウドソーシン
グを想定しているためいくつかの点でまだ考慮すべき点がある．
第一に，タスクの処理について，実際のクラウドソーシング上
ではワーカの回答精度は 100%ではなく，依頼者が必要としない回答が多く発生する可能性があるため，選択率がシミュレーションよりも低下する可能性がある．第二に，依頼回数である

Run について，実際のクラウドソーシングプラットフォーム上で，人間の手作業により依頼する場合の回数としては多いという点がある．シミュレーションでは Run の値が 100 を超えており，仮に１日に１度，手作業で依頼したとすれば，手間がかかるだけでなく，作業が終了するまでに 100 日以上を要する．
今後はこれらの考慮点を踏まえた，実際のクラウドソーシン
グで行う場合のタスク発行数を動的に決定する際の基準値について検討する必要がある．例えば，Run の値について上限を設定し，基準値を大きくすることで作業の並列性を高め，上限を超えない範囲で作業を終了できるような処理を目指すというよ
うなことが考えられる．

8. まとめと今後の課題
本稿ではクラウドソーシング環境における処理方式実行プランについて提案を行った．シミュレーションにより，目標に必要な最低タスク数と処理結果から導けるデータの選択率など各パラメータを用いて，タスクの発行数を動的に変化させる手法
を用いた処理方式が有効である可能性を示した．
今後の課題として (1) 実際に使われているクラウドソーシン
グプラットフォーム上での評価実験を行うこと．(2) 提案手法
における Run の回数について上限の制約がある場合の，処理の最適化について検討することなどがあげられる．
謝

辞

本 研 究 の 一 部 は ，JST CREST お よ び JSPS 科 研 費（#25240012）の支援による文

献[1] Jeﬀ Howe. The rise of crowdsourcing. Wired Magazine,
Vol. 14, No. 06, pp. 1–5, 2006.
[2] Atsuyuki Morishima, N. Shinagawa, and T. Mitsuishi. Cylog/crowd4u: a declarative platform for complex datacentric crowdsourcing. Proceedings of the VLDB Endow.,
Vol. 5, No. 12, pp. 1918–1921, 2012.

[3] Aditya Ganesh Parameswaran, Hyunjung Park, Hector
Garcia-Molina, Neoklis Polyzotis, and Jennifer Widom.
Deco: declarative crowdsourcing. In Proceedings of the 21st
ACM international conference on Information and knowledge management, pp. 1203–1212. ACM, 2012.
[4] Roy Goldman and Jennifer Widom. WSQ/DSQ: A Practical Approach for Combined Querying of Databases andtheWeb. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data - SIGMOD’00, Vol. 29, pp. 285–296, 2000.
[5] Aditya Parameswaran and Neoklis Polyzotis. Answering
Queries using Humans, Algorithms and Databases. Proceedings of the 2011 Conference on Inovative Data Systems
Research, pp. 160–166, 2011.
[6] Michael J Franklin, Donald Kossmann, Tim Kraska, Sukriti
Ramesh, and Reynold Xin. Crowddb: answering queries
with crowdsourcing. Proceedings of the 2011 ACM SIGMOD International Conference on Management of data,
pp. 61–72, 2011.
[7] Ju Fan, Meihui Zhang, Stanley Kok, Meiyu Lu, andBeng Chin Ooi. Crowdop: Query optimization for declarative crowdsourcing systems. 2016 IEEE 32nd International
Conference on Data Engineering, ICDE 2016, Vol. 27,
No. 8, pp. 1546–1547, 2016.
[8] Amazon mechanical turk. https://www.mturk.com.
[9] Data Systems, Adam Marcus, Eugene Wu, David R Karger,
Samuel Madden, and Robert C Miller. Crowdsourced
Databases : Query Processing with People. Cidr, 2011.
[10] Hyunjung Park, Aditya Parameswaran, and Jennifer
Widom. Query Processing over Crowdsourced Data. 2012.
[11] Ron Avnur and Jm Hellerstein. Eddies: Continuously adaptive query processing. ACM SIGMoD Record, pp. 261–272,
2000.
[12] Hector Garcia-Molina, Jeﬀrey D. Ullman, and Jennifer D.
Widom. Database Systems: The Complete Book (GOAL
Series). Prentice Hall, us ed edition, 10 2001.
[13] a Sorokin and D Forsyth. Utility data annotaton with amazon mechanical turk. Proceedings of the 1st IEEE Workshop
on Internet Vision at CVPR 08, No. c, pp. 1–8, 2008.