Friendship-aware task planning in mobile crowdsourcing

Abstract

Recently, crowdsourcing platforms have attracted a number of citizens to perform a variety of locationspecific 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.

Keywords

Mobile crowdsourcing / Task planning / Greedy algorithms / Simulated annealing

References

[1] Armenatzoglou, N., Pham, H., Ntranos, V., , 2015. Real-time multi-criteria social graph partitioning: a game theoretic approach. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.1617–1628. http://dx.doi.org/10.1145/2723372.2749450

[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., , 2012. Whom to ask? Jury selection for decision making tasks on micro-blog services. Proc. VLDB Endow., 5(11):1495–1506. http://dx.doi.org/10.14778/2350229.2350264

[4] Cao, C.C., Tong, Y., Chen, L., , 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. http://dx.doi.org/10.1145/2487575.2487642

[5] Cheng, Y., Yuan, Y., Chen, L., , 2016. DistR: a distributed method for the reachability query over large uncertain graphs. IEEE Trans. Parall. Distr. Syst. , 27(11):3172–3185. http://dx.doi.org/10.1109/TPDS.2016.2535444

[6] Gao, D., Tong, Y., She, J., , 2016. Top-k team recommendation in spatial crowdsourcing. Proc. Int. Conf. on Web-Age Information Management, p.191–204. http://dx.doi.org/10.1007/978-3-319-39937-9_15

[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. http://dx.doi.org/10.1145/100216.100262

[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. http://dx.doi.org/10.1145/2424321.2424346

[9] Kirkpatrick, S., Gelatt, J.C.D., Vecchi, M.P., 1987. Optimization by simulated annealing. Science, 220(4598): 671–680. http://dx.doi.org/10.1126/science.220.4598.671

[10] Li, K., Lu, W., Bhagat, S., , 2014. On social event organization. Proc. 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.1206–1215. http://dx.doi.org/10.1145/2623330.2623724

[11] Liu, X., He, Q., Tian, Y., , 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. http://dx.doi.org/10.1145/2339530.2339693

[12] Mehta, A., 2012. Online matching and ad allocation. Found. Trends Theor. Comput. Sci. , 8(4):265–368. http://dx.doi.org/10.1561/0400000057

[13] Meng, R., Tong, Y., Chen, L., , 2015. CrowdTC: crowdsourced taxonomy construction. Proc. IEEE Int. Conf. on Data Mining, p.913–918. http://dx.doi.org/10.1109/ICDM.2015.77

[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. http://dx.doi.org/10.1145/2470654.2470745

[15] Pan, Y.H., 2016. Heading toward artificial intelligence 2.0. Engineering, 2(4):409–413. http://dx.doi.org/10.1016/J.ENG.2016.04.018

[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. http://dx.doi.org/10.1145/2723372.2749446

[17] She, J., Tong, Y., Chen, L., , 2015b. Conflict-aware event-participant arrangement. Proc. 31st IEEE Int. Conf. on Data Engineering, p.735–746. http://dx.doi.org/10.1109/ICDE.2015.7113329

[18] She, J., Tong, Y., Chen, L., , 2016. Conflict-aware event-participant arrangement and its variant for online setting. IEEE Trans. Knowl. Data Eng., 28(9):2281–2295. http://dx.doi.org/10.1109/TKDE.2016.2565468

[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. http://dx.doi.org/10.1007/978-3-319-03260-3_10

[20] Ting, H.F., Xiang, X.Z., 2015. Near optimal algorithms for online maximum edge-weighted b-matching and twosided vertex-weighted b-matching. Theor. Comput. Sci., 607(2):247–256. http://dx.doi.org/10.1016/j.tcs.2015.05.032

[21] Tong, Y., Chen, L., Cheng, Y., , 2012a. Mining frequent itemsets over uncertain databases. Proc. VLDB Endow., 5(11):1650–1661. http://dx.doi.org/10.14778/2350229.2350277

[22] Tong, Y., Chen, L., Ding, B., 2012b. Discovering thresholdbased frequent closed itemsets over probabilistic data. Proc. IEEE 28th Int. Conf. on Data Engineering, p.270–281. http://dx.doi.org/10.1109/ICDE.2012.51

[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. http://dx.doi.org/10.1145/2339530.2339767

[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. http://dx.doi.org/10.1145/2623330.2623647

[25] Tong, Y., Cao, C.C., Zhang, C.J., , 2014b. Crowd-Cleaner: data cleaning for multi-version data on the web via crowdsourcing. Proc. IEEE 30th Int. Conf. on Data Engineering, p.1182–1185. http://dx.doi.org/10.1109/ICDE.2014.6816736

[26] Tong, Y., Chen, L., She, J., 2015a. Mining frequent itemsets in correlated uncertain databases. J. Comput. Sci. Technol., 30(4):696–712. http://dx.doi.org/10.1007/s11390-015-1555-9

[27] Tong, Y., She, J., Chen, L., 2015b. Towards better understanding of App functions. J. Comput. Sci. Technol., 30(5):1130–1140. http://dx.doi.org/10.1007/s11390-015-1588-0

[28] Tong, Y., She, J., Ding, B., , 2016a. Online minimum matching in real-time spatial data: experiments and analysis. Proc. VLDB Endow., 9(12):1053–1064. http://dx.doi.org/10.14778/2994509.2994523

[29] Tong, Y., She, J., Ding, B., , 2016b. Online mobile micro-task allocation in spatial crowdsourcing. Proc. 32nd IEEE Int. Conf. on Data Engineering, p.49–60. http://dx.doi.org/10.1109/ICDE.2016.7498228

[30] Tong, Y., She, J., Meng, R., 2016c. Bottleneck-aware arrangement over event-based social networks: the maxmin approach. World Wide Web J., 19(6):1151–1177. http://dx.doi.org/10.1007/s11280-015-0377-6

[31] Tong, Y., Zhang, X., Chen, L., 2016d. Tracking frequent items over distributed probabilistic data. World Wide Web J., 19(4):579–604. http://dx.doi.org/10.1007/s11280-015-0341-5

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

[33] Yang, D., Shen, C., Lee, W., , 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. http://dx.doi.org/10.1145/2339530.2339679

[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. http://dx.doi.org/10.1145/2661829.2661880

[35] Zhang, C.J., Tong, Y., Chen, L., 2014b. Where to: crowdaided path selection. Proc. VLDB Endow., 7(14): 2005–2016. http://dx.doi.org/10.14778/2733085.2733105

[36] Zhang, C.J., Chen, L., Tong, Y., , 2015. Cleaning uncertain data with a noisy crowd. Proc. 31st IEEE Int. Conf. on Data Engineering, p.6–17. http://dx.doi.org/10.1109/ICDE.2015.7113268

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag Berlin Heidelberg