A Cache-based Approach to Dynamic
Switching between Different Dataflows
in Crowdsourcing
Yusuke Suzuki†, Masaki Matsubara†, Keishi Tajima‡,
Toshiyuki Amagasa†, and Atsuyuki Morishima††‡

1

Key points of the presentation
1. 【Background】 Crowdsourcing sometimes makes
2. dataflow change halfway, but it costs a lot of money.
3. 【Related Work】 With the method using task result caches,

4. it cannot cope with dataflow change.
5. 【Our Approach】 We propose the method to use caches
6. coping with changing dataflows.

7. 【Simulation】 Our simulation results showed that it is
8. possible to identify the best point to minimize the total cost.

2

Background(1/4) :Crowdsourcing Takes Time and Monetary Cost
Task 1
Please translate thefollowing sentencefrom Japanese toEnglish.

Task 2
Please translate thefollowing sentencefrom English toSpanish.

“Konnichiwa”

WorkerSpanish$0.05 per task

EnglishJapanese$0.10 per task

“Hello”

WorkerCrowdsourcing Characteristics
Because of slow processing by human,
it requires time and monetary costs.
3

Background(2/4) : Changing Dataflows
Because completing all tasks takes long time, we may want
to change the dataflow halfway due to various factors.

“Konnichiwa”

Example: Japanese language data to
be translated increased, and hugemoney cost was expected to incur.

Task 2
Please translate thefollowing sentencefrom English toSpanish

SpanishEnglishJapanese

Task 1
Please translate thefollowing sentencefrom Japanese to
English“Hello”

Change“Konnichiwa”

WorkerSpanishJapanese

Task 3
Please translate thefollowing sentencefrom Japanese toSpanish4

Background(3/4) :Changing dataflows in crowdsourcing are difficult
Switching query plans at appropriate timing.
(Eddies[1] et al.)→ Since it is necessary to develop a mechanism for each typeof operator, such a mechanism cannot be generalized forcrowdsourcing settings where we have variety of tasks

Propose a rerunning method with the task result cache.
→ It is reasonable because the cost of the computer involved
in using caches is low compared to the cost of processing
tasks in crowdsourcing.
[1] Ron Avnur and Joseph M Hellerstein. Eddies: Continuously adaptive query processing. In
ACM sigmod record, Vol. 29, pp. 261–272. ACM, 2000.

5Background(4/4) :It takes extra money cost to redo the task
Changing the dataflow makes it impossible to use the resultof the task performed halfway and the cost for that iswasted.
Unavailable after changing a dataflow
Already paid cost
Japanese

English

Konnichiwa

HelloJapanese

Task1

EnglishSpanishTask2

SpanishChangeTask3

The purpose of our research
To reduce the total monetary cost in the dataflow change
6process

Key points of the presentation
1. 【Background】 Crowdsourcing sometimes makes
2. dataflow change halfway, but it costs a lot of money.
3. 【Related Work】 With the method using task result caches,

4. it cannot cope with dataflow change.
5. 【Our approach】 We propose the method to use caches
6. coping with changing dataflows.

7. 【Simulation】 Our simulation results showed that it is
8. possible to identify the best point to minimize the total cost.

7

Existing Method : Rerunning method withthe task result caches [2]It can resume halfway when crashing
Japanese

Initialrunning

Process by human

EnglishCrash

Konnichiwa

Process by human Spanish
Hola

HelloArigatou

ThanksCreateCacheJapaneseRerunning

CreateJapaneseEnglishEnglishSpanish

Konnichiwa

Hello

HelloHola

ArigatouThanksUse

English

Konnichiwa

HelloArigatouThanksProcess by cache

Use

SpanishHola

Process by cache[2] G. Little et al. “Turkit: human computation algorithms on mechanical turk”. In: UIST. 2010.

8

Existing Method : Cannot use caches
after changing the dataflow[2]Because caches does not correspond to the task in new
dataflow, the caches cannot be used.
Japanese

Initialrunning

Process by human

English

Konnichiwa

HelloArigatouThanksProcess by human Spanish
Hola

CreateCacheChanging adataflow+Rerunning

CreateJapaneseEnglishEnglishSpanish

Konnichiwa

HelloHelloHola

ArigatouThanksJapaneseKonnichiwa

UseSpanish？

Arigatou[2] G. Little et al. “Turkit: human computation algorithms on mechanical turk”. In: UIST. 2010.

9Key points of the presentation
1. 【Background】 Crowdsourcing sometimes makes
2. dataflow change halfway, but it costs a lot of money.
3. 【Related Work】 With the method using task result caches,

4. it cannot cope with dataflow change.
5. 【Our Approach】 We propose the method to use caches
6. coping with changing dataflows.

7. 【Simulation】 Our simulation results showed that it is
8. possible to identify the best point to minimize the total cost.

10Combining caches
Combine cache from task input and task output
Initialrunning

Cache

Japanese

EnglishEnglishSpanish

Konnichiwa

Hello

Hello

Hola

ArigatouThanksCombineCache

Changing adataflow+Rerunning

Japanese

Konnichiwa

Japanese

Spanish

Konnichiwa

Hola

Use

SpanishHola

Arigatou11

Processing data without corresponding cache
In the old dataflow,
only data with no corresponding cache will be processed.
Olddataflow

Japanese

EnglishSpanishkonnichiwa

Hello

Hola

ArigatouThanksCreateCache

Process by cache.
Does not require cost.
New
dataflow
Process by human.
Requires more cost.

Japanese

Spanish

Konnichiha

Hola

Dangling result

Use
Japanese

Spanish

Konnichiha

Hola

Arigatou

12

Process the dangling result in the old dataflow
Reduce wasted task results by executing additional tasks
on dangling results.
Old
dataflow

Japanese

EnglishSpanish

Konnichiwa

Hello

Hola

ArigatouThanksDangling result
Cache

Additional task

Japanese

EnglishEnglishSpanish

Konnichiwa

Hello

HelloHola

ArigatouThanksThanksGrasiasCombine

Not wasted
CacheJapanese

Spanish

Konnichiwa

HolaArigatou

GrasiasResult of additional task

13

Relationship between dangling results and costs
It is not enough to simply process dangling results to the end
Plan 1JapaneseProcess the datain the OLD dataflow Arigatou

Additional task

Already processed
EnglishSpanishThanksDangling result

ComparePlan 2JapaneseProcess the datain the NEW dataflow Arigatou

Additional processing cost in dataflow before change&Processing cost in dataflow after change
SpanishCompare the costs and process with the cheaper dataflow
14

Cost estimation for each dataflow
Monetary cost for the old dataflow
Input

Monetary costfor the olddataflow

Konnichiwa

0.00

Arigatou

0.05

Sayounara

0.15

Input

Monetary costfor the newdataflow

Konnichiwa

0.10

Arigatou

Arigatou

0.10

Sayounara

Sayounara

0.10

Japanese

Cost
0.10

English

Konnichiwa

HelloArigatouThanksCost
0.05

SpanishHola

Sayounara

Monetary cost for the new dataflow
Japanese
Konnichiwa

Cost
0.10

Spanish15

Key points of the presentation
1. 【Background】 Crowdsourcing sometimes makes
2. dataflow change halfway, but it costs a lot of money.
3. 【Related Work】 With the method using task result caches,

4. it cannot cope with dataflow change.
5. 【Our Approach】 We propose the method to use caches
6. coping with changing dataflows.

7. 【Simulation】 Our simulation results showed that it is
8. possible to identify the best point to minimize the total cost.

16

Simulation purpose and Results
Purpose: To show relationship between data processing costand cost before change

The total cost

Results:• it is possible toidentify the best
point to minimizethe total cost.
• There are noobvioussolutions.

The number of the data processed in the old dataflow
17

Summary• We proposed the method to use caches corresponding tochanging dataflows.
• Our simulation showed that it is possible to identify thebest point to minimize the total cost.

• I explored the dataflow including join operation. (poster)

Future Work• Since cost estimation is costly for calculation,• we will consider a method to reduce calculation cost.
18