Trichromatic Online Matching in Real-time Spatial Crowdsourcing Tianshu Song 1, Yongxin Tong1, Libin Wang1, Jieying She 2, Bin Yao 3, Lei Chen 2, Ke Xu 1 Beihang University The Hong Kong University of Science and Technology 3 Shanghai Jiao Tong University ∞兆京航宜航天大學 香港科技大學 THE HONG KONG UNIVERSITY OF 上文通大 BEIHANG UNIVERSITY SCIENCE AND TECHNOLOGY , SHANCHAI JIAO TONG UNIVERSITY
Trichromatic Online Matching in Real-time Spatial Crowdsourcing Tianshu Song 1 , Yongxin Tong 1 , Libin Wang 1 , Jieying She 2 , Bin Yao 3 , Lei Chen 2 , Ke Xu 1 1 Beihang University 2 The Hong Kong University of Science and Technology 3 Shanghai Jiao Tong University
Outline o Background and Motivation ● Problem statement ° Our so| utions ● EXperiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 3
Spatial Crowdsourcing Traditional Crowdsourcing V.S. Spatial Crowdsourcing Traditional: Tasks performed in the Internet world Spatial: Tasks are performed in the real world Mission Verde HOA Ssion, A task: queue up for me San Diego Education Association A worker Chiba Japanese Bella posta McGregors Grill 7-Eleve o SD Luggage < Mission Plaza Community Association
⚫ Traditional Crowdsourcing v.s. Spatial Crowdsourcing ⚫ Traditional: Tasks performed in the Internet world ⚫ Spatial: Tasks are performed in the real world Spatial Crowdsourcing A task: queue up for me A worker 6
Spatial Crowdsourcing Applications 可gn FIELD AGENT ick audit of a new con ∪BER Note the price or miik at a loca aZ
Spatial Crowdsourcing Applications 7
Spatial Crowdsourcing Spatial Crowdsourcing Platforms Help assign offline spatial tasks to online crowd workers e.g. Offline-to-Online(020)applications Task allocation/assignment is the most important Task Allocation/Assignment Quality Control Privacy Protection
⚫ Spatial Crowdsourcing Platforms ⚫ Help assign offline spatial tasks to online crowd workers ⚫ e.g. Offline-to-Online (O2O) applications ⚫ Core Challenges ⚫ Task Allocation/Assignment ⚫ Quality Control ⚫ Privacy Protection ⚫ …… Spatial Crowdsourcing Task allocation/assignment is the most important ! 8
Existing Research Static Scenarios: considered as the offline maximum weighted bipartite graph matching problem A crowd worker A spatial task 5 3 Weight: the utility 9 score between a task and a worker 2 Finding a matching to maximize the total utility L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework. In TASA 2015
⚫ Static Scenarios: considered as the offline maximum weighted bipartite graph matching problem. Existing Research L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing. In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework. In TASA 2015. A spatial task A crowd worker 3 5 7 9 2 1 11 6 7 Weight: the utility score between a task and a worker. Finding a matching to maximize the total utility 9
Existing Research Dynamic Scenarios considered as the online maximum weighted bipartite graph matching problem Y Tong et al. Online Mobile Micro-Task Allocation in Spatial Crowdsourcing In ICDE 2016
⚫ Dynamic Scenarios : considered as the online maximum weighted bipartite graph matching problem. Existing Research Y. Tong et al. Online Mobile Micro-Task Allocation in Spatial Crowdsourcing. In ICDE 2016. 10
Offline v.s. Online 5 1 2 2 The offline optimal cost is 20 Offline scenario
Offline v.s. Online Offline Scenario 3 5 7 9 2 1 11 6 7 The offline optimal cost is 20 11
Offline v.s. Online 5 1 2 2 The offline optimal cost is 20 Offline scenario Online Scenario
The offline optimal cost is 20 Offline Scenario Online Scenario 3 5 7 9 2 1 11 6 7 Offline v.s. Online 12
Offline v.s. Online 5 1 1 2 1. Full bipartite graph cannot u be known 2. The new arrival object needs to be immediately assigned based on partial information 2 The offline optimal cost is 20 Offline scenario Online Scenario
Offline Scenario 3 1. Full bipartite graph cannot be known. 2. The new arrival object needs to be immediately assigned based on partial information. 3 5 7 9 2 1 11 6 7 Offline v.s. Online The offline optimal cost is 20 Online Scenario 13