空间众包环境下的3类对象在线任务分配
|
摘要
随着移动互联网技术与O2O(offline-to-online)商业模式的发展,各类空间众包平台变得日益流行,如滴滴出行、百度外卖等空间众包平台更与人们日常生活密不可分.在空间众包研究中,任务分配问题更是其核心问题之一,该问题旨在研究如何将实时出现的空间众包任务分配给适宜的众包工人.但大部分现有研究所基于的假设过强,存在两类不足:(1)现有工作通常假设基于静态场景,即,全部众包任务和众包工人的时空信息在任务分配前已完整获知,但众包任务与众包工人在实际应用中动态出现,且需实时地对其进行任务分配,因此,现存研究结果在实际应用中缺乏可行性;(2)现有研究均假设仅有两类众包参与对象,即众包任务与众包工人,而忽略了第三方众包工作地点对任务分配的影响.综上所述,为弥补上述不足,提出了一类新型动态任务分配问题,即,空间众包环境下的3类对象在线任务分配.该问题不但囊括了任务分配中的3类研究对象,即众包任务、众包工人和众包工作地点,而且关注动态环境.进而设计了随机阈值算法,给出了该算法在最差情况下的竞争比分析.采用在线学习方法进一步优化了随机阈值算法,提出自适应随机阈值算法,并证明该优化策略可逼近随机阈值算法使用不同阈值所能达到的最佳效果.最终通过在真实数据集和具有不同分布人造数据集上进行的大量实验,验证了算法的效果与性能.
With the rapid development of mobile Internet techniques and Online-to-offline(O2O) business models, various spatial crowdsourcing(SC) platforms become popular. In particular, the SC platforms, such as Didi taxi and Baidu meal-ordering service, play a significant role in people's daily life. A core issue in SC is task assignment, which is to assign real-time tasks to suitable crowd workers. Existing approaches usually are based on infeasible assumptions and have the following two drawbacks:(1) Existing methods often assume to work on the static scenarios, where the spatio-temporal information of all tasks and workers is known before the assignment is conducted. However, since both tasks and workers dynamically appear and request to be allocated in real time, therefore, existing works are impractical in real applications.(2) Existing studies usually assume that there are only two types of objects, tasks and workers, in SC and ignore the influence of workplace for task assignment. To solve the aforementioned challenges, this paper frames a novel dynamic task assignment problem, called online task assignment for three types of objects in spatial crowdsourcing, which not only includes the three types of objects, namely tasks, workers and workplaces, but also focuses on dynamic scenarios. Moreover, a random-threshold-based algorithm is designed for the new problem and a worst-case competitive analysis is provided for the algorithm. Particularly, to further optimize the algorithm, an adaptive threshold algorithm, which is always close to the best possible effectiveness of the random-threshold-based algorithm, is developed. Finally, the effectiveness and efficiency of the proposed methods are verified through extensive experiments on real dataset and synthetic datasets generated by different distributions.
With the rapid development of mobile Internet techniques and Online-to-offline(O2O) business models, various spatial crowdsourcing(SC) platforms become popular. In particular, the SC platforms, such as Didi taxi and Baidu meal-ordering service, play a significant role in people's daily life. A core issue in SC is task assignment, which is to assign real-time tasks to suitable crowd workers. Existing approaches usually are based on infeasible assumptions and have the following two drawbacks:(1) Existing methods often assume to work on the static scenarios, where the spatio-temporal information of all tasks and workers is known before the assignment is conducted. However, since both tasks and workers dynamically appear and request to be allocated in real time, therefore, existing works are impractical in real applications.(2) Existing studies usually assume that there are only two types of objects, tasks and workers, in SC and ignore the influence of workplace for task assignment. To solve the aforementioned challenges, this paper frames a novel dynamic task assignment problem, called online task assignment for three types of objects in spatial crowdsourcing, which not only includes the three types of objects, namely tasks, workers and workplaces, but also focuses on dynamic scenarios. Moreover, a random-threshold-based algorithm is designed for the new problem and a worst-case competitive analysis is provided for the algorithm. Particularly, to further optimize the algorithm, an adaptive threshold algorithm, which is always close to the best possible effectiveness of the random-threshold-based algorithm, is developed. Finally, the effectiveness and efficiency of the proposed methods are verified through extensive experiments on real dataset and synthetic datasets generated by different distributions.
引文
[1]Jeff H.Crowdsourcing:Why the Power of the Crowd is Driving the Future of Business.Crown Business,2009.
[2]Li GL,Wang JN,Zheng YD,Franklin JM.Crowdsourced data management:A survey.ACM Trans.on Knowledge and Data Engineering,2016,28(9):2296-2319.[doi:10.1109/TKDE.2016.2535242]
[3]Feng JH,Li GL,Feng JH.A survey on crowdsourcing.Chinese Journal of Computers,2015,38(9):1713-1726(in Chinese with English abstract).
[4]Chittilappilly AI,Chen L,Amer-Yahia S.A survey of general-purpose crowdsourcing techniques.ACM Trans.on Knowledge and Data Engineering,2016,28(9):2246-2266.[doi:10.1109/TKDE.2016.2555805]
[5]Garcia-Molina H,Joglekar M,Marcus A,Parameswaran AG,Verroios V.Challenges in data crowdsourcing.ACM Trans.on Knowledge and Data Engineering,2016,28(4):901-911.[doi:10.1109/TKDE.2016.2518669]
[6]Chen Z,Fu R,Zhao ZY,Liu Z,Xia LH,Chen L,Cheng P,Cao CC,Tong YX,Zhang CJ.g Mission:A general spatial crowdsourcing platform.In:Jagadish HV,ed.Proc.of the 40th Int’l Conf.on Very Large Data Bases.Hangzhou:ACM Press,2014.1629-1632.
[7]Garey MR,Johnson DS.Computers and Intractability:A Guide to the Theory of NP-Completeness.W.H.Freeman,1979.
[8]Cormen TH,Leiserson CE,Revest RL,Stein C.Introduction to Algorithms.MIT Press,2009.
[9]Burkard RE,Dell’Amico M,Martello S.Assignment Problems.SIAM,2009.
[10]Wong RC,Tao YF,Fu AW,Xiao XK.On efficient spatial matching.In:Koch C,ed.Proc.of the 33rd Int’l Conf.on Very Large Data Bases.University of Vienna:ACM Press,2007.579-590.
[11]U LH,Yiu ML,Mouratidis K,Mamoulis N.Capacity constrained assignment in spatial databases.In:Wang JT,ed.Proc.of the27th Int’l Conf.on Management of Data.Vancouver:ACM Press,2008.15-28.[doi:10.1145/1376616.1376621]
[12]Long C,Wong RC,Yu PS,Jiang MH.On optimal worst-case matching.In:Ross KA,ed.Proc.of the 32nd Int’l Conf.on Management of Data.New York:ACM Press,2013.845-856.[doi:10.1145/2463676.2465321]
[13]U LH,Mouratidis K,Mamoulis N.Continuous spatial assignment of moving users.VLDB Journal,2016,19(2):141-160.[doi:10.1007/s00778-009-0144-3]
[14]Gao J,Guibas LJ,Milosavljevic N,Zhou DP.Distributed resource management and matching in sensor networks.In:Proc.of the8th ACM/IEEE Int’l Conf.on Information Precessing in Sensor Networks.San Francisco:ACM Press,2009.97-108.
[15]Kann V.Maximum bounded 3-dimensional matching is MAX SNP complete.Information Process.Letter,1991,37(1):27-35.[doi:10.1016/0020-0190(91)90246-E]
[16]Papadimitriou C,Yannakakis M.Optimization,approximation,and complexity classes(extended abstract).In:Simon J,ed.Proc.of the 20th Annual Symp.on Theory of Computing.Chicago:ACM Press,1988.229-234.[doi:10.1145/62212.62233]
[17]Hurkens CAJ,Schrijver A.On the size of systems of sets every t of which have an SDR,with an application to the worst-case ratio of heuristics for packing problems.SIAM Journal on Discrete Mathematics,1989,2(1):68-72.[doi:10.1137/0402008·Source:DBLP]
[18]Arkin EM,Hassin R.On local search for weighted k-set packing.Mathematics of Operations Research,1998,23(3):640-648.[doi:10.1287/moor.23.3.640]
[19]Hassan UU,Curry E.A multi-armed bandit approach to online spatial task assignment.In:Proc.of the 11th IEEE Int’l Conf.on Ubiquitous Intelligence and Computing.Bali:IEEE Computer Society,2014.212-219.[doi:10.1109/UIC-ATC-Scal Com.2014.68]
[20]Ting HF,Xiang XZ.Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching.Theoretical Computer Science,2015,607:247-256.[doi:10.1016/j.tcs.2015.05.032]
[21]Tong YX,She JY,Ding BL,Wang LB,Chen L.Online mobile micro-task allocation in spatial crowdsourcing.In:Proc.of the 32nd IEEE Int’l Conf.on Data Engineering.Helsinki:Computer Society,2016.49-60.[doi:10.1109/ICDE.2016.7498228]
[22]Tong YX,She JY,Ding BL,Chen L,Wo TY,Xu K.Online minimum matching in real-time spatial data:Experiments and analysis.In:Proc.of the 42nd Int’l Conf.on Very Large Data Bases.New Delhi:ACM Press,2016.1053-1064.[doi:10.14778/2994509.2994523]
[23]Kazemi L,Shahabi C.Geocrowd:Enabling query answering with spatial crowdsourcing.In:Proc.of the 20th Int’l Conf.on Advances in Geographic Information Systems.Redondo Beach:ACM Press,2012.189-198.[doi:10.1145/2424321.2424346]
[24]Kazemi L,Shahabi C,Chen L.Geotrucrowd:Trustworthy query answering with spatial crowdsourcing.In:Proc.of the 21st Int’l Conf.on Advances in Geographic Information Systems.Orlando:ACM Press,2013.304-313.[doi:10.1145/2525314.2525346]
[25]To H,Shahabi C,Kazemi L.A server-assigned spatial crowdsourcing framework.ACM Trans.on Spatial Algorithms and Systems,2015,1(1):2.[doi:10.1145/2729713]
[26]Cheng P,Lian X,Chen Z,Fu R,Chen L,Han JS,Zhao JZ.Reliable diversity-based spatial crowdsourcing by moving workers.Proc.of the VLDB Endowment,2015,8(10):1022-1033.[doi:10.14778/2794367.2794372]
[27]She JY,Tong YX,Chen L,Cao CC.Conflict-Aware event-participant arrangement and its variant for online setting.ACM Trans.on Knowledge and Data Engineering,2016,28(9):2281-2295.[doi:10.1109/TKDE.2016.2565468]
[28]She JY,Tong YX,Chen L,Cao CC.Conflict-Aware event-participant arrangement.In:Proc.of the 31st Int’l Conf.on Data Engineering.2015.735-746.[doi:10.1109/ICDE.2015.7113329]
[29]Gao DW,Tong YX,She JY,Song TS,Chen L,Xu K.Top-k teams recommendation in spatial crowdsourcing.In:Proc.of the 17th Int’l Conf.on Web-Age Information Management.2016.191-204.[doi:10.1007/978-3-319-39937-9_15]
[30]Deng DX,Shahabi C,Demiryurek U.Maximizing the number of worker’s self-selected tasks in spatial crowdsourcing.In:Proc.of the 21st Int’l Conf.on Advances in Geographic Information Systems.Orlando:ACM Press,2013.314-323.[doi:10.1145/2525314.2525370]
[31]She JY,Tong YX,Chen L.Utility-Aware social event-participant planning.In:Proc.of the 34th ACM SIGMOD Int’l Conf.on Management of Data.2015.1629-1643.[doi:10.1145/2723372.2749446]
[32]Li Y,Liu LM,Xu WJ.Oriented online route recommendation for spatial crowdsourcing task workers.In:Proc.of the 14th Int’l Symp.on Spatial and Temporal Databases.Hong Kong:Springer-Verlag,2015.137-156.[doi:10.1007/978-3-319-22363-6_8]
[33]To H,Ghinita G,Shahabi C.A framework for protecting worker location privacy in spatial crowdsourcing.Proc.of the VLDB Endowment,2014,7(10):919-930.[doi:10.14778/2732951.2732966]
[34]Pournajaf L,Xiong L,Sunderam VS,Xu XF.Spatial task assignment for crowd sensing with cloaked locations.In:Proc.of the15th Int’l Conf.on Mobile Data Management.Brisbane:IEEE Computer Society,2014.73-82.[doi:10.1109/MDM.2014.15]
[35]Littlestone N,Warmuth MK.The weighted majority algorithm.Information and Computation,1994,108(2):212-261.[doi:10.1006/inco.1994.1009]
[36]Freund Y,Schapire R.Game theory,on-line prediction and boosting.In:Proc.of the 9th Annual Conf.Conputational Learning Theory.New York:ACM Press,1996.325-332.[doi:10.1145/238061.238163]
[37]Blum A,Burch C.On-Line learning and the metrical task system problem.Machine Learning,2000,39(1):35-58.[doi:10.1023/A:1007621832648]
[3]冯剑红,李国良,冯建华.众包技术研究综述.计算机学报,2015,38(9):1713-1726.
[2]Li GL,Wang JN,Zheng YD,Franklin JM.Crowdsourced data management:A survey.ACM Trans.on Knowledge and Data Engineering,2016,28(9):2296-2319.[doi:10.1109/TKDE.2016.2535242]
[3]Feng JH,Li GL,Feng JH.A survey on crowdsourcing.Chinese Journal of Computers,2015,38(9):1713-1726(in Chinese with English abstract).
[4]Chittilappilly AI,Chen L,Amer-Yahia S.A survey of general-purpose crowdsourcing techniques.ACM Trans.on Knowledge and Data Engineering,2016,28(9):2246-2266.[doi:10.1109/TKDE.2016.2555805]
[5]Garcia-Molina H,Joglekar M,Marcus A,Parameswaran AG,Verroios V.Challenges in data crowdsourcing.ACM Trans.on Knowledge and Data Engineering,2016,28(4):901-911.[doi:10.1109/TKDE.2016.2518669]
[6]Chen Z,Fu R,Zhao ZY,Liu Z,Xia LH,Chen L,Cheng P,Cao CC,Tong YX,Zhang CJ.g Mission:A general spatial crowdsourcing platform.In:Jagadish HV,ed.Proc.of the 40th Int’l Conf.on Very Large Data Bases.Hangzhou:ACM Press,2014.1629-1632.
[7]Garey MR,Johnson DS.Computers and Intractability:A Guide to the Theory of NP-Completeness.W.H.Freeman,1979.
[8]Cormen TH,Leiserson CE,Revest RL,Stein C.Introduction to Algorithms.MIT Press,2009.
[9]Burkard RE,Dell’Amico M,Martello S.Assignment Problems.SIAM,2009.
[10]Wong RC,Tao YF,Fu AW,Xiao XK.On efficient spatial matching.In:Koch C,ed.Proc.of the 33rd Int’l Conf.on Very Large Data Bases.University of Vienna:ACM Press,2007.579-590.
[11]U LH,Yiu ML,Mouratidis K,Mamoulis N.Capacity constrained assignment in spatial databases.In:Wang JT,ed.Proc.of the27th Int’l Conf.on Management of Data.Vancouver:ACM Press,2008.15-28.[doi:10.1145/1376616.1376621]
[12]Long C,Wong RC,Yu PS,Jiang MH.On optimal worst-case matching.In:Ross KA,ed.Proc.of the 32nd Int’l Conf.on Management of Data.New York:ACM Press,2013.845-856.[doi:10.1145/2463676.2465321]
[13]U LH,Mouratidis K,Mamoulis N.Continuous spatial assignment of moving users.VLDB Journal,2016,19(2):141-160.[doi:10.1007/s00778-009-0144-3]
[14]Gao J,Guibas LJ,Milosavljevic N,Zhou DP.Distributed resource management and matching in sensor networks.In:Proc.of the8th ACM/IEEE Int’l Conf.on Information Precessing in Sensor Networks.San Francisco:ACM Press,2009.97-108.
[15]Kann V.Maximum bounded 3-dimensional matching is MAX SNP complete.Information Process.Letter,1991,37(1):27-35.[doi:10.1016/0020-0190(91)90246-E]
[16]Papadimitriou C,Yannakakis M.Optimization,approximation,and complexity classes(extended abstract).In:Simon J,ed.Proc.of the 20th Annual Symp.on Theory of Computing.Chicago:ACM Press,1988.229-234.[doi:10.1145/62212.62233]
[17]Hurkens CAJ,Schrijver A.On the size of systems of sets every t of which have an SDR,with an application to the worst-case ratio of heuristics for packing problems.SIAM Journal on Discrete Mathematics,1989,2(1):68-72.[doi:10.1137/0402008·Source:DBLP]
[18]Arkin EM,Hassin R.On local search for weighted k-set packing.Mathematics of Operations Research,1998,23(3):640-648.[doi:10.1287/moor.23.3.640]
[19]Hassan UU,Curry E.A multi-armed bandit approach to online spatial task assignment.In:Proc.of the 11th IEEE Int’l Conf.on Ubiquitous Intelligence and Computing.Bali:IEEE Computer Society,2014.212-219.[doi:10.1109/UIC-ATC-Scal Com.2014.68]
[20]Ting HF,Xiang XZ.Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching.Theoretical Computer Science,2015,607:247-256.[doi:10.1016/j.tcs.2015.05.032]
[21]Tong YX,She JY,Ding BL,Wang LB,Chen L.Online mobile micro-task allocation in spatial crowdsourcing.In:Proc.of the 32nd IEEE Int’l Conf.on Data Engineering.Helsinki:Computer Society,2016.49-60.[doi:10.1109/ICDE.2016.7498228]
[22]Tong YX,She JY,Ding BL,Chen L,Wo TY,Xu K.Online minimum matching in real-time spatial data:Experiments and analysis.In:Proc.of the 42nd Int’l Conf.on Very Large Data Bases.New Delhi:ACM Press,2016.1053-1064.[doi:10.14778/2994509.2994523]
[23]Kazemi L,Shahabi C.Geocrowd:Enabling query answering with spatial crowdsourcing.In:Proc.of the 20th Int’l Conf.on Advances in Geographic Information Systems.Redondo Beach:ACM Press,2012.189-198.[doi:10.1145/2424321.2424346]
[24]Kazemi L,Shahabi C,Chen L.Geotrucrowd:Trustworthy query answering with spatial crowdsourcing.In:Proc.of the 21st Int’l Conf.on Advances in Geographic Information Systems.Orlando:ACM Press,2013.304-313.[doi:10.1145/2525314.2525346]
[25]To H,Shahabi C,Kazemi L.A server-assigned spatial crowdsourcing framework.ACM Trans.on Spatial Algorithms and Systems,2015,1(1):2.[doi:10.1145/2729713]
[26]Cheng P,Lian X,Chen Z,Fu R,Chen L,Han JS,Zhao JZ.Reliable diversity-based spatial crowdsourcing by moving workers.Proc.of the VLDB Endowment,2015,8(10):1022-1033.[doi:10.14778/2794367.2794372]
[27]She JY,Tong YX,Chen L,Cao CC.Conflict-Aware event-participant arrangement and its variant for online setting.ACM Trans.on Knowledge and Data Engineering,2016,28(9):2281-2295.[doi:10.1109/TKDE.2016.2565468]
[28]She JY,Tong YX,Chen L,Cao CC.Conflict-Aware event-participant arrangement.In:Proc.of the 31st Int’l Conf.on Data Engineering.2015.735-746.[doi:10.1109/ICDE.2015.7113329]
[29]Gao DW,Tong YX,She JY,Song TS,Chen L,Xu K.Top-k teams recommendation in spatial crowdsourcing.In:Proc.of the 17th Int’l Conf.on Web-Age Information Management.2016.191-204.[doi:10.1007/978-3-319-39937-9_15]
[30]Deng DX,Shahabi C,Demiryurek U.Maximizing the number of worker’s self-selected tasks in spatial crowdsourcing.In:Proc.of the 21st Int’l Conf.on Advances in Geographic Information Systems.Orlando:ACM Press,2013.314-323.[doi:10.1145/2525314.2525370]
[31]She JY,Tong YX,Chen L.Utility-Aware social event-participant planning.In:Proc.of the 34th ACM SIGMOD Int’l Conf.on Management of Data.2015.1629-1643.[doi:10.1145/2723372.2749446]
[32]Li Y,Liu LM,Xu WJ.Oriented online route recommendation for spatial crowdsourcing task workers.In:Proc.of the 14th Int’l Symp.on Spatial and Temporal Databases.Hong Kong:Springer-Verlag,2015.137-156.[doi:10.1007/978-3-319-22363-6_8]
[33]To H,Ghinita G,Shahabi C.A framework for protecting worker location privacy in spatial crowdsourcing.Proc.of the VLDB Endowment,2014,7(10):919-930.[doi:10.14778/2732951.2732966]
[34]Pournajaf L,Xiong L,Sunderam VS,Xu XF.Spatial task assignment for crowd sensing with cloaked locations.In:Proc.of the15th Int’l Conf.on Mobile Data Management.Brisbane:IEEE Computer Society,2014.73-82.[doi:10.1109/MDM.2014.15]
[35]Littlestone N,Warmuth MK.The weighted majority algorithm.Information and Computation,1994,108(2):212-261.[doi:10.1006/inco.1994.1009]
[36]Freund Y,Schapire R.Game theory,on-line prediction and boosting.In:Proc.of the 9th Annual Conf.Conputational Learning Theory.New York:ACM Press,1996.325-332.[doi:10.1145/238061.238163]
[37]Blum A,Burch C.On-Line learning and the metrical task system problem.Machine Learning,2000,39(1):35-58.[doi:10.1023/A:1007621832648]
[3]冯剑红,李国良,冯建华.众包技术研究综述.计算机学报,2015,38(9):1713-1726.