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

Background‡

Problem & Purpose
Existing method cannot cope with the changing dataflows[1].

We may want to change dataflows halfway.
Dataflow Example:
Identifying the missing and survivors when a disaster occurs
Task 1
Please enter thecharacteristics ofthe person in thephoto.

Task 2 (⋈)
Are the people in
the two photos thesame person?

30s, Woman30s
Woman

SubmitTask
ResultCacher’1(r1, 30s, Woman)

Same or not(r’1, s’1) → 〇r2⋈
S(Photos ofsurvivors)S’(Survivors andCharacteristics)

s1s’1(s1, 30s, Woman)s2s’2(s2, 20s, Man)

RR’S

r1 r’1(r1, 30s, Woman)

S’R’S’

Same or not

r’1 s’1 ○s1 s’1(s1, 30s, Woman)s2 s’2(s2, 20s, Man)

Changing dataflows&Running

Results

Photos ofsurvivors

Photos ofMissing person

Onemissing person

r1

Use

Multiple answers
can be obtainedwith one task

Task 3 (⋈)
Is there someone in the photo on the right thatshows the person on the left?

R’(The missing andCharacteristics)

Dangling results

30s
Woman

ChangeExample: Change to an efficientmethod because the number ofsurvivors was less than expected.

Results

Photos of
Photos ofMissing person survivors

Initial runningR(Photos ofthe missing)R(Missing)

S(Survivor)

r1

s1

r2

s2

Same or not

PurposeAll survivors

To reduce the total monetary cost in the dataflow change process[1] G. Little, L. B. Chilton, M. Goldman, and R. C. Miller, “Turkit: human computation algorithms on mechanical turk,” in Proc. of ACM UIST 2010, 2010, pp. 57–66.

Proposed Method Propose a rerunning method in changing dataflows.

Combining Caches

Cost Estimation

Additional Task

Compare the costs of the two plans

Task R R’
Result r1 r’1(r1, 30s, Woman)
Cache

SS’

R’

S’

s1s’1(s1, 20s, Woman)r’1 s’1 ×s2s’2(s2, 30s, Man)

Issue additional tasks to use dangling results.
Monetary cost for the old dataflow
However, there is a tradeoff between cost reduction by cacheR(Photos of Cost R’(The missing andand the cost increase by additional tasks.
the missing) 0.05 Characteristics)

Same or not

CombineR’(The missing andCharacteristics)

r1

r’1(r1, 30s, Woman)

RS

Same or not

r1

s1

×

Use

s1

s’1(s1, 20s, Man)s2

s’2(s2, 30s, Woman)

S(Survivor)

Same or not

r1

s1(r1, s1) → ×d1

c2

d1

s1

(r1, s1) → ×

R(The missing)

S(Survivors)

r2

s2(r1, s2) → 〇

r1

s1

r2

s2

s1
s2

0.10
0.15

InputsMonetary costfor the newdataflow

Cost0.12

r10.12Same or not

r2s1
s2

0.12
0.12
0.12

d1

21 datac4

d1

18 datac4

d1

15 datac6

d1

12 datac7

Task cost distribution

Simulation Resultsd : Data node, c : Costd1

9 datac8

d1

6 datac9d9

3 datac10

Total cost of the task in the dataflow before change : 1.0
The task cost in the dataflow after change : 0.7
Cost distribution

d10

The minimum costof each distribution
appears in red.

1：Constant
2：Linear increase
3：Linear decrease
4：Low & High

Processing order
Process from data closest to the last nodes’2(s2, 30s, Woman)

r1

Task cost

Data location at changing
3 dangling results for each data nodes2

Same or notc’=0.7

Num of tasks
10s’1(s1, 20s, Man)

0.05
0.15

It is possible to identify the best point to minimize the total cost
and there is no obvious solution.
24 datac3

s1

S(Survivor)

The total cost

d0c1

27 data

Cost S’(Survivors and0.05 Characteristics)

R(Missing)

Simulation settings
30 data

S(Photos ofsurvivors)

r1r2

Monetary cost for the new dataflow

Process by cache

Simulation
33 data

Additional tasks2

r2(r’1, s’2) → 〇ChangeR(Missing)⋈Same or not⋈S’(Survivors andCharacteristics)(r’1, s’1) → ×

r2(r’1, s’1) → ×

S(Photos ofsurvivors)r’1(r1, 30s, Woman)

r1

r2

Task
ResultCacheNewdataflow

R(Photos ofthe missing)

Cost
0.05 Same or not

Monetary costfor the oldInputs dataflow

5：High & Low
Task number in the dataflow before change

The number of the data processed in the old dataflow

The Second IEEE Workshop on Human-in-the-loop Methods and Human Machine Collaboration in BigData (IEEE HMData2018), Dec. 10th, Seattle, US