Spatial keywords task matching algorithm

LIU Junling; HE Qiannan; ZOU Xinyuan; SUN Huanliang; CAO Keyan; YU Ge

doi:10.16511/j.cnki.qhdxxb.2020.22.037

PDF(5583 KB)

Journal of Tsinghua University(Science and Technology) ›› 2021, Vol. 61 ›› Issue (9) : 953-964. DOI: 10.16511/j.cnki.qhdxxb.2020.22.037

DATABASE

Spatial keywords task matching algorithm

{{article.zuoZhe_EN}}

Author information +

History +

Abstract

The development of the Internet has driven popularization of e-commerce and other applications. For these applications, the Internet needs various services such as temporary matching which matches various types of tasks with the servicer skills while minimizing the distance overhead between matching objects. This paper presents a spatial keywords task matching algorithm for these conditions. Given a task set and a servicer set with spatial locations and keywords, the sum of the distances between all the tasks and the matching servicers is minimized for the premise that all the tasks can be completed. The massive number of tasks and servicers and the wide range of keywords complicate efficient determinations of high quality matching results. This study uses a k-nearest neighbor incremental optimization strategy to improve the matching quality of the traditional matching algorithm. A grouping optimization strategy based on spatial partitioning is then used to improve the matching efficiencies for large datasets. These two strategies are then used to develop a keyword k-nearest neighbor incremental algorithm and a keyword-based grouping optimization algorithm. Tests on real datasets verify the effectiveness of these algorithms.

Key words

spatial keywords / task matching / spatial index / spatial database

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

LIU Junling, HE Qiannan, ZOU Xinyuan, SUN Huanliang, CAO Keyan, YU Ge. Spatial keywords task matching algorithm[J]. Journal of Tsinghua University(Science and Technology). 2021, 61(9): 953-964 https://doi.org/10.16511/j.cnki.qhdxxb.2020.22.037

References

[1] HO C J, VAUGHAN J W. Online task assignment in crowdsourcing markets [C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence. Toronto, Canada, 2012.
[2] YIN X Y, CHEN Y J, LI B C. Task assignment with guaranteed quality for crowdsourcing platforms [C]//2017 IEEE/ACM 25th International Symposium on Quality of Service (IWQoS). Barcelona, Spain, 2017.
[3] WONG R C W, TAO Y F, FU A W C, et al. On efficient spatial matching [C]//Proceedings of the 33rd International Conference on Very Large Data Bases. Vienna, Austria, 2007: 579-590.
[4] POURNAJAF L, XIONG L, SUNDERAM V, et al. Spatial task assignment for crowd sensing with cloaked locations [C]//2014 IEEE 15th International Conference on Mobile Data Management. Brisbane, Australia, 2014.
[5] LAHN N, RAGHVENDRA S. A faster algorithm for minimum-cost bipartite matching in minor-free graphs [C]//Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms. San Diego, USA, 2019: 457-476.
[6] BELESIOTIS A, SKOUTAS D, EFSTATHIADES C, et al. Spatio-textual user matching and clustering based on set similarity joins [J]. The VLDB Journal, 2018, 27(3): 297-320.
[7] CONG G, JENSEN C S, WU D M. Efficient retrieval of the top-k most relevant spatial web objects [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 337-348.
[8] HU H Q, LI G L, BAO Z F, et al. Top-k spatio-textual similarity join [J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(2): 551-565.
[9] HARYANTO A A, ISLAM M S, TANIAR D, et al. IG-Tree: An efficient spatial keyword index for planning best path queries on road networks [J]. World Wide Web, 2019, 22(4): 1359-1399.
[10] CHEN L S, CONG G, JENSEN C S, et al. Spatial keyword query processing: An experimental evaluation [J]. Proceedings of the VLDB Endowment, 2013, 6(3): 217-228.
[11] GALE D, SHAPLEY L S. College admissions and the stability of marriage [J]. The American Mathematical Monthly, 1962, 69(1): 9-15.
[12] KAZEMI L, SHAHABI C. GeoCrowd: Enabling query answering with spatial crowdsourcing [C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, USA, 2012.
[13] CHENG P, LIAN X, CHEN Z, et al. Reliable diversity-based spatial crowdsourcing by moving workers [J]. Proceedings of the VLDB Endowment, 2015, 8(10): 1022-1033.
[14] TONG Y X, ZHOU Z M, ZENG Y X, et al. Spatial crowdsourcing: A survey [J]. The VLDB Journal, 2020, 29(1): 217-250.
[15] DENG D X, SHAHABI C, DEMIRYUREK U. Maximizing the number of worker's self-selected tasks in spatial crowdsourcing [C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Orlando, USA, 2013: 314-323.
[16] TONG Y X, WANG L B, ZHOU Z M, et al. Dynamic pricing in spatial crowdsourcing: A matching-based approach [C]//Proceedings of the 2018 International Conference on Management of Data. Houston, USA, 2018: 773-788.
[17] XIA J F, ZHAO Y, LIU G F, et al. Profit-driven task assignment in spatial crowdsourcing [C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. Macao, China, 2019: 1914-1920.
[18] SHE J Y, TONG Y X, CHEN L, et al. Conflict-aware event-participant arrangement and its variant for online setting [J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(9): 2281-2295.
[19] ZHAO Y, LI Y, WANG Y, et al. Destination-aware task assignment in spatial crowdsourcing [C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. Singapore, 2017: 297-306.
[20] ZHAO Y, XIA J F, LIU G F, et al. Preference-aware task assignment in spatial crowdsourcing [C]//Proceedings of 33rd AAAI Conference on Artificial Intelligence. Palo Alto, USA, 2019.
[21] 范泽军, 沈立炜, 彭鑫, 等. 基于约束的空间众包多阶段任务分配[J]. 计算机学报, 2019, 42(12): 2722-2741. FAN Z J, SHEN L W, PENG X, et al. Multi stage task allocation on constrained spatial crowdsourcing [J]. Chinese Journal of Computers, 2019, 42(12): 2722-2741. (in Chinese)
[22] ZHAO Y, ZHENG K, CUI Y, et al. Predictive task assignment in spatial crowdsourcing: A data-driven approach [C]//2020 IEEE 36th International Conference on Data Engineering (ICDE). Dallas, USA, 2020: 13-24.
[23] WANG Y, ZHANG D X, LIU Q, et al. Towards enhancing the last-mile delivery: An effective crowd-tasking model with scalable solutions [J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 93: 279-293.