Full Text:   <1807>

Summary:  <1519>

CLC number: TP3

On-line Access: 2017-01-20

Received: 2016-12-23

Revision Accepted: 2017-01-09

Crosschecked: 2017-01-10

Cited: 1

Clicked: 4259

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Wen-jun Wu

http://orcid.org/0000-0003-0953-0115

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.1 P.107-121

http://doi.org/10.1631/FITEE.1601860


Friendship-aware task planning in mobile crowdsourcing


Author(s):  Yuan Liang, Wei-feng Lv, Wen-jun Wu, Ke Xu

Affiliation(s):  State Key Laboratory of Software Development Environment, School of Computer Science, Beihang University, Beijing 100191, China

Corresponding email(s):   liangyuan120@nlsde.buaa.edu.cn, lwf@nlsde.buaa.edu.cn, wwj@nlsde.buaa.edu.cn, kex@nlsde.buaa.edu.cn

Key Words:  Mobile crowdsourcing, Task planning, Greedy algorithms, Simulated annealing


Yuan Liang, Wei-feng Lv, Wen-jun Wu, Ke Xu. Friendship-aware task planning in mobile crowdsourcing[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 107-121.

@article{title="Friendship-aware task planning in mobile crowdsourcing",
author="Yuan Liang, Wei-feng Lv, Wen-jun Wu, Ke Xu",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="18",
number="1",
pages="107-121",
year="2017",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1601860"
}

%0 Journal Article
%T Friendship-aware task planning in mobile crowdsourcing
%A Yuan Liang
%A Wei-feng Lv
%A Wen-jun Wu
%A Ke Xu
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 1
%P 107-121
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1601860

TY - JOUR
T1 - Friendship-aware task planning in mobile crowdsourcing
A1 - Yuan Liang
A1 - Wei-feng Lv
A1 - Wen-jun Wu
A1 - Ke Xu
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 1
SP - 107
EP - 121
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1601860


Abstract: 
Recently, crowdsourcing platforms have attracted a number of citizens to perform a variety of location-specific tasks. However, most existing approaches consider the arrangement of a set of tasks for a set of crowd workers, while few consider crowd workers arriving in a dynamic manner. Therefore, how to arrange suitable location-specific tasks to a set of crowd workers such that the crowd workers obtain maximum satisfaction when arriving sequentially represents a challenge. To address the limitation of existing approaches, we first identify a more general and useful model that considers not only the arrangement of a set of tasks to a set of crowd workers, but also all the dynamic arrivals of all crowd workers. Then, we present an effective crowd-task model which is applied to offline and online settings, respectively. To solve the problem in an offline setting, we first observe the characteristics of task planning (CTP) and devise a CTP algorithm to solve the problem. We also propose an effective greedy method and integrated simulated annealing (ISA) techniques to improve the algorithm performance. To solve the problem in an online setting, we develop a greedy algorithm for task planning. Finally, we verify the effectiveness and efficiency of the proposed solutions through extensive experiments using real and synthetic datasets.

移动众包环境下基于友谊度的任务规划

概要:最近,众包平台已吸引了大量的注册用户在线下执行特定的任务。然而,大部分现有方法仅考虑了工人和任务信息都已提前获知的情况(静态离线情景),而较少考虑到工人动态抵达的情况(动态在线情景)。因此,当工人动态抵达时,如何给工人安排适合的任务以获得其最大的满意度成为了一个具有挑战性的问题。为解决这一问题,本文提出了一种有用并且普遍的人工-任务模型,该模型不仅考虑在静态离线时给工人安排任务的情况,还同时考虑了在工人动态抵达时如何给工人安排合适的任务。在本文中,为解决静态离线情景下的任务分配问题,我们首先提出一个有效的贪心算法。由于贪心算法极易陷入局部最优,我们又加入了模拟退火法来提高贪心算法的性能。另外,为解决动态在线情景下的分配问题,我们提出了一种贪心算法。最后,在真实数据集和具有不同分布人造数据集上进行了大量实验,实验结果验证了算法的效果与性能。

关键词:移动众包;任务规划;贪心算法;模拟退火

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Armenatzoglou, N., Pham, H., Ntranos, V., et al., 2015. Real-time multi-criteria social graph partitioning: a game theoretic approach. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.1617-1628.

[2]Burkard, R.E., Dell’Amico, M., Martello, S., 2009. Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia.

[3]Cao, C.C., She, J., Tong, Y., et al., 2012. Whom to ask? Jury selection for decision making tasks on micro-blog services. Proc. VLDB Endow., 5(11):1495-1506.

[4]Cao, C.C., Tong, Y., Chen, L., et al., 2013. WiseMarket: a new paradigm for managing wisdom of online social users. Proc. ACM SIGGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.455-463.

[5]Cheng, Y., Yuan, Y., Chen, L., et al., 2016. DistR: a distributed method for the reachability query over large uncertain graphs. IEEE Trans. Parall. Distr. Syst., 27(11):3172-3185.

[6]Gao, D., Tong, Y., She, J., et al., 2016. Top-k team recommendation in spatial crowdsourcing. Proc. Int. Conf. on Web-Age Information Management, p.191-204.

[7]Karp, R.M., Vazirani, U.V., Vazirani, V.V., 1990. An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Symp. on Theory of Computing, p.352-358.

[8]Kazemi, L., Shahabi, C., 2012. GeoCrowd: enabling query answering with spatial crowdsourcing. Proc. 20th Int. Conf. on Advances in Geographic Information Systems, p.189-198.

[9]Kirkpatrick, S., Gelatt, J.C.D., Vecchi, M.P., 1987. Optimization by simulated annealing. Science, 220(4598): 671-680.

[10]Li, K., Lu, W., Bhagat, S., et al., 2014. On social event organization. Proc. 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.1206-1215.

[11]Liu, X., He, Q., Tian, Y., et al., 2012. Event-based social networks: linking the online and offline social worlds. Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.1032-1040.

[12]Mehta, A., 2012. Online matching and ad allocation. Found. Trends Theor. Comput. Sci., 8(4):265-368.

[13]Meng, R., Tong, Y., Chen, L., et al., 2015. CrowdTC: crowdsourced taxonomy construction. Proc. IEEE Int. Conf. on Data Mining, p.913-918.

[14]Musthag, M., Ganesan, D., 2013. Labor dynamics in a mobile micro-task market. Proc. SIGCHI Conf. on Human Factors in Computing Systems, p.641-650.

[15]Pan, Y.H., 2016. Heading toward artificial intelligence 2.0. Engineering, 2(4):409-413.

[16]She, J., Tong, Y., Chen, L., 2015a. Utility-aware social event-participant planning. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.1629-1643.

[17]She, J., Tong, Y., Chen, L., et al., 2015b. Conflict-aware event-participant arrangement. Proc. 31st IEEE Int. Conf. on Data Engineering, p.735-746.

[18]She, J., Tong, Y., Chen, L., et al., 2016. Conflict-aware event-participant arrangement and its variant for online setting. IEEE Trans. Knowl. Data Eng., 28(9):2281-2295.

[19]Sun, Y., Chen, C.C., 2013. A novel social event recommendation method based on social and collaborative friendships. Int. Conf. on Social Informatics, p.109-118.

[20]Ting, H.F., Xiang, X.Z., 2015. Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching. Theor. Comput. Sci., 607(2):247-256.

[21]Tong, Y., Chen, L., Cheng, Y., et al., 2012a. Mining frequent itemsets over uncertain databases. Proc. VLDB Endow., 5(11):1650-1661.

[22]Tong, Y., Chen, L., Ding, B., 2012b. Discovering threshold-based frequent closed itemsets over probabilistic data. Proc. IEEE 28th Int. Conf. on Data Engineering, p.270-281.

[23]Tong, Y., Chen, L., Yu, P.S., 2012c. UFIMT: an uncertain frequent itemset mining toolbox. Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.1508-1511.

[24]Tong, Y., Cao, C.C., Chen, L., 2014a. TCS: efficient topic discovery over crowd-oriented service data. Proc. 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.861-870.

[25]Tong, Y., Cao, C.C., Zhang, C.J., et al., 2014b. CrowdCleaner: data cleaning for multi-version data on the web via crowdsourcing. Proc. IEEE 30th Int. Conf. on Data Engineering, p.1182-1185.

[26]Tong, Y., Chen, L., She, J., 2015a. Mining frequent itemsets in correlated uncertain databases. J. Comput. Sci. Technol., 30(4):696-712.

[27]Tong, Y., She, J., Chen, L., 2015b. Towards better understanding of App functions. J. Comput. Sci. Technol., 30(5):1130-1140.

[28]Tong, Y., She, J., Ding, B., et al., 2016a. Online minimum matching in real-time spatial data: experiments and analysis. Proc. VLDB Endow., 9(12):1053-1064.

[29]Tong, Y., She, J., Ding, B., et al., 2016b. Online mobile micro-task allocation in spatial crowdsourcing. Proc. 32nd IEEE Int. Conf. on Data Engineering, p.49-60.

[30]Tong, Y., She, J., Meng, R., 2016c. Bottleneck-aware arrangement over event-based social networks: the max-min approach. World Wide Web J., 19(6):1151-1177.

[31]Tong, Y., Zhang, X., Chen, L., 2016d. Tracking frequent items over distributed probabilistic data. World Wide Web J., 19(4):579-604.

[32]West, D.B., 2001. Introduction to Graph Theory. Pearson.

[33]Yang, D., Shen, C., Lee, W., et al., 2012. On socio-spatial group query for location-based social networks. Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.949-957.

[34]Zhang, C.J., Chen, L., Tong, Y., 2014a. MaC: a probabilistic framework for query answering with machine-crowd collaboration. Proc. 23rd ACM Int. Conf. on Information and Knowledge Management, p.11-20.

[35]Zhang, C.J., Tong, Y., Chen, L., 2014b. Where to: crowd-aided path selection. Proc. VLDB Endow., 7(14): 2005-2016.

[36]Zhang, C.J., Chen, L., Tong, Y., et al., 2015. Cleaning uncertain data with a noisy crowd. Proc. 31st IEEE Int. Conf. on Data Engineering, p.6-17.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE