DEIM Forum 2013 C4-2

Crowdsourced Join Pre-filter による
Human-powered Join 処理効率化の評価
三津石智巳†

森嶋厚行††

青木 秀人†† 筑波大学大学院 図書館情報メディア研究科 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系/知的コミュニティ基盤研究センター 〒 305–8550 茨城県つくば市春日 1–2
E-mail: †{tomomi,aoki}@slis.tsukuba.ac.jp ††{mori,siena}@slis.tsukuba.ac.jp
あらまし近年，群衆の知や力を利用して計算機だけでは困難な問題の解決を行うクラウドソーシングシステムが数多く登場している．クラウドソーシングシステムには，選択演算や結合演算など DB 操作に対応する人手の演算（Human-powered 演算）がしばしば含まれる．本論文ではそのような演算のひとつである Human-powered Join の効
率化について議論する．これまで，Human-powered Join の効率化手法のひとつとして Join Pre-filter を利用するものが提案されているが，それが適用可能な範囲は限定されていた．本論文では，Join Pre-filter を利用する既存の効率化手法が前提とする仮定が成立しない場合であっても適用可能な効率化手法である Crowdsourced Join Pre-filter を提案し，その理論的・実験的評価を行う．特に，静的なデータベースだけでなく，タプルが継続的に追加される動的なデータベースを対象とした場合においても提案手法が効果的であることを示す．
キーワード

クラウドソーシング

1. は じ め に
計算機ネットワーク技術の発達に伴い，計算機だけではなく人も情報資源や処理装置とみなし，問題解決のためのシステ
ムに含めることが可能になった．その結果，計算機には困難なデータ収集や処理を部分的に人手によって行うクラウドソーシ
ングシステムが数多く出現している [1]．多くのクラウドソーシ
ングシステムは，データの処理・管理などを目的とするデータ中心型である．
データ中心型クラウドソーシングシステムには，選択演算や

図 1 Human-powered Join のタスク：顔写真の被写体の同一性判定（画像は JAFFE Database [11] を利用）

結合演算のような DB 操作に対応する人手の演算（Human-

powered 演算）がしばしば含まれる [3]．Human-powered 演
算のひとつである，人手による選択演算（Human-powered Se-

lection）は，人手による主観的基準（美しい，楽しい等）に基づいて画像の選定を行うような演算である [2]．また，人手による結合演算（Human-powered Join）は，写真共有 SNS において顔写真に人名のタグ付けを行うような演算である．これら

Human-powered 演算の処理コストは高いので，効率化に関する議論が活発に行われている [3] [4] [5] [6]．
本論文では，Human-powered 演算のうち，データ統合等の場面において重要な演算である Human-powered Join の処理
効率化について議論する．Human-powered Join とは，人手によって結合条件の判定を行う結合演算であり，一般に計算機による結合条件の判定が難しい場合に利用される．Human-powered

Join を含む問合せの別の例として，2 つの顔写真の集合から同一人物の顔写真のペアだけを得るような問合せが考えられる．
計算機による被写体の同一性の判定が難しい場合，図 1 のようなタスクを人手によって行う必要がある．

Human-powered Join に対する効率化手法のひとつとして，

論文 [3] では，Join Pre-filter を利用した効率化手法を提案している．この手法のポイントは，クラウドソーシングのプログラマが与える条件から生成される Join Pre-filter によって，結合条件を満たさないタプルのペアを事前に除去する前処理を行うという点である．例えば，同一人物の顔写真のペアだけを得る問合せに対しては，性別の異なる 2 人は同一人物ではないという Join Pre-filter が考えられる．プログラマがその Join

Pre-filter を指定し，クラウドが各タプルに対して性別を入力するタスクを追加で行うことによって，追加タスクの増加分以上に，人手による結合条件判定タスクの数を削減することができる．
しかし，プログラマが常に適切な Join Pre-filter を考えるた
めに必要なドメイン知識を持っているとは限らない．例えば，同一人物の顔写真のペアだけを得る問合せに対して，性別の情報を用いる Join Pre-filter は誰でも思いつくかもしれないが，筑波大学の部屋番号とゼミ名の結合を行うための適切な Join

Pre-filter がなんであるかは誰でも思いつくとは限らない．

我々はプログラマが適切な Join Pre-filter を生成することがSELECT R.img, S.img

できない場合にも適用可能な処理効率化手法 Crowdsourced

FROM R JOIN S

Join Pre-filter（CSJP）を提案している [7] [8] [9]．CSJP で

ON samePerson(R.img, S.img)
図 2 Human-powered Join を含む問合せは，適切な Join Pre-filter の生成をクラウドソーシングによって行う．本論文では，CSJP に関する理論的・実験的な評価結果を示す．CSJP では，タプルが継続的に追加されるような動えることで得られるデータが変化することについて議論してい的なデータベース（例：名簿に新しい人が追加される）におい

る．我々の提案手法とこれらのデータ品質向上のための手法も，ては，効率化のための追加タスクも継続的に増加する．本論文

組み合わせて利用することができる．

では，特にこのような動的なデータベースにおいても提案手法が有効であることを，理論的・実験的に示す．
本論文の貢献は次の通りである．

3. Human-powered Join とその処理効率化
本節では，Human-powered 演算のうち，データ統合等の場（1）クラウドソーシングによる処理効率化．多くのデータ中面において重要な演算である Human-powered Join と，その心型クラウドソーシングシステムは，データ収集や処理をクラ効率化のための Join Pre-filter を利用した効率化手法について

ウドソーシングするが，その処理効率化はプログラマが指定す述べる．

る必要がある．一方，提案手法は，データ収集や処理をクラウ

3. 1 Human-powered Join

ドソーシングするだけでなく，その処理効率化自体もクラウド

Human-powered Join とは，人手によって結合条件の判定をソーシングする手法である．この意味において，提案手法は高行う結合演算であり，一般に計算機による結合条件の判定が難階のクラウドソーシングであるといえる．

しい場合に利用される．Human-powered Join を含む問合せの（2）提案手法の理論的な分析と実験による評価．提案手法を実例として，2 つの顔写真の集合（それぞれ，R(img)，S(img) と現するタスクが適切であることを理論的に評価する．また，提する）から同一人物の顔写真のペアだけを得るような問合せが案手法の有効性をクラウドソーシングプラットフォームである

考えられる．計算機による被写体の同一性の判定が難しい場合，

Crowd4U [10] 上で実際に実験を行った結果を示す．本論文で図 1 のようなタスクを人手によって行う必要がある．この問合は，特に動的なデータベースにおいても提案手法が有効である

せの結合条件を「R.img と S.img の被写体が同一である」とすことを示す．

ると，論文 [4] で提案されている拡張 SQL を用いれば，この問

本論文の構成は次の通りである．2 節では，関連研究につい合せを図 2 のように記述することができる．

て述べる．3 節では，Human-powered Join と，Join Pre-filter

結合条件判定タスク．Human-powered Join を含む問合せを処を利用した効率化手法について述べる．4 節では，提案手法

理するためには，結合条件判定タスクをワーカが行う必要があ

Crowdsourced Join Pre-filter と，その理論的な分析結果につる．具体的には，ワーカは演算対象の 2 つのリレーションの直いて述べる．5 節では，特に，タプルが継続的に追加される動積の全てのタプルに対して「Yes」または「No」を入力する．

的なデータベースを対象とした場合における，提案手法の理論

例えば，図 2 の問合せを処理するためには，ワーカは R と S の的な分析結果について述べる．6 節では，提案手法の実験的評直積に含まれる全ての顔写真のペアに対して，図 1 のような価について述べる．7 節は，まとめと今後の課題である．

フォームから「Yes」または「No」を入力する．問合せの処理

2. 関 連 研 究
我々の知る限り，提案手法はデータ指向クラウドソーシング

結果は，ワーカによって「Yes」が入力されたタプルである．結
合条件判定タスクの数は |R × S| である．

3. 2 Join Pre-filter を利用した効率化手法の処理効率化をクラウドソーシングする唯一の手法である．一

Human-powered Join に対する効率化手法として，Join Pre-方，データ指向クラウドソーシングの処理効率化をプログラ

filter を利用した効率化手法が提案されている．この手法のポマが行う手法はいくつか提案されている．例えば，タスクの大イントは，Join Pre-filter を利用して，結合条件を満たさない

きさや，ユーザインタフェースを変更する手法が提案されていタプルのペアを事前に除去する前処理を行うという点である．

る [3] [4] [5] [6] ．我々の提案手法とこれらの効率化手法は，組

例えば，図 2 の問合せに対するタスクの数は，Join Pre-filter

み合わせて利用することができる．

を生成するための次の 2 つのタスクを生成することで削減する

データ指向クラウドソーシングにおける処理効率化以外の重ことができると考えられる．

要な問題はデータ品質である．データ品質を向上させる手法（ 1 ） R と S の全ての顔写真に対する性別の入力タスク

もいくつか提案されている．例えば，多くのクラウドソーシン（ 2 ） 同性同士の顔写真のペアの被写体同一性判定タスク

グで採用されている多数決 [3] はデータ品質を向上させる手法

論文 [3] では，この Join Pre-filter を利用した問合せは図 3 ののひとつである．ただし，データの品質は大数の法則に依存すように記述する．図 2 との違いは，4 行目に Possibly 句を追加る．別のアプローチとしては，同調ゲーム [12] [13] がある．たすることで，Join Pre-filter の生成に性別の情報が必要であり，だし，合理的なワーカが適切な値を入力することを前提として

性別の情報を Join Pre-filter として利用することを指定していいる．論文 [14] では，GWAP（Game With A Purpose）に対ることである．具体的には，Possibly 句で，Join Pre-filter をして，ゲーム理論による分析および，インセンティブ構造を変生成するための属性 gender を指定している．

SELECT R.img, S.img

な同値類に分割するための属性をプログラマが考える必要が

FROM R JOIN Sある（3. 2 節 Step 1 参照）．しかし，プログラマが必ずしも適ON samePerson(R.img, S.img)

切な属性を考えることができるとは限らない．例えば，同一人

AND POSSIBLY gender(R.img) = gender(S.img)

物の顔写真のペアだけを得る問合せに対して，同値類に分割す

図 3 Join Pre-ﬁlter を利用した図 2 の問合せの処理効率化

るための属性として gender を考えることは誰でもできるかもしれないが，筑波大学の部屋番号と研究室の結合を行う問合せ

Join Pre-filter を利用した問合せの処理．図 3 のような，Joinに対して，どのような属性が適切であるかは必ずしも自明では

Pre-filter を利用した問合せの処理は次のように行われる．

ない．

Step 1. まず，プログラマが Join Pre-filter を生成するため

CSJP では，演算対象の適切な同値類への分割をクラウドの属性（例：属性 gender）を考えて，図 3 のような問合せをソーシングによって行う．したがって，プログラマが適切な同値

クエリプロセッサに入力する．クエリプロセッサは，演算対象類への分割ができない場合も，タスクを行う各ワーカが演算対のリレーション R と S に属性 gender 追加したリレーション

象に関する部分的なドメイン知識を持つ場合は Join Pre-filter

R’(img, gender) と S’(img, gender) を生成する．

を利用した効率化が適用可能である．提案手法のチャレンジは，

Step 2. クエリプロセッサは，リレーション R’ と S’ の全て演算対象の適切な同値類への分割という知的に高度な処理を，の顔写真に対して，属性 gender の属性値を入力するタスクを

小さなタスクの集まりとして実現する点である．我々は，CSJP生成する．このタスクは，Join Pre-filter を利用する効率化ので 3 つのタイプのタスクを利用する．

ために，ワーカが追加で行うタスクである．

本節では，次の問合せ Q1 を利用して 3 タイプのタスクを説Step 3. ワーカが全ての顔写真に属性値を入力すると，ク明する．

エ リ プ ロ セッサ は R’ 1JP S’ を 計 算 す る ．こ こ で ，JP

問合せ Q1：筑波大学の春日エリアには複数の建物があり，各は，Join Pre-filter を利用した効率化を行うための結合条件

建物内の部屋は一意に識別可能な部屋番号（7D202 等）を持つ．

R’.gender=S’.gender である．

また，部屋のうちの一部は，筑波大学図書館情報メディア研究

Step 4. クエリプロセッサは，R’ 1JP S’ の全てのタプルに対科に所属する教員のゼミ（森嶋研等）によって利用されている

して，結合条件判定タスクを生成する．ワーカが全ての結合条件

が，どの部屋がどのゼミによって利用されているかは，ドメイ判定タスクを完了すると，クエリプロセッサは Human-powered

ン固有の知識であり，誰もが知っているわけではない．ここで，Join の処理結果を出力する．

春日エリアの部屋番号の一覧を表すリレーションを R（スキーJoin Pre-filter による結合条件判定タスクの削減数．Join

マは R(部屋番号)) とし，当該研究科のゼミ名の一覧を表すリ

Pre-filter は，Human-powered Join のための結合条件判定タ

レーションを S (スキーマは S(ゼミ名)）とする．R と S のタ

スクを数削する．仮に，R と S の顔写真の男女比が 1 : 1 である
場合，結合条件判定タスク数は |R| · |S| から |R|·|S| + |R| + |S| にプル間を明示的に対応づける属性は存在しないため，これらの削減される．Join Pre-filter を利用した効率化の本質は，演算

号とゼミ名を結びつける Human-powered Join R 1p S （ただ対象を同値類（例：[male], [female]）に分割することである．

し，p = 利用 (部屋番号, ゼミ名)）を問合せ Q1 と呼ぶ．

2

対応付けには人手による判断が必要である．このとき，部屋番

2

3. 3 Perfect Join Pre-filter モデル

4. 1 CSJP のタスク設計

Join Pre-filter は 次 の よ う に モ デ ル 化 す る こ と が で き

簡潔に言うと，CSJP で利用するタスクは，タプルに付与する [3]．N を 問 合 せ に 追 加 さ れ る Possibly 句 の 数 と す る ．

る属性値（例：male, female）の入力をワーカに求めるものと，F = {F1 , F2 , . . . FN } を Join Pre-filter を生成するために追属性値間の非両立性（例：male, female は非両立）の入力を加する属性の集合とする．ここで，Fi は i 番目の Possibly

ワーカに求めるものである．

句で指定されている属性の属性値を含む集合である．例え問題は，一般に Join Pre-filter を生成するために追加する

ば，i 番目で指定されている属性が gender であるとすると，属性（例：gender）がプログラマは事前に分からないこと

Fi = {male, female} である．L を演算対象の各タプルに付与である．そこで，提案手法では，R(. . .) および S(. . .) に個別される付与されるラベルの集合 F1 × . . . × FN とする．つまり，の属性を追加せず，prop と no prop という属性を追加して，

ラベル l ∈ L は F の各属性の属性値を持つ N つ組である．演

R’(. . . , prop, no prop) および S’(. . . , prop, no prop) を作成す

算対象のリレーション R と S の全てのタプルは，付与されるラる．属性 prop は，各タプルに付与される属性値の和集合を表

ベル l によって表されるいずれかの同値類に属する．例えば，

す属性である．一方，属性 no prop は，各タプルに付与される全ての顔写真は，[male], [female] という 2 つのいずれかの同非属性値の和集合を表す属性である．例えば，prop 属性の値

値類に属する．したがって，同じ同値類に属するタプルの組にとして male を持ち，no prop 属性の値として female を持つ

対してのみ人手による結合条件判定を行えばよい．このモデル

タプルは，male と female が同時には成立しないという非両立を，perfect join pre-filter モデルと呼ぶ．

性から得られる．

4. Crowdsourced Join Pre-filter
Join Pre-filter を利用した効率化手法では，演算対象を適切タプルに付与する属性値とそれらの非両立性を記録するために，Name table(name, incompatible names)（図 4）を利用する．各タプル (n, in) において，n は属性値（例：male）で

図4

リレーション Name table

図 6 Type 2 のタスク

図 7 Type 3 のタスク

図 5 Type 1 のタスクあり，in は，非両立な属性値の集合（例：{female}）である．
また，Name table リレーションに含まれる全ての属性値を記

図 8 CSJP で生成されるリレーションの例録するために Names リレーションを利用する．
具体的な設計．CSJP では，Join Pre-filter を利用した問合せType 2. 非両立性入力タスク Type 2 では各 n ∈ Names にの処理（3. 2 節）の Step 1 を除去する．その代わりに，ワーカ

対してタスクが作成される（したがって，タスク数は |Names|

は次の Type 1, Type 2 のタスクを行う．さらに，Step 2 のタである）．各タスクは，図 6 のようなフォームを通じて n とスクを修正し，ワーカは prop と no prop 属性の値を入力する

両立しない全ての n′ ∈ Names − {n} にチェックを入力するもType 3 のタスクを行う．

のである．チェックされた全ての n′ を Names リレーションの（ 1 ） Type 1: タプルに付与する属性値の入力

incompatible names 属性の値として追加する．例えば，図 4（ 2 ） Type 2: 属性値間の非両立性の入力

では「A 棟」と両立しない属性値の集合として「B 棟」「C 棟」（ 3 ） Type 3: prop と no prop 属性の値の入力「D 棟」が入力されている．

以下では，CSJP のための各タスクについて順に説明する．

Type 3. 属性値付与タスク R’ と S’ の 各 タ プ ル に 対 し て

以下では，処理を行うワーカの集合をリレーション Crowd とType 3 のタスクが作成される．このタスクでは，ワーカが表す．

各タプルに適切な属性値を付与する．タスク数は |R| + |S| でType 1. タプルに付与する属性値の入力． Type 1 のタスクある．図 7 のようなフォームを通じて prop の属性値およびでは，各 c ∈ Crowd が，タプルに付与する属性値を図 5 のよ

no prop の属性値を入力する．例えば，図 8 では R’ の部屋番

うなフォームを通じて入力する．フォームのページには，タス号が「7D130」である属性 prop の値として { 春日エリア }，属クに関する説明と，既に入力された属性値（図 5 では，ワーカ

性 no prop の値として {A 棟，B 棟 } が入力されている．

への分かりやすさを考慮して「グループ名」と表記），属性値

CSJP の手続き．CSJP の手続きは次の通りである．

を入力するための HTML フォームが表示されている．さらに，（ 1 ） R(...) および S(...) に，prop と no prop 属性を追加

ワーカが，他に属性値がないことを宣言するためのボタンも配し て ，R’(..., prop, no prop)，S’(..., prop, no prop)

置されている．

を作成する．

入力された属性値はリレーション Name table の name 属性（ 2 ） Type 1 のタスクをワーカに割り当て，ワーカが入力に追加される（図 4）タスク数は，|Crowd| × k + M である．こした属性値を Name table リレーションの name 属性に追加すこで，k は，各 c ∈ Crowd の平均の入力回数，M は終了宣言のる．他に属性値がないことを宣言するためのボタン M 回押ための特別なタスクの入力回数である．

されると，Type 2 のタスクをワーカに割り当て，ワーカが

incompatible names の値を入力する．全ての Type 2 のタス

わない．この時，perfect join pre-filter は，3 つの異なる同値

クが完了すると，Type 3 のタスクがワーカに割り当てられ，

類 [A], [B], [C] を生成する．この時，CSJP の手続きで perfect

ワーカが R’ と S’ リレーションに prop と no prop の値を入力

join pre-filter と同じ同値類が生成できない次の 2 つのケース

する．Type 3 のタスクの処理が行われる間，Type 2 のタスクが存在する．

の結果は no prop の値のいくつかを自動的に計算するのに使わCase A: CSJP の手続きが Type 2 のタスクより前で終了れる．

した場合．このケースでは，CSJP が F1 を分割することはな（ 3 ） R’ 1JP S’ を次の Join Pre-filter で計算する．JP は

い．全ての [A], [B], [C] が F1 の部分集合であることは自明で次の通りである．

ある．

¬(R’.prop ∩ S’.no prop =| ϕ ∨ R’.no prop ∩ S’.prop =| ϕ)Case B: CSJP の手続きが F1 に関する全ての非両立性が入力されるより前で終了した場合．C とそれ以外の属性値の間

すなわち，R’ の属性 prop の値が，S’ の属性 no prop に含まの非両立性が入力されなかった（すなわち ‘A =| B’ だけが入れる場合，タプルの結合を行わない．S’ に対しても同様であ力された）と仮定する．この時，CSJP の手続きは，[A] ∪ [C]る．例えば，図 8 では R’ の部屋番号が「7D130」である属性と [B] ∪ [C] という 2 つの同値類を生成する．具体的には，

prop の値として { 春日エリア }，S’ のゼミ名が「三津石研」

G = {[A] ∪ [C], [B] ∪ [C]} である．したがって，[A], [B], [C]である属性 no prop の値として { 春日エリア } が入力されては，G の部分集合である．一般的に，CSJP の手続きは，「perfect

いる．したがって，これらのタプルの結合は行わない．

join pre-filter が生成する同値類は，G に含まれる全ての非両立でない同値類の部分集合」という条件を満たすように同値類

4. 2 定の集合を生成する．したがって，perfect join pre-filter が生成

理

本節では，CSJP が，Join Pre-filter を利用した効率化手法の一般化であることを示す次の 2 つの定理について述べる．

する全ての同値類は，CSJP によって生成される同値類の部分2集合である．

（1）CSJP は，ワーカによった必要な情報が全て入力されれば，

4. 3 総タスク数

perfect join pre-filter の結果と同等である．
（2）perfect joinType 1 の総タスク数は，|Crowd| × k + M である．ここで，pre-filter で削減されないタプルは，CSJP でも削減されない．

k は，各 c ∈ Crowd の平均の入力回数，M は終了宣言のための

これらの定理は，Type 1 と Type 2 のタスクのみに関係する．

特別なタスクの入力回数である．また，Type 2 のタスク数は

なぜなら，Type 3 のタスクは通常の結合条件判定タスクと本|Names|，Type 3 のタスクにおいて |R| + |S| である．したがっ

質的に同じだからである．

て，総タスク数は次のようになる．

［Theorem 1］ CSJP の手続きは perfect join pre-filter をシ
ミュレート可能である．

2

証明．CSJP の手続きによって生成される Join Pre-filter は，(|Crowd| × k + M ) + |Names| + (|R| + |S|).

次の場合に perfect join pre-filter の手続きによって生成される

5. 動的なデータベースにおける CSJP

Join Pre-filter と等価である．

CSJP では，タプルが継続的に追加されるような動的なデー•

Type 1 のタスクによって入力された属性値の集合がF1 ∪ . . . ∪ FN であり, かつ•る．本節では，動的なデータベースにおける CSJP について説Type 2 のタスクによって，各 Fi に属する fj , fk ∈ Fi

に関する全ての非両立性が入力されている.

タベースにおいては，効率化のためのタスクも継続的に増加す

2

明する．

5. 1 動的なデータベースの分類

次の定理は，各タプルに付与されるラベル l ∈ L（3. 3 節参

動的なデータベースにおいて追加されるタプルは，既存のタ照）によって表されるいかなる同値類も CSJP によってそれ以プルと同じような性質を持っていることもあれば，全く異なる上に分割されないということをいう．すなわち，perfect join

性質を持っていることもある．この観点から動的なデータベー

pre-filter で削減されないタプルは，CSJP でも削減されないとスを分類すると，表 1 に示す 4 つのケースに分類することがでいうことを保証する定理である．

きる．

［Theorem 2］ G を CSJP の手続きによって生成される同値類の集合とする．また，L を perfect join pre-filter において，

表 1 動的なデータベースの分類
既存の属性 Fi の属性値

演算対象の各タプルに付与されるラベルの集合とする．このとき，l ∈ L によって表されるいかなる同値類も G の部分集合で
ある．

2

増えない

増える

新たな属性 Fj の属性値 増えない

Case 1Case 2増える

Case 3

Case 4

証明．Join Pre-filter を生成するために追加する属性を F1 のみであると仮定しても一般性を失わない．なぜなら，perfectjoin pre-filter では，各 Fi が互いに独立していることを仮定しているからである（すなわち，L = F1 × . . . × FN である）．次に，F1 = {A, B, C} とする．同様に，この仮定も一般性を失Case 1: 新しく追加されるタプルが既存のタプルと同じ性質の場合である．具体例を鉄道車両の写真とその路線名（例：山手線，京急線）の結合を行う問合せで考える．この例で，車両

の色で同値類に分割するための既存の属性 color の属性値としの属性値 α, β が現れて，F1 = {A, B, C}, F2 = {α, β} となって，red，blue，green が入力されているとする．Case 1 は，たとする．この時，perfect join pre-filter においては，F1 と既存の路線の鉄道車両の写真が追加される場合である．このF2 は互いに独立していることを仮定しているので，このケース

場合，既存のタプルに付与されている属性値以外は現れない．

は Case 1 と同様である．したがって，Theorem 2 より，l ∈ L

したがって，追加で Type 1 と Type 2 のタスクを行う必要はによって表されるいかなる同値類も G′ の部分集合である．

ない．

Case 4: 既存の属性 F1 の新たな属性値と，新たな属性 F2 の一方，Case 2, Case 3, Case 4 は，新しく追加されたタプル

属性値が現れる場合．F1 = {A, B, C, D}, F2 = {α, β} となっが既存のタプルと異なる性質の場合である．

たとする．この時，perfect join pre-filter においては，F1 とCase 2: 既存のタプルに付与されている属性値以外に，既存のF2 は互いに独立していることを仮定しているので，このケース

属性の属性値が新たに現れる．同じ問合せの例では，新たに路は Case 2 と同様である．したがって，Theorem 2 より，l ∈ L

線の鉄道車両の写真とその路線名が追加される場合である．こによって表されるいかなる同値類も G′ の部分集合である． 2の場合，新しい色の鉄道車両が追加されているとすると，追加

5. 3 総タスク数

で Type 1 と Type 2 のタスクを行う必要がある．例えば，既本節では，動的なデータベースにおける総タスク数について存の属性 color の属性値として，orange が必要になるとする

議論する．リレーション R と S が存在し，R に x タプルが追加と，追加で Type 1 と Type 2 のタスクを行う必要がある．

されたとする．CSJP を適用しない場合には，結合条件判定タ

Case 3: 新たな属性の属性値が現れる．同じ問合せの例では，

スクが x × |S| 増加する．

新たに路線バスの写真とその路線名が追加される場合である．

t1 , t2 , t3 がそれぞれ，Type 1, Type 2, Type 3 で増加する

この場合，例えば，新たな属性 vehicle の属性値として，bus

タスク数とすると，CSJP を適用する場合の総タスク数は，と train が必要になるので，追加で Type 1 と Type 2 のタス

t1 + t2 + t3 増加する．t1 , t2 , t3 については 5. 1 節で述べた Case

クを行う必要がある．

1 の場合と，それ以外のケースの場合の 2 通りで次のようにまCase 4: 既存の属性の属性値が新たに現れ，かつ，新たな属性

とめることができる．

の属性値が現れる．この場合も，追加で Type 1 と Type 2 のCase 1: この場合，既存のタプルに付与されている属性値以外

タスクを行う必要がある．

は現れないので，追加で Type 1 と Type 2 のタスクを行う必5. 2 定要はない．したがって，t1 = 0, t2 = 0, t3 = x である．

理

本節では，CSJP が，動的なデータベースに対しても適用可

Case 2, Case 3, Case 4: この場合，追加で Type 1 と Type能であることを示す定理について述べる．この定理は，動的な

2 と Type 3 のタスクを行う必要がある．Type 1 で追加される属

データベースにおいても，perfect join pre-filter で削減されな性値の数を y とすると，t1 = (|Crowd| × k + M ), t2 = y, t3 = x

いタプルは，CSJP でも削減されないことをことを保証する定

となる．

理である．
［Theorem 3］ G を CSJP の手続きによって生成される同値類の集合とする．その後，タプルが新たに追加された後に，′

6. 実験と評価
本節では，CSJP を評価する実験とその結果について述べる．

CSJP の手続きによって生成される同値類の集合を G とする．

本実験の目的は，CSJP が perfect join pre-filter と比較してど

また，L を perfect join pre-filter において，演算対象の各タプの程度の効率化を実現できるか調査することである．また，動ルに付与されるラベルの集合とする．このとき，l ∈ L によっ的なデータベースにおける CSJP の効率を検証するため，5. 3′

節で理論的に示した動的なデータベースにおける総タスクが，て表されるいかなる同値類も G の部分集合である．

2．

証明．F1 = {A, B, C} とする．また，G = {[A], [B], [C]} とする．この時，動的なデータベースには，次の 4 つのケースが存

実際にどのような値になるかシミュレーションで調査する．
本実験では，学術利用を目的として構築中のクラウドソー

在する（5. 1 参照）．

シングプラットフォーム Crowd4U [10] を利用した．Crowd4U

Case 1: 既存の属性 F1 の属性値以外が現れない場合．こは，閉世界仮説を前提としない Datalog 風の言語 CyLog [10]のケースでは，新たに追加されたタプルに対して，prop とを用いて，データ中心型クラウドソーシングを実現するためのno prop 属性の値を入力する Type 3 のタスクのみを行うので，プラットフォームである．Crowd4U では，登録されたワーカ′

F1 は変化しない．この時，G = {[A], [B], [C]} である．したの属性情報がプログラマに見えており，プログラマはドメイン

がって，Theorem 2 より，l ∈ L によって表されるいかなる同知識を持っていそうなワーカへタスクを依頼することが可能で値類も G′ の部分集合である．

ある．本実験ではこの機能を利用して，タスクの依頼を行った．

Case 2: 既存の属性 F1 の新たな属性値が現れる場合．新し6. 1 実 験 環 境

い属性値 D が現れて，F1 = {A, B, C, D} となったとする．

問合せ．本実験では，Human-powered Join を含み，タスクを

perfect join pre-filter は，[A], [B], [C], [D]} という同値類を生行う際にドメイン知識が必要であると考えられる問合せ Q1 を成する．この時，Theorem 2 より，l ∈ L によって表されるい

Crowd4U 上で実行する．筑波大学に詳しくないプログラマが′かなる同値類も G の部分集合である．

事前に Join Pre-filter のためのヒントを与えることは困難であCase 3: 新たな属性 F2 の属性値が現れる場合．新たな属性ると考えられる．

ワーカ．本実験では Crowd4U を通じて，問合せ Q1 に対する
部分的な知識を持つと思われる学生 5 人を用意し，タスクを行うことを依頼した．
データ．実験に利用するデータとして次の 2 つのリレーションを利用した．各リレーションのタプル数は，R が 52，S が 62 である．

•

R：筑波大学春日エリアの部屋番号一覧•

S：筑波大学図書館情報メディア研究科のゼミ名一覧

パラメータ．本実験における唯一の変数は，M である．これ

図 9 CSJP によるタスク数の削減効果

は，ワーカが，他に属性値がないことを宣言するためのボタン
を Type 1 のタスクで押した回数である（参照 4. 1 節）．本実
験では，M = 5 としている．すなわち，全てのワーカがボタンを押す必要がある．
比較対象．CSJP の比較対象として，一定のドメイン知識を持
つプログラマによる perfect join pre-filter を適用した場合を設定した．具体的には，次の 2 つの異なるレベルのドメイン知識を用いて行われる理想的な効率化を想定し，どれだけのタスクの削減効果があるか計算した．（Perfect 1） building name
属性を R と S に追加する．これは，プログラマが建物名に関するドメイン知識を持っているということを想定している．
（Perfect 2） building name 属性と floor number 属性を Rと S に追加する．これは，プログラマが建物名と階数に関する
ドメイン知識を持っていることを想定している．

CSJP によって入力される属性値は必ずしも全て正しい値と図 10 タスク処理時間分布は限らない．タスク数の削減効果を計算するために，次の 2
つのケースを設定した．（CSJP 1） building name 属性とション S (タプル数 62）に関しては，全てのタプルに対して属

floor number 属性に対応するような属性値（例：7D 棟，1 階

性 prop および，属性 no prop の値が付与された．

など）を CSJP の計算に利用する．（CSJP 2） 入力されたタスク処理時間分布と総タスク処理時間．本実験では，ワー全ての属性値を CSJP の計算に利用する．

カが各タスクを選択してから終了ボタンを押すまでの時間を

6. 2 実験結果と考察

タスクの処理時間として計測した．タスク処理時間分布図を

静的なデータベースに対する CSJP の効率．図 9 は，Join

図 10 に示す．これらのタスクの処理時間の平均は約 40 秒でPre-filter を適用しない場合の総タスク数（JP なし），一定のドあり，約 84%のタスクが 60 秒以下で完了した．この結果から，メイン知識を持つプログラマによる perfect join pre-filter であCrowdsourced Join Pre-filter で利用するタスクは，ワーカにる Perfect 1 と Perfect 2 を利用した場合の総タスク数，CSJP

とって短時間で比較的容易に実行可能なタスクであったと考えである CSJP 1 と CSJP 2 を利用した場合の総タスク数を比られる．このことは，本論文で提案するタスク設計が適切であ較したグラフである．CSJP 1 では総タスク数が 1617 であり，ることを示唆している．

十分に効率的な Perfect 1 と Perfect 2 の中間のタスク数であ

総タスク処理時間は，1 時間 42 分 26 秒であった．

る．また，CSJP 2 では総タスク数が 734 であり，Perfect 2 よ6. 3 動的なデータベースのシミュレーション

り多くのタスクが削減されている．これは，building name 属

動的なデータベースにおける CSJP の効率を検証するため，性と floor number 属性以外にも，Join Pre-filter に利用可能

5. 3 節で理論的に示した動的なデータベースにおける総タスク

な属性値が数多く入力されたからである．これらの結果は，各が，実際にどのような値になるかシミュレーションで調査する．

c ∈ Crowd が問合せ Q1 に対する部分的な知識を持つときに部屋番号リレーション R にいくつかのタプルが追加されることは，CSJP による効率化が有効である可能性を示唆している．

をシミュレーションするために，次のようなシナリオを設定す

CSJP による各タスクの実行結果の詳細は次の通りであった．

る．なお，このシナリオは，5. 1 節で述べた Case 2 に対応する．

まず，Type1 のタスクでは，29 の分割ラベルが付与された．次シミュレーションのシナリオ．筑波大学の春日エリアには講義に，Type2 のタスクでは，分割ラベルの組合せ 29 C2 のうち，棟・研究棟・ユニオン棟という 3 つの建物がある．このうち，ユ40 の非両立ラベルのペアが発見された．また，Type3 の属性

ニオン棟という建物が新しく建造され，いくつかの部屋が新た値付与タスクでは，部屋番号リレーション R（タプル数 52) にに増えるという状況を仮定する．具体的には，部屋番号リレー

関して，全てタプルに対して属性 prop の値が付与され，51 のション R が 52 のうち，はじめから存在するタプル数が 40（約

タプルに対して属性 no prop の値が付与された．ゼミ名リレー77%），新たに追加されるタプル数が 12（約 33%）であること

文

図 11

動的なデータベースにおける CSJP によるタスク数の削減効果を仮定する．ゼミ名リレーション S にはタプルは追加されない．
ユニオン棟が建造されるまでは，Join Pre-filter を生成するために追加する属性 building name の属性値は { 講義棟, 研究棟 }であり，属性値 floor number の属性値は {1F, 2F, 3F, 4F, 5F}であるとする．ユニオン棟は，4 階建ての建物であるので，タプルが追加されることによって追加される属性値は「ユニオン棟」のみを仮定する．
総タスク数のシミュレーション．このようなシナリオで，動的なデータベースにおける総タスク数を計算する．Type 1 のタ
スクでは，新たにユニオン棟という建物名が属性値として入力されるので，1 タスク増える．Type 2 のタスクでは，ユニオン棟とそれ以外の既存の属性値との非両立性が入力されるので，1 タスク増える．ここでは，「講義棟 =| ユニオン棟」「研究棟=| ユニオン棟」の非両立性が入力されたとする．Type 3 のタスクでは，新たに追加される 12 のタプルに属性値を付与するために，12 タスク増える．したがって，Join Pre-filter のためのタスク数は 14 である
次に，削減されるタスク数を計算する．新たなタプルが 12追加されたとき，Join Pre-filter を適用しない場合のタスク数は 744 である．一方，Type 1, Type 2, Type 3 を 14 タスクを行うことによって，タスク数を 179 まで削減できる．このシナリオにおいては，動的なデータベースにおいても提案手法が有効であることが分かった．

7. まとめと今後の課題
本論文では，Human-powered Join に対する効率化手法である Crowdsourced Join Pre-filter に対する理論的な分析および，実験による評価を行った．具体的には，Crowdsourced Join

Pre-filter のためのタスク設計が適切であることを理論的に示し，実環境での効果を実験によって示した．また，静的なデー
タベースだけでなく，タプルが継続的に追加される動的なデー
タベースに対しても提案手法が有効であることを示した．今後の課題としては，他の効率化手法やデータ品質管理手法等と組み合わせた場合の分析を行うことがあげられる．

謝

辞ゼミなどにおいてコメントいただきました，筑波大学 杉本重雄教授，阪口哲男准教授，永森光晴講師に感謝いたします．本
研究の一部は JST さきがけ「情報環境と人」による．

献[1] Doan AnHai, Ramakrishnan Raghu, Halevy Alon Y..
“Crowdsourcing systems on the World-Wide Web. Commun.ACM. vol. 54, no. 4, pp. 86-96, 2011[2] gwap.com. “Matchin”.
http://www.gwap.com/gwap/gamesPreview/matchin/[3] Marcus Adam, Wu Eugene, Karger David R., Madden
Samuel, Miller Robert C.. “Human-powered Sorts andJoins”. PVLDB 2011, vol. 5, no. 1, pp. 13-24, 2011.
[4] Marcus Adam, Wu Eugene, Madden Samuel, Miller Robert
C.. “Crowdsourced Databases: Query Processing with People”. CIDR 2011, pp. 211-214, 2011.
[5] Franklin Michael J., Kossmann Donald, Kraska Tim,
Ramesh Sukriti, Xin Reynold.. “CrowdDB: answering
queries with crowdsourcing”. SIGMOD 2011, pp. 61-72,
2011.
[6] Parameswaran Aditya G., Polyzotis Neoklis.. “Answering
Queries using Humans, Algorithms and Databases”. CIDR
2011, pp. 160-166, 2011.
[7] 三津石智巳，森嶋厚行，品川徳秀，青木秀人．“クラウドソー
シングによる Human-powered Join の効率化”．DEIM 2012,2012．
[8] 三津石智巳，森嶋厚行，品川徳秀，青木秀人．“Human-powered
Join 処理に対するクラウドソーシングに効率化手法の評価”．
SoC 2012, pp. 103-108，2012．
[9] Tomomi Mitsuishi, Atsuyuki Morishima, Norihide Shinagawa, Hideto Aoki. “Eﬃcient Evaluation of Human-powered
Joins with Crowdsourced Join Pre-ﬁlters”. ICUIMC 2013,2013 .
[10] Atsuyuki Morishima, Norihide Shinagawa, Tomomi Mitsuishi, Hideto Aoki, Shun Fukusumi. “CyLog/Crowd4U:
A Declarative Platform for Complex Data-centric Crowdsourcing”. VLDB 2012, August 2012 (demo, to appear).
[11] Michael J. Lyons, Akamatsu Shigeru, Kamachi Miyuki, Gyoba Jiro. “Coding Facial Expressions with Gabor Wavelets”.
Third IEEE International Conference on Automatic Faceand Gesture Recognition. pp. 200-205, 1998.
[12] Atsuyuki Morishima, Norihide Shinagawa, Shoji Mochizuki.
“The Power of Integrated Abstraction for Data-Centric Human/Machine Computations”. VLDS 2011: 7-10
[13] gwap.com. “ESP Game”.
http://www.gwap.com/gwap/gamesPreview/espgame/[14] Shaili Jain, David C. Parkes: A Game-Theoretic Analysis
of Games with a Purpose. WINE 2008: 342-350