SCIENCE CHINA Information Sciences, Volume 64 , Issue 8 : 189101(2021) https://doi.org/10.1007/s11432-019-3061-x

Real-time bottleneck matching in spatial crowdsourcing

More info
  • ReceivedDec 27, 2019
  • AcceptedJul 21, 2020
  • PublishedMay 21, 2021


There is no abstract available for this article.


This work was supported by National Natural Science Foundation of China (Grant No. U11811463).


Appendixes A–E.


[1] Tong Y, Zhou Z, Zeng Y. Spatial crowdsourcing: a survey. VLDB J, 2020, 29: 217-250 CrossRef Google Scholar

[2] Tong Y, She J, Ding B, et al. Online mobile micro-task allocation in spatial crowdsourcing. In: Proceedings of the 32nd IEEE International Conference on Data Engineering, 2016. 49--60. Google Scholar

[3] Li Y, Fang J, Zeng Y. Two-sided online bipartite matching in spatial data: experiments and analysis. Geoinformatica, 2020, 24: 175-198 CrossRef Google Scholar

[4] Tong Y, Zeng Y, Ding B. Two-sided Online Micro-Task Assignment in Spatial Crowdsourcing. IEEE Trans Knowl Data Eng, 2020, : 1-1 CrossRef Google Scholar

[5] Tong Y, She J, Ding B. Online minimum matching in real-time spatial data. Proc VLDB Endow, 2016, 9: 1053-1064 CrossRef Google Scholar

[6] Kalyanasundaram B, Pruhs K. Online Weighted Matching. J Algorithms, 1993, 14: 478-488 CrossRef Google Scholar

[7] Anthony B M, Chung C. Online bottleneck matching. J Comb Optim, 2014, 27: 100-114 CrossRef Google Scholar

[8] Kalyanasundaram B, Pruhs K R. The Online Transportation Problem. SIAM J Discrete Math, 2000, 13: 370-383 CrossRef Google Scholar

[9] Meyerson A, Nanavati A, Poplawski L. Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, 2006. 954--959. Google Scholar


    Algorithm 1 LLDF

    Input $W$, $T$;

    Output A feasible matching $M$;

    (i) Initialization:




    for $p~=~0$ to $|W|-1$

    ${\rm~DenSet}\leftarrow\{\forall~u|u\in~W$ and ${\rm~DenDis}(w_p,u)\leq~\kappa\times~{\rm~AvgDenDis}\}$;


    end for

    (ii) A task $t_i$ arrives:



    ${\rm~Cand}\leftarrow\{\forall~u|u\in~W$ and ${\rm~dis}(t_i,u)\leq\eta\times~{\rm~Avg}_{t_i}\}$;

    $w_x\leftarrow$ the worker in ${\rm~Cand}$ with the minimum ${\rm~density}$;



    return $M$;


Contact and support