TY - GEN
T1 - SLADE
T2 - 35th IEEE International Conference on Data Engineering, ICDE 2019
AU - Tong, Yongxin
AU - Chen, Lei
AU - Zhou, Zimu
AU - Jagadish, Hosagrahar Visvesvaraya
AU - Shou, Lidan
AU - Lv, Weifeng
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2019/4/1
Y1 - 2019/4/1
N2 - A crowdsourcing task in real-world applications often consists of thousands of atomic tasks. A common practice to distribute a large-scale crowdsourcing task is to pack atomic tasks into task bins and send to crowd workers in batches. It is challenging to decompose a large-scale crowdsourcing task into task bins to ensure reliability at a minimal total cost. In this paper, we propose the Smart Large-scAle task DEcomposer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove its NP-hardness and study two variants of the problem. For the homogeneous SLADE problem, we propose a greedy algorithm and an approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, we extend this framework and prove its approximation guarantee. Extensive experiments validate the effectiveness and efficiency of the solutions. © 2019 IEEE.
AB - A crowdsourcing task in real-world applications often consists of thousands of atomic tasks. A common practice to distribute a large-scale crowdsourcing task is to pack atomic tasks into task bins and send to crowd workers in batches. It is challenging to decompose a large-scale crowdsourcing task into task bins to ensure reliability at a minimal total cost. In this paper, we propose the Smart Large-scAle task DEcomposer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove its NP-hardness and study two variants of the problem. For the homogeneous SLADE problem, we propose a greedy algorithm and an approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, we extend this framework and prove its approximation guarantee. Extensive experiments validate the effectiveness and efficiency of the solutions. © 2019 IEEE.
KW - Crowdsourcing
KW - Task assignment
KW - Task decomposition
UR - http://www.scopus.com/inward/record.url?scp=85067971242&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85067971242&origin=recordpage
U2 - 10.1109/ICDE.2019.00261
DO - 10.1109/ICDE.2019.00261
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781538674741
VL - 2019-April
T3 - Proceedings - International Conference on Data Engineering
SP - 2133
EP - 2134
BT - Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
PB - IEEE Computer Society
Y2 - 8 April 2019 through 11 April 2019
ER -