1-S

Efficient Pipeline Processing of Crowdsourcing Workflows
Ken Mizusawa†, Keishi Tajima‡, Masaki Matsubara†, Toshiyuki Amagasa†, Atsuyuki Morishima††‡Approache

Background

Pipeline processing of workflows
with price control

Pipeline Crowdsourcing
Sequential workflows

Documents

ENGLISH
DOCUMENTREVISEDDOCUMENT

Find

point out the location to be revisedFixrevise the phrases at these locations

VerifyTask 1
Task 2

decide whether the revision is appropriate
Task 3Using workflow to crowdsource a task of revising a document

The problems handled by crowdsourcing are becoming
more complex, and we need to use workflows that involve
more than one type of subtasks with dataflow among them

Our approach is to control the budget distribution tosubtasks in order to balance the execution speed of
the subtasks and to improve throughput of overall
sequential workflows.

Bernstein, Michael S., et al. "Soylent: a word processor with a crowd inside.
" Communications of the ACM 58.8 (2015): 85-94.

Dynamically changing the price setting
according to the progress of the workflow

Proposed Framework< : Budget!

Performed tasks

Pull#$($,*,$,*#%(%,*,%,*⋮#&

at each Interval +Priceupdater,&,*(&,*Updating Prices
Let (-,* be the price. Let ,-,* be the number of task instances of #that workers have already completed at time . · +.
i ,k" − ,-,*(′-,* = ( &)9∑67$ " − ,-,*

Workers
We assign the same amount of budget B/D to each of the D data items,
and distribute them equally to the N tasks in W<(-,: =">Given the inputs, the framework generates tasks for #- and updates the prices for the tasksaccording to the progress of execution. The framework monitors the progress status of thetasks at each interval +, and computes the price (-,* for each #- for the .-th interval according
to their status at that time.

Dynamic pricing was up to 1.8 times faster on averagethan stepwise batch execution with fixed prices

ExperimentComparing four methods (one stepwise batch execution
and three pipeline processing) in a sequential workflow

All tasks were submitted via Amazon Mechanical Turk.
Workers could perform only one task instance for each task.

We ran the workflow 14 times with each scheme.
MethodStepwise

NameStepwise

Change_p0

Change_p1

Change_p3

Controlnonoyesyes-#tasks in one process

Parameter ; controls the degree of the influence over (′-,*Processing Flow

Initial Setting

Parameter

we assign larger weights to tasks with moretask instances that have not yet been performed.

We normalize (′-,* so that ∑&$ (′-,* = 1 , and compute (-,* (-,* = (-,: (′-,*Pipeline

p=0150 (=3×50)

p=1Budget

p=3$ 6.00

ResultCost＊＊＊500＊ ・・・ < 0.05
＊ ＊ ・・・ < 0.01

400
300300.1Average Time
221.9

200

158.7

187.4

About Total cost
Average and maximum
p1 : $5.51 , $5.70
p3 : $5.62 , $5.85(complete under budget)

Quality
Accuracy of the four methods
was not statistically significant
81%, 82%, 86%, and 82% for
Stepwise, Pipeline_p0, _p1,
and _p3,respectively

1000

Proposed
MethodBox plot of total completion time of each method

Time600
Total completion time (min)"Stepwise

Pipeline_p0 Pipeline_p1 Pipeline_p3

Multiple comparison tests with Bonferroni correction revealed significant differences between Stepwise
and Pipeline_p1 (p<.01), and between Stepwise and Pipeline_p3 (p<.05) in the total processing time.