logo

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

Abstract

There is no abstract available for this article.


Acknowledgment

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


Supplement

Appendixes A–E.


References

[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:

    $M~\leftarrow~\emptyset$;

    ${\rm~AvgDenDis}\leftarrow\frac{\sum_{p=0,q=0}^{p=|W|-1,q=|W|-1}{\rm~DenDis}(w_p,w_q)}{|W|^2}$;

    ${\rm~Density}\leftarrow[0,0,\ldots,0]_{|W|}$;

    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}\}$;

    ${\rm~Density}[p]\leftarrow~|{\rm~DenSet}|$;

    end for

    (ii) A task $t_i$ arrives:

    $\pi\leftarrow\{{\rm~dis}(t_i,w_0),{\rm~dis}(t_i,w_1),\ldots,{\rm~dis}(t_i,w_{|W|-1})\}$;

    ${\rm~Avg}_{t_i}\leftarrow~\frac{\sum_{j=0}^{j=k-1}\pi_j}{k}$;

    ${\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}$;

    $M~\leftarrow~(t_i,~w_x)$;

    $W\leftarrow~W-w_x$;

    return $M$;

qqqq

Contact and support