Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2021, Vol. 61 Issue (9): 953-964    DOI: 10.16511/j.cnki.qhdxxb.2020.22.037
  数据库 本期目录 | 过刊浏览 | 高级检索 |
刘俊岭1, 何倩男1, 邹鑫源1, 孙焕良1, 曹科研1, 于戈2
1. 沈阳建筑大学 信息与控制工程学院, 沈阳 110168;
2. 东北大学 计算机科学与工程学院, 沈阳 110000
Spatial keywords task matching algorithm
LIU Junling1, HE Qiannan1, ZOU Xinyuan1, SUN Huanliang1, CAO Keyan1, YU Ge2
1. Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China;
2. School of Computer Science and Engineering, Northeastern University, Shenyang 110000, China
全文: PDF(5583 KB)   HTML
输出: BibTeX | EndNote (RIS)      
摘要 互联网的发展带动了电商等应用的普及,产生了大量具有临时匹配性质的服务。这些服务需要考虑任务的类型与人员具备技能的匹配,同时最小化匹配对象间的路程开销。针对以上实际需求,提出了空间关键字任务匹配问题,给定具有空间位置及关键字的任务集与成员集,在所有任务均可完成的前提下,使所有匹配的任务与成员的距离之和最小。所提出的问题考虑了任务由不同的关键字表示,由于任务和成员数量的海量性及关键字的多样性使得高效求解高质量的匹配结果成为挑战。该文提出了k近邻增量优化策略,引入关键字设计了k近邻空间关键字任务匹配算法,提高了任务匹配质量;提出了基于空间划分的分组优化匹配算法,以适应海量数据的任务匹配情况。针对真实数据集进行了充分测试,验证了算法的有效性。
E-mail Alert
关键词 空间关键字任务匹配空间索引空间数据库    
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 wordsspatial keywords    task matching    spatial index    spatial database
收稿日期: 2020-09-17      出版日期: 2021-08-21
通讯作者: 孙焕良,教授,     E-mail:
刘俊岭, 何倩男, 邹鑫源, 孙焕良, 曹科研, 于戈. 空间关键字任务匹配算法[J]. 清华大学学报(自然科学版), 2021, 61(9): 953-964.
LIU Junling, HE Qiannan, ZOU Xinyuan, SUN Huanliang, CAO Keyan, YU Ge. Spatial keywords task matching algorithm. Journal of Tsinghua University(Science and Technology), 2021, 61(9): 953-964.
链接本文:  或
[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.
No related articles found!
Full text



版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持