空间关键字任务匹配算法  

Spatial keywords task matching algorithm

作　　者：刘俊岭[1] 何倩男 邹鑫源 孙焕良[1] 曹科研 于戈 LIU Junling;HE Qiannan;ZOU Xinyuan;SUN Huanliang;CAO Keyan;YU Ge(Faculty of Information and Control Engineering,Shenyang Jianzhu University,Shenyang 110168,China;School of Computer Science and Engineering,Northeastern University,Shenyang 110000,China)

机构地区：[1]沈阳建筑大学信息与控制工程学院,沈阳110168 [2]东北大学计算机科学与工程学院,沈阳110000

出　　处：《清华大学学报（自然科学版）》2021年第9期953-964,共12页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金项目(61602323,U1811261)。

摘　　要：互联网的发展带动了电商等应用的普及,产生了大量具有临时匹配性质的服务。这些服务需要考虑任务的类型与人员具备技能的匹配,同时最小化匹配对象间的路程开销。针对以上实际需求,提出了空间关键字任务匹配问题,给定具有空间位置及关键字的任务集与成员集,在所有任务均可完成的前提下,使所有匹配的任务与成员的距离之和最小。所提出的问题考虑了任务由不同的关键字表示,由于任务和成员数量的海量性及关键字的多样性使得高效求解高质量的匹配结果成为挑战。该文提出了k近邻增量优化策略,引入关键字设计了k近邻空间关键字任务匹配算法,提高了任务匹配质量;提出了基于空间划分的分组优化匹配算法,以适应海量数据的任务匹配情况。针对真实数据集进行了充分测试,验证了算法的有效性。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.

关 键 词：任务匹配 空间索引 空间数据库 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]