, 曹科研1, 于戈21. 沈阳建筑大学 信息与控制工程学院, 沈阳 110168;
2. 东北大学 计算机科学与工程学院, 沈阳 110000
收稿日期：2020-09-17
基金项目：国家自然科学基金项目（61602323，U1811261）
作者简介：刘俊岭(1972-), 女, 副教授
通讯作者：孙焕良, 教授, E-mail: sunhl@sjzu.edu.cn
摘要：互联网的发展带动了电商等应用的普及，产生了大量具有临时匹配性质的服务。这些服务需要考虑任务的类型与人员具备技能的匹配，同时最小化匹配对象间的路程开销。针对以上实际需求，提出了空间关键字任务匹配问题，给定具有空间位置及关键字的任务集与成员集，在所有任务均可完成的前提下，使所有匹配的任务与成员的距离之和最小。所提出的问题考虑了任务由不同的关键字表示，由于任务和成员数量的海量性及关键字的多样性使得高效求解高质量的匹配结果成为挑战。该文提出了k近邻增量优化策略，引入关键字设计了k近邻空间关键字任务匹配算法，提高了任务匹配质量；提出了基于空间划分的分组优化匹配算法，以适应海量数据的任务匹配情况。针对真实数据集进行了充分测试，验证了算法的有效性。
关键词：空间关键字任务匹配空间索引空间数据库
Spatial keywords task matching algorithm
LIU Junling1, HE Qiannan1, ZOU Xinyuan1, SUN Huanliang1
, CAO Keyan1, YU Ge21. Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China;
2. School of Computer Science and Engineering, Northeastern University, Shenyang 110000, China
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 keywordstask matchingspatial indexspatial database
随着互联网的发展，电子商务、微商等应用借助互联网平台得到广泛普及，微商型企业雇佣员工的方式更加灵活，经常由任务驱动临时召集，同时产生了大量的自由职业者，例如装修行业、教育培训机构、专车业务、家政服务、跑腿等[1-2]。这类工作任务需求促生了人力资源中介服务平台，由需求方发布任务需求，工作人员提供服务，如何完成供需双方高效匹配是服务平台的主要任务。
空间任务匹配一般需要同时考虑供需双方的技能与空间距离因素。技能通常以关键字表示，可以为任务需求的技能以及工作人员可以提供的技能；匹配对象间的空间距离为路程花费，在多个任务与多个工作人员同时匹配的情况下，总体距离和越小则路程花费越低。例如，如图 1所示，任务o1, o2为不同住户在同一时间发布的需求，p1, p2, p3为工作人员，关键字a, b, c代表不同的技能。图 1中，空心圆代表任务，叉形代表成员，边代表任务与成员建立匹配关系，下同。任务o1需要技能a，任务o2需要技能b。空间关键字任务匹配结果为 < o1, p2>, < o2, p1>，即o1的a由p2满足，o2的b由p1满足，且匹配总距离为最小。
 |
| 图 1 空间关键字任务匹配实例 |
| 图选项 |
基于以上实际需求，本文提出了空间关键字任务匹配问题。给定具有空间位置及关键字的任务集和成员集(工作人员集合)，任务与成员匹配指在关键字上的匹配，即两者含有相同关键字。考虑任务为同时执行，一个成员中的一个关键字只能与一个任务的关键字匹配。匹配的目标是在所有任务均有匹配的成员前提下，任务与成员间所有匹配对的距离之和最小。
本文提出的空间关键字任务匹配不同于空间任务匹配问题。空间任务匹配并未考虑关键字约束，例如文[3-4]。图 1中如不考虑关键字约束时匹配结果为 < o1, p1>, < o2, p2>，即这两对对象间的距离和最小。当同时考虑多任务与多人员之间空间位置与关键字约束时，此问题为NP难问题，需要设计高效的近似匹配算法。利用现有方法解决此问题，需要将任务集和成员集中满足关键字约束的对象对作为可行匹配，利用可行匹配建立二分图，用空间距离标记边的权重，然后采用最大流匹配算法进行匹配[5]。由于任务集和成员集中对象数据较大，加之关键字具有多样性，因此利用此方法匹配效率较低，难以满足实际应用需求。
文[3]提出了一种启发式的方法解决无关键字的空间任务匹配问题，提出了1-近邻匹配策略，设计了空间任务匹配算法——Chain算法。由于Chain算法只考虑互为1-近邻情况，其搜索空间过小，任务间存在匹配上的冲突，影响了匹配质量。
本文提出k近邻增量优化策略，考虑了多近邻情况，扩展了匹配搜索空间，提高了匹配质量。当任务冲突较多时，要求扩展的k值较大，搜索空间也会扩大，查询效率受到影响。为了提高查询效率，提出了搜索空间范围约束条件，同时设计了基于空间划分的分组优化策略：分别对任务集和成员集进行分组，将同一空间内的任务组与成员组进行匹配，减少了任务冲突，缩减了搜索空间，从而提高匹配效率。基于上述优化策略分别设计了关键字k近邻增量算法和基于关键字的分组优化算法。
本文的贡献如下：1) 提出了空间关键字任务匹配问题，符合空间临时任务与成员匹配的实际需求。2) 提出了k近邻增量优化策略和基于空间划分的分组优化策略，并设计了启发式的近似算法，用于实现空间任务匹配。3) 设计了关键字k近邻增量算法用于解决空间关键字任务匹配问题，设计了基于关键字的分组优化算法缩减搜索空间，提高了算法匹配效率。4) 利用真实数据集对所提算法与现有算法在时间性能、匹配质量等方面进行充分测试，验证了所提算法的有效性。
1 相关工作用户使用搜索引擎对空间对象查询的需求逐渐增加，特别是将空间对象的属性信息与空间位置结合产生的空间关键字查询。在线地图搜索引擎，如谷歌地图、百度地图，逐渐增加了结合空间位置与关键字结构的查询服务。典型的空间查询包括：kNN查询(k nearest neighbor, kNN)、范围查询、空间关键字查询等[6-10]。空间关键字查询实现技术通常利用文本-空间索引，如IR-tree[7]。
任务匹配问题是将两类对象按照优先顺序进行匹配，使最终结果最优。最大流问题是经典任务匹配问题，可以采用最大流的标号算法解决。算法从一个可行流开始，不断寻找增广链得到更大的流，直到不存在该流的可增广链时得到最大流[11]。本文将此算法进行扩展，设计了基于最大流的空间关键字任务匹配算法作为比较算法。
空间任务匹配问题指将空间的两类对象，如任务与成员对象，按距离进行匹配，使匹配后的总距离最小。文[3]提出了Chain算法来求解空间任务匹配问题的近似最优解，其主要思想是将互为最近邻的一对任务与成员作为分配结果直至所有的任务都有对应的成员。Chain算法是基于R-Tree索引的近似匹配算法。文[4]考虑了用户隐私问题，解决不确定位置下的空间任务匹配。
空间众包问题为了实现空间相关的任务指派，可以分为服务指派任务、工人选择任务两大类[12-14]。空间众包指派目标包括可靠性与多样性[13]、最大化工人数量[15]、价格最优[16-17]、偏好约束[18-21]、预测指派[22]等。空间众包问题的研究重点是在线环境下的实时任务分配，而本文的研究重点是海量空间对象与多关键字的匹配，提供的是基于空间索引的解决方案。
本文结合关键字查询与空间任务匹配，提出了空间关键字任务匹配问题。针对任务匹配过程中的冲突，提出了k近邻增量优化及分组优化策略，提高了匹配效率与匹配质量。
2 问题定义给定一个空间区域内的任务集O和成员集P，任务oi∈O和成员pi∈P由一个三元组 < id, loc, items>表示。其中：id为标识代表对象在所属集合中的编号；loc为空间位置，由经纬度表示；items为关键字集合，表示为 < item1, item2, …, itemi>，不同对象的items中关键字的个数不同。
定义1 ??关键字匹配。给定任务o及成员p，两者有相同的关键字item，即o.item=p.item，则成员p与任务o在关键字item上可以建立匹配关系，表示为 < o, p>item。
定义2??任务匹配。给定任务o，存在一个P的子集Po，Po中的任一对象只与o的一个关键字建立匹配关系，则Po与任务o建立了任务匹配关系，表示为 < o, Po>。
在定义2中，任务o的每个关键字itemi都需要有一个包含该关键字的成员与之匹配，即o中关键字的个数等于子集Po中成员的个数。
定义3?? 任务集匹配。给定任务集O，O中的每一个任务均有相应的成员子集匹配，并且任意两个子集满足Pi∩Pj=，表示为R={ < o1, P1>, < o2, P2>, …, < on, Pn>}。
本文解决的空间关键字任务匹配问题中假定一个任务集中的所有任务同时执行，因此一个成员只能匹配一个任务，由定义3的条件Pi∩Pj= ?约束。任务集匹配成功的标志是所有o∈O中每个关键字都有不重复匹配的成员与该任务o匹配。
定义4?? 任务集匹配代价。给定任务集O={o1, o2, …, on}，成员集P={p1, p2, …, pn}，任务集匹配R={ < o1, P1>, < o2, P2>, …, < on, Pn>}，任务集匹配代价的定义为匹配关键字对之间空间距离的总和，即
| $ D(R) = \sum\limits_{i = 1}^n {\sum\limits_{{p_j} \in {P_i}} d } \left( {{o_i},{p_j}} \right). $ | (1) |
定义5?? 空间关键字任务匹配问题。给定任务集O和成员集P，找到任务集O的一个匹配集R使得R的匹配代价最小。
图 2为匹配示例。图中：任务集O={o1, o2, o3}，成员集P={p1, p2, p3, p4, p5, p6, p7}，关键字集为{a, b, c, d, e}。o3与p1是关于关键字e的匹配。与任务o1匹配的成员子集P1={p2, p3, p4}。整个任务集O的匹配集R={ < o1, P1>, < o2, P2>, < o3, P3>}，其中P2={p5, p6}，P3={p1, p7}。
 |
| 图 2 任务与成员匹配实例 |
| 图选项 |
假设任务数为n，成员数为m，且m>n。寻找最优匹配解需要将n个任务中的每个任务与m个成员进行一次比较，其代价为Amn。现设每个任务有c个关键字，由于每个任务的每个关键字都需要有对应的成员进行匹配，因此m>nc，代价为Amnc，取极限为Ancnc=(nc)!。由此可知，该问题是NP难问题。
3 空间任务匹配算法由于空间关键字任务匹配是一个NP难问题，需要设计近似算法解决此问题。文[3]提出了互为1-近邻对的匹配方法解决无关键字的空间任务匹配问题，且未考虑其他近邻点对结果的影响。本文提出k近邻增量优化策略以及分组优化策略，并在此基础上设计了空间关键字任务匹配算法。
3.1 匹配优化策略3.1.1 k近邻增量优化策略文[3]提出了1-近邻匹配策略，如图 3所示。o1, o2的最近邻对象均为p1，使用1-近邻算法匹配，p1与o2互为最近邻，将p1与o2匹配，最终结果为{ < o2, p1>, < o1, p2>}，如图 3a所示。然而，匹配结果{ < o1, p1>, < o2, p2>}更优，其匹配总距离更小，如图 3b所示。1-近邻方法优先匹配最近邻对，没有考虑多近邻情况，影响了匹配质量。当一个成员为多个任务的k最近邻时，需要选择任务与之匹配，称这些任务是冲突的，如定义6所示。
 |
| 图 3 1-近邻匹配[3] |
| 图选项 |
定义6?? 任务冲突。假设任务o1, o2, …, on中每个任务的kNN成员均为p0, k={1, 2, …, n}，那么任务o1, o2, …, on冲突，称p0为冲突成员。
当有任务冲突时，如果采用图 3a所示的1-近邻匹配，得到的结果差于将o1与1-近邻p1匹配、o2与2-近邻p2匹配的情况。因此，本文提出k近邻距离增量的概念，简称k近邻增量，如定义7所示。计算o1, o2的2-近邻成员p2较1-近邻成员p1的距离增量作为其2-近邻成员的匹配增量。将1-近邻成员与匹配增量大的任务匹配，即o1与p1匹配，将o2与最近且未被匹配的成员进行匹配，所得结果更优。
定义7??k近邻增量。设任务oi∈O有当前最近邻成员pa和kNN成员pb，oi在匹配过程中需要断开当前与pa的匹配关系，并与新成员pb建立匹配关系，则k近邻成员的匹配增量为
| $I_{(a, b)}^{i}=d\left(o_{i}, p_{b}\right)-d\left(o_{i}, p_{a}\right) . $ | (2) |
 |
| 图 4 k近邻增量 |
| 图选项 |
利用k近邻增量匹配，可以得出如下3个结论：
定理1??假设任务o1, o2, …, on的1NN成员分别为p1, p2, …, pn，当任意两个成员pi≠pj, 则每一个任务oi都与其最近邻成员pi匹配，此匹配为最优匹配。
定理1说明了所有任务在1NN匹配不冲突下的情况，显然为最优匹配。查询1NN成员时，若存在部分任务冲突情况，则将1NN不冲突的任务与其1NN成员匹配，1NN冲突任务的匹配方式由定理2说明。
定理2??假设任务o1, o2, …, on的1NN成员均为p0，若任意两个任务的2NN成员不相同，则1NN冲突成员p0与冲突任务中2NN匹配增量最大的任务oi匹配，其余任务与当前最近且未被匹配的成员进行匹配，此匹配为最优匹配。
证明：??初始时任务o1, o2, …, on都与其最近邻成员p0匹配，此时所有任务的匹配总距离最小，设为x0。计算各任务2NN成员的匹配增量I(0, 1)1, I(0, 2)2, …, I(0, n)n，显然对于每个任务oi∈{o1, o2, …, on}以及2NN成员pi∈{p1, p2, …, pn}，不存在新成员pm使匹配增量I(0, m)m>I(0, i)i，即当前匹配增量是每个任务的最小匹配增量。1NN成员p0只能与任务o1, o2, …, on中的一个任务匹配，显然应该将p0匹配给增量最大的任务，使得匹配总距离最小。
定理2说明了当1NN有冲突、2NN无冲突时最优匹配结果的情况。图 5a中任务o1，o2，o3的最近邻都为p1，任务冲突，各任务的2NN成员分别为p3，p2，p4，此时成员互不相同，计算各自的匹配增量I(1, 3)1，I(1, 2)2，I(1, 4)3，比较发现I(1, 3)1最大，则将p1与任务o1匹配，o2，o3分别与各自的2NN成员p2，p4匹配，此时成员无重复匹配，且匹配总距离最小，如图 5b所示。
 |
| 图 5 1NN冲突、2NN不冲突时匹配 |
| 图选项 |
因此，可以得出一个结论：当扩展任务的近邻成员至无冲突时，一定会有最优解。如果不扩展到无冲突情况，则难以保证有最优解，近邻数越少搜索空间越小，其匹配质量也会下降，如定理3所示。
定理3?? 当任务集O={o1, o2, …, on}中存在最近邻冲突成员p0，任务的次近邻分别为p1, p2, …, pn，当d(o1, p0)>d(o2, p0)>…>d(on, p0)且I(0, 1)1>I(0, 2)2>…>I(0, n)n时，采用2-近邻匹配的结果优于1-近邻匹配。
证明：? 采用1-近邻匹配时，由于d(o1, p0)>d(o2, p0)>…>d(on, p0)，可得on与p0互为最近邻，因此任务集匹配结果R1={ < o1, p1>, < o2, p2>, …, < on-1, pn-1>, < on, p0>}，任务集匹配总距离D(R1)=d(on, p0)+ d(o1, p0)+I(0, 1)1+d(o2, p0)+I(0, 2)2+…+d(on-1, p0)+I(0, n-1)n-1；采用2-近邻匹配时，由I(0, 1)1>I(0, 2)2>…>I(0, n)n可得p0与任务o1匹配，因此任务集匹配结果R2={ < o1, p0>, < o2, p2>, …, < on, pn>}，任务集匹配总距离D(R2)= d(o1, p0)+d(o2, p0)+I(0, 2)2+…+d(on, p0)+I(0, n)n。比较两者可知，由于I(0, 1)1>I(0, n)n，因此D(R1)>D(R2)，2-近邻匹配的总距离更小，定理3成立。
由定理3可知，即使当2-近邻不满足最优匹配条件时，其近似匹配结果也优于1-近邻匹配结果，因为2-近邻的匹配空间大于1-近邻匹配空间。可以推导出类似的结论，即3-近邻匹配结果优于2-近邻匹配结果，k近邻匹配结果优于k-1近邻匹配结果。
3.1.2 基于空间划分的分组优化策略k近邻距离增量优化策略每次将冲突成员与其k近邻最大匹配增量的任务进行匹配，冲突的任务越多，冲突的级别越高，存在需要寻找的k近邻就越多，大量任务的k近邻查询会影响算法执行效率。
因此，本文提出了基于空间划分的分组优化策略，对任务集与成员按空间进行分组后再匹配。该策略的基本思想为：将搜索空间等分为多个矩形区域，统计各区域空间内任务与成员的数量，若成员数量≥任务数量，则该空间内的任务与成员可以利用k近邻增量优化策略进行匹配。对于成员数量 < 任务数量的空间，则向四周扩展该空间，将周围未被匹配的成员添加到空间内，直到该空间满足匹配条件，再对组内进行匹配。由于本文针对的场景为整体成员数量≥整体任务数量情况，因此通过向外扩展空间一定可以使成员数量≥任务数量。通常情况下，任务集与成员集分布存在一致性，即任务分布密集，成员也会分布密集，而且采用向外扩展空间的方式可以处理分布不一致问题。基于空间划分的分组优化策略由于大多数任务与成员可以在组内完成匹配，缩减了匹配空间，提高了匹配效率。由于分组优化在分组空间内匹配，在边界部分匹配可能不是最优解。
图 6给出了一个分组优化实例。图 6a的空间被划分为4个区域，对每个区域的任务集O和成员集P分组，得到任务组O1={o1, o2}, O2={o3, o4, o5}, O3={o6, o7, o8}, O4={o9, o10, o11}，成员组P1={p1, p2}, P2={p3, p4, p5, p6, p7}, P3={p8, p9, p10, p11}, P4={p12, p13}。计算相应空间的任务和成员数量，并进行匹配，如图 6b所示。此时，最后一个空间的成员数量 < 任务数量，因此需要对空间进行扩展，如图 6c所示。扩展空间后满足匹配条件，可以对空间内的任务与成员再进行匹配，如图 6d所示。
 |
| 图 6 分组优化实例 |
| 图选项 |
3.2 空间关键字任务匹配算法空间关键字任务匹配问题中每个任务和成员都至少包含一个关键字。本节首先提出无关键字的k近邻增量匹配(k nearest neighbor match, kNNmatch)算法，再考虑关键字匹配情况，设计了关键字k近邻增量匹配(search keywords by k nearest neighbor match, SK-kNNmatch)算法，同时使用分组优化策略，提高执行效率。
3.2.1 k近邻增量匹配算法当扩展任务的近邻成员至无冲突时，可以找到最优解，但搜索范围过大，本文提出一个保证2-近似率的匹配算法，算法的搜索空间范围定义为：假设任务o1, o2, …, on的kNN成员存在冲突，k={1, 2, …, n}，若成员数量>任务数量(冲突成员仅记一次)，则结束搜索。其中，1NN冲突成员pi与冲突任务组中kNN匹配增量最大的任务oi匹配，其他任务则与各自的下一近邻建立新的匹配关系。
图 7给出了k近邻增量优化算法过程，任务集为O={o1, o2, …, on}，成员集存储在IR-tree中，包含成员对象的位置信息与关键字信息。初始化近邻k=1，成员子集Pm为空。
 |
| 图 7 1NN冲突、2NN不冲突时匹配 |
| 图选项 |
算法的执行过程为：从1NN开始，调用图 8和9所示的算法将不冲突的任务与成员进行匹配(图 7第2-3行)，若存在多个任务匹配同一个成员pi，导致成员集的成员数量<任务集的任务数量，任务集不能被完全匹配，则循环调用图 8算法来查询k近邻的成员，直到成员集的成员数量>任务集的任务数量(图 7第4-7行)。当某一个任务k近邻与其他任务不冲突，则直接指派此成员(图 7第7行)，将剩余的任务与成员按下面的匹配算法匹配(图 7第8-13行)：计算并比较冲突任务k近邻的匹配增量，不断将最近邻冲突成员与最大匹配增量的任务匹配，并从相应的任务集与成员集中删除，其他任务则与各自对应的下一近邻建立新的近邻关系。重复上述步骤直到没有多余的任务可匹配，则返回最终结果。由k近邻增量优化策略可知，1NN不冲突情况的匹配由图 7第3行执行，1NN冲突时执行图 7第5-7行，kNN冲突情况由图 7第5行的任务与成员数量的比较来判断，图 7第8-12行利用定义7的匹配增量进行匹配，且结果可靠性由定理4保证。
 |
| 图 8 Search_kNN算法 |
| 图选项 |
 |
| 图 9 NonConflict_match算法 |
| 图选项 |
定理4?? k近邻增量优化算法可以保证2-近似率。
证明：?? 本文定义的搜索空间范围中的kNN冲突分为以下3种情况：
1) k=n，显然结果包含最优解。
2) k < n，存在某一任务o的k近邻与其他任务不冲突。此时最优结果为Dn，使用k近邻增量优化得到的结果为
3) k < n，存在多个任务的k近邻与其他任务不冲突。此时最优结果为Dn，使用k近邻增量优化得到的结果为
给定n个任务与m个成员，且m>n。kNNmatch算法查询n个任务的k近邻代价为nk，从第k次依次向前进行匹配，代价为n+(n-1)+…+(n-k+1)，最后对剩余任务查询成员代价为n-k，则算法总代价为n(2k+1)-0.5 k(k+1)，可表示为O(kn)。
3.2.2 关键字k近邻增量匹配算法关键字k近邻增量算法SK-kNNmatch将k近邻增量算法拓展到空间关键字任务匹配问题。SK-kNNmatch算法将最小化增量的思想应用到任务的关键字上，即当任务本身含有的不同关键字与成员匹配存在冲突时，解决任务与成员选择相应匹配关键字的问题。
图 10描述了SK-kNNmatch算法解决同一任务时不同关键字匹配同一成员的情况。图 10a中任务o1分别以关键字a, b与p1建立了匹配关系，即 < o1, p1>a，< o1, p1>b，此时o1{a}、o1{b}冲突，p1是冲突成员。继续查询分别包含任务o1关键字a、b的下一近邻，得到p2{a}、p3{b}，计算各自的增量I(1, 2)a1、I(1, 3)b1，显然I(1, 2)a1<I(1, 3)b1，则将b作为成员p1与任务o1的匹配关键字，最终的匹配结果为 < o1, p1>b，< o1, p2>a，如图 10b所示。
 |
| 图 10 关键字匹配实例 |
| 图选项 |
同一任务的关键字的顺序代表该关键字优先级，顺序在前面的关键字优先匹配。因此，在增量相等的情况下，同一任务所包含关键字的顺序代表与它距离短的成员优先匹配的顺序。假设图 7a中p2的关键字为p2{a, b}，由于o1的关键字a在前，因此a被优先匹配，最终的匹配结果为 < o1, p1>a，< o1, p2>b。
图 11详细描述了SK-kNNmatch算法的过程。由于存在同一任务含有多个关键字的情况，因此初始化每个任务oi的匹配成员子集Pi(第1行)，算法通过调用图 12算法查找包含任务关键字且距离该任务的k近邻的成员，调用图 13算法将不冲突的任务关键字与含有该关键字的成员进行匹配。在匹配更新时，需要同时更新任务关键字(第11-12行)，当任务内的关键字都有成员匹配时，将对应的任务匹配集添加到总匹配集内(第13-14行)。
 |
| 图 11 关键字k近邻增量匹配算法SK-kNNmatch |
| 图选项 |
 |
| 图 12 Search_itemkNN算法 |
| 图选项 |
 |
| 图 13 NonConflict_itemmatch算法 |
| 图选项 |
SK-kNNmatch算法的动态匹配过程与k近邻增量匹配算法的过程相似(图 11第2-15行)，需要考虑关键字，因此在查找k近邻成员时，图 12算法(图 11第2-4行)相对图 8算法(第2-3行)增加了相应关键字的查找。图 13算法(第3-6行)是对图 9算法(第3-4行)1-近邻不冲突匹配情况的扩展，图 11算法(第9-14行)是对图 7算法(第9-12行)k近邻匹配情况的扩展。
SK-kNNmatch算法在kNNmatch算法的基础上加入关键字匹配，由于任务中每一个关键字需匹配一个成员，因此任务的数量扩展为nc，其余计算方法与kNNmatch算法相同，因此总代价为nc(2k+1)-0.5 k(k+1)，可表示为O(ckn)。
3.2.3 基于关键字的分组优化算法基于关键字的分组优化算法(search keywords by grouping k nearest neighbor match, SK-GkNNmatch)在关键字k近邻增量算法SK-kNNmatch的基础上分组优化。该算法利用基于空间划分的分组优化策略进行空间分组，考虑关键字的影响，即空间匹配条件为：对于空间内含有某一关键字的任务数量，都存在多于这一数量且含有该关键字的成员，则进行组内匹配。组内对象利用SK-kNNmatch算法进行匹配，不满足条件的空间则需要扩展范围来保证匹配可行。
图 14描述了SK-GkNNmatch算法的过程。首先进行空间划分(第1行)，对空间内的任务成员组执行匹配(第2-6行)，组内细节匹配调用图 7所示的关键字k近邻增量算法(第6行)，对不满足匹配条件的空间进行扩展，直到满足条件再进行组内匹配(第7-9行)。
 |
| 图 14 基于关键字的分组优化算法 |
| 图选项 |
SK-GkNNmatch算法在复杂度上与SK-kNNmatch算法相同, 但它通过任务集与成员集分组，优先匹配成员充足的组，减少了冲突出现的可能性，提高了匹配效率。
4 实验分析本节将对所提出的空间关键字任务匹配算法进行实验比较。比较的基准算法有两种：1) 采用文[23]使用的最大流算法。该算法针对每个关键字，查询所有任务的kNN成员，建立二分图，然后采用最大流算法进行匹配，对于单关键字与多关键字的匹配算法分别命名为Bipartite与SK-Bipartite (search keywords on Bipartite, SK-Bipartite)。2) 将文[3]中提出的Chain算法进行扩展以解决关键字匹配问题，其思想是每次寻找包含同一关键字的一对互为最近邻对作为匹配结果，直到所有任务内每个关键字都有唯一的成员与其匹配。对于单关键字与多关键字匹配算法分别命名为Chain、SK-Chain。kNNmatch和GkNNmatch为本文所提出的基于k-近邻及分组优化的算法，考虑了关键字设计了SK-kNNmatch和SK-GkNNmatch算法。
4.1 数据集实验中分别进行空间匹配与空间关键字匹配，其中空间匹配数据集采用真实地图信息点(point of information, POI)数据以及合成数据。空间关键字匹配数据集为从“58同城”网站抓取的北京、沈阳餐馆的地址与菜单、招聘数据。
4.1.1 空间匹配数据集真实数据集是从网站http://www.rtreeportalorg/spatial.html. 下载获得，数据集来自加利福尼亚、长滩、希腊、德国，分别命名为CA(62 556)、LB(53 145)、GR(23 628)和GM(36 334)。由于空间任务匹配问题包含两部分数据集，分别是任务数据集O以及成员数据集P，因此本文利用标准化后的真实数据集自由组合产生了4个数据集，分别命名为CA-GR，LB-GR，CA-GM和LB-GM，分别代表(P，O)=(CA，GR)，(P，O)=(LB，GR)，(P，O)=(CA，GM)和(P，O)=(LB，GM)。
合成数据集满足以下条件：任务集数据符合Zipf分布，成员集数据符合Gauss分布。数据集中每个POI点有两个维度，每一维的坐标空间都标准化为[0, 10 000]。为了比较不同数据量下各个算法的性能，本文主要生成了两组数据集，如表 1所示。
表 1 空间匹配合成数据集
| 数据集 | 维度数量 | 任务集数据条数 | 成员集数据条数 |
| 数据集1 | 2 | 5 000 | 50 000 |
| 数据集2 | 2 | 10 000 | 100 000 |
表选项
4.1.2 空间关键字匹配数据集合成的任务集数据5 000条，成员集数据50 000条，关键字10类，每个任务的关键字个数范围[2, 5]，每位成员的关键字个数范围[1, 3]，如表 2所示。合成数据有两个维度，每一维的空间范围在[0, 10 000]内，成员集数据符合Gauss分布，任务集数据符合Zipf分布。
表 2 空间关键字匹配合成数据集
| 集合类型 | 数据条数 | 关键词个数 | 维度数量 |
| 任务集O | 5 000 | 2~5 | 2 |
| 成员集P | 50 000 | 1~3 | 2 |
表选项
真实数据集包括两部分：北京的简历数据29 364条以及招聘数据4 392条，沈阳的简历数据11 763条和招聘数据1 809条。关键字种类共有7类，包括：服务员、厨师、后厨、学徒、配菜、收银和餐饮管理。爬取到的数据集中招聘数据都有具体的位置，然后通过百度地图API批量Input地址获取到相应的经纬度，而简历数据中有一部分的居住地址没有细化到街道，无法直接用地图API获取到具体的坐标，对于这类数据首先人工获取各个区域的中心经纬度，经度上下浮动[-0.05°, 0.05°](对应实际距离4.14 km)，纬度上下浮动[-0.03°, 0.03°](对应实际距离3.33 km)。
4.2 空间匹配算法性能分析在算法的性能分析方面，比较了不同数据集下算法的运行时间、匹配质量、top-k查询次数。
图 15a—15c给出了Bipartite、Chain、kNNmatch和GkNNmatch算法随着任务数量的增长各自的运行时间、匹配质量及top-k查询次数的变化。在本次比较中，成员数量保持不变，为10 000条，任务数量从1 000逐渐增长到5 000。图 15a展示了任务数量对3种算法效率的影响。可以看出，Bipartite算法比另外3种算法运行时间更长，kNNmatch算法次之。图 15b给出了任务数量对算法匹配质量的影响。可以看出，kNNmatch与Bipartite算法明显优于另外两种算法。本实验验证了定理3的结论，利用k近邻查询方式可以提高匹配质量。当k相同时，kNNmatch与Bipartite可以取得相同的匹配质量。图 15c给出了任务数量对R-Tree查询次数的影响。随着任务数量的增多，Bipartite算法访问R-Tree次数多于另外3种算法。
 |
| 图 15 (网络版彩图)空间匹配算法性能比较 |
| 图选项 |
图 16展示了4组真实数据集下各算法的性能比较。可以看出，Bipartite与kNNmatch具有最好的匹配质量，Chain算法的匹配质量最差，Bipartite算法的匹配效率最低。
 |
| 图 16 (网络版彩图)真实数据集中空间匹配各算法性能比较 |
| 图选项 |
kNNmatch算法查询了k近邻的局部距离对总距离的影响，因此相较于Chain算法，在匹配质量上有明显提升，但由于对大量k近邻点进行查询，导致算法效率降低。GkNNmatch算法将集合分成多个小集合，减少了冲突。该算法相比于kNNmatch算法虽然降低了匹配质量，但是提升了算法的运行效率。
综上所述，GkNNmatch算法在处理供多需少的空间关键字任务匹配问题时，在时间和匹配质量上都有较高的性能。
4.3 空间关键字匹配算法性能分析在算法的性能分析方面，比较了不同匹配策略情况下SK-kNNmatch算法的运行时间、匹配质量，然后比较了混合关键字匹配策略下算法的性能。
顺序匹配(ordering match, ORM)是指匹配算法根据关键字自然顺序进行依次匹配，即所有任务按关键字独立运行空间任务匹配算法；最少关键字优先匹配(sequential frequency match, RFM)则每次挑选成员集中频数最低的关键字进行匹配；混合关键字匹配(synthetical keyword match, SKM)同时考虑不同任务与成员匹配的影响以及同一任务不同关键字与成员匹配的影响。
图 17比较了不同匹配策略下SK-kNNmatch算法的运行时间以及匹配质量。匹配的任务数量从1 000逐渐增加至5 000，成员数量固定为50 000。图 17a给出了任务数量的增加对3种匹配策略运行时间的影响。可以看出，3种匹配策略对应的运行时间都呈线性增长，但混合匹配策略SKM相较另外两种策略运行时间更长且运行时间增长的趋势更快。图 17b给出了任务数量对不同策略的匹配质量的影响。可以看出，混合关键字匹配策略明显优于另外两种匹配策略。此外，随着任务数量的增长，最少关键字优先匹配策略与混合关键字匹配策略的差异在逐渐缩小。
 |
| 图 17 (网络版彩图)不同匹配策略性能比较 |
| 图选项 |
图 18给出了混合关键字匹配策略下不同空间关键字匹配算法的性能比较。本次比较使用的是合成数据集，任务数量从1 000增长到5 000，成员数量固定为50 000。图 18a为任务数量对各算法的运行时间的影响。可以看出，SK-Chain和SK-GkNNmatch算法在时间上几乎相同，都呈线性增长趋势，SK-Bipartite算法由于需要对每个任务执行kNN查询构建二分图，导致其查询效率最低。图 18b为各算法的匹配质量比较。可以看出，SK-kNNmatch和SK-Bipartite算法具有最高的匹配质量，SK-GkNNmatch算法匹配质量优于SK-Chain算法。
 |
| 图 18 (网络版彩图)合成数据集中空间关键字匹配算法性能比较 |
| 图选项 |
图 19展示了北京和沈阳数据集下各算法的性能比较。可以看出，SK-kNNmatch算法减少了匹配总距离，提升了匹配质量；SK-GkNNmatch算法运行时间与SK-Chain算法的运行时间基本相同，SK-Bipartite算法的运行时间最长。
 |
| 图 19 (网络版彩图)真实数据集中各空间关键字匹配算法性能比较 |
| 图选项 |
针对空间任务匹配问题，比较了4种算法的性能：与Chain算法相比，本文提出的kNNmatch和GkNNmatch算法有效地提升了匹配质量，其中GkNNmatch算法的运行效率与Chain算法基本接近。针对空间关键字匹配问题，通过对比可以发现：混合关键字匹配策略的性能最优；4种算法中SK-kNNmatch算法和SK-Bipartite算法的匹配质量优于其他2种算法；SK-Chain算法和SK-GkNNmatch算法的运行效率较快。综合来看，SK-GkNNmatch算法的整体性能较优。
5 结论本文首先提出了空间关键字任务匹配问题。与传统的空间任务匹配问题不同，所提出的空间关键字任务匹配是同时考虑空间位置和关键字信息的多任务与多成员的全局匹配，在保证所有任务均有匹配成员的前提下，使任务与成员间所有匹配对的距离之和最小。在空间任务匹配方面，本文提出了k近邻增量优化策略和基于空间划分的分组优化策略，同时设计了相关算法。在空间关键字任务匹配方面，本文提出了关键字k近邻增量匹配算法SK-kNNmatch，同时为了提高运行效率，提出了基于关键字的分组优化算法SK-GkNNmatch，将大任务空间分解成多个小任务空间，减少冲突，从而减少了匹配迭代次数。针对真实数据集进行了充分测试，验证了所提出的分组优化算法的匹配质量优于现有的Chain算法，同时保证了查询效率。
参考文献
| [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. DOI:10.1007/s00778-018-0498-5 |
| [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. DOI:10.14778/1687627.1687666 |
| [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. DOI:10.1109/TKDE.2015.2485213 |
| [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. DOI:10.1007/s11280-018-0643-5 |
| [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. DOI:10.14778/2535569.2448955 |
| [11] | GALE D, SHAPLEY L S. College admissions and the stability of marriage[J]. The American Mathematical Monthly, 1962, 69(1): 9-15. DOI:10.1080/00029890.1962.11989827 |
| [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. DOI:10.14778/2794367.2794372 |
| [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. DOI:10.1007/s00778-019-00568-7 |
| [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. DOI:10.1109/TKDE.2016.2565468 |
| [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. DOI:10.1016/j.tre.2016.06.002 |
