关于高效空间匹配Efficiency Spatial Matching的一些理解

概论

Spatial matching(SPM)，就是假定在任意度量空间中存在两个数据集O和P。O是客户的集合，P是服务提供者的集合，且拥有能够支持客户的最大上限（也就是说P的承载客户服务量有限制）。SPM能够将每一个用户分配至离它最近且还有余力承载客户服务的服务提供者。现在已经开发出了一个通过计算线性数*O(|P|+|O|})*的一个算法来实现SPM。

介绍

双色反向最近邻/bichromatic reverse nearest neighbor,BRNN的特点与不足

bichromatic reverse nearest neighbor,BRNN是一种用于在双色点集中找到在另一色点集中的最近邻的算法。其中一个点集是查询点集，另一个点集是数据点集。BRNN的目标是为查询点集中的每个点找到数据点集中距离最近的点。在空间数据库中已经被广泛研究过。

也就是说，在同一片空间中，给定两个数据集O和P，BRNN查询可以找到距离点p为最近点的所有点o（o、p分别属于数据集O、P），即不存在点p’使得o到p’的距离要短于o到p之间的距离。

打个比方，BRNN的一个最典型的应用就是“寻找最佳服务”。如下图所示，给定数据集O、P，其中分别包含三个住宅地o₁o₂o₃和三个投票地点p₁p₂p₃。

要确定哪些投票点服务哪些住宅区，可以很容易运用BRNN检索法来判断p₁应该服务所有的o_i点，而p₂p₃什么都不用干。因为显然p₁距离这三个住宅区都最近。

然而很遗憾，这样分配并没有考虑到每个服务站都有“投票能力”这个事实。事实上每个服务站都有服务人数上限，参考图中b部分。当p₁服务所有的住宅区时，客户人数将超出服务站的服务人数上限。

显然此时单单应用BRNN技术是不行的，这个时候我们就需要使用到SPM技术。

Spatial Matching技术

SPM可以被视作为进阶版的BRNN技术。对上例应用SPM，可得到分配结果如下：{(p₁,o₁),(p₁,o₂),(p₂,o₃)}。因为p₁满员了，所以用p₂来代替去服务o₃。

要理解SPM技术是如何工作的，可以用以下两种技术进行说明。每一种都很好理解。

closes pair/最近点对算法

即平面最近点问题，要么使用暴力朴素算法枚举所有点对，然后记录最小的点对距离；要么运用分治法从中间开始匹配（匹配前需要对横坐标进行排序）

在刚刚的住宅区和投票池例子中，即针对o_i一个个寻找与他距离最近的p_i。首先是(p₁,o₁)，随后o₁被移出集合O；然后是(p₁,o₂)，再把o₂移出集合O，此时p₁也将被移出集合P（因为p₁达到了服务人数上限）；最后再根据距离最短匹配原则，即(p₂,o₃)。

stable marriage/稳定婚姻算法

稳定婚姻算法是一个很有意思的问题。它假设当前有N位男生和N位女生，开始之前每个男女生都对自己心怡的异性进行排名。男生和女生结婚后，对于每一对男生女生，不会出现比起当前匹配的伴侣互相更喜爱的一对男生女生，即可认为婚姻是稳定的。

这个问题十分的有意思，尤其是结论令人咂舌：传统的求爱，结婚过程是male-optimal的，也就是说，男性能够得到尽可能好的心上人，女性却不然。

在此附上这个问题的链接，有兴趣可以自行阅读。稳定婚姻问题_百度百科 (baidu.com)

话扯远了，那么如何运用稳定婚姻算法来解释SPM的工作机制呢？其实也很简单。

对于o_i和p_i，假定每一个元素都以距离为标准给非同集元素进行降序排序。那么很显然，对于o₁o₂o₃来说，它们的排序表都是{p₁,p₂,p₃}。然而，对于p₁来说，排序是{o₁,o₂,o₃}，p₂p₃则是{o₃,o₂,o₁}，根据这个表，stable marriage能返回一个最稳定的配对并确保没有住宅地和投票池更加偏向于其他组合。当然与经典婚姻匹配不一致的是，这个例子中投票池和住宅地并不是一一对应的关系，即一个投票池可以在不超过承载能力上限的情况下容纳几个住宅地。

基本定义和属性

定义D为一个平面空间，并且满足三角不等式|a,b|+|b,c|>=|a,c|。定义集合P为平面D中的一系列对象，每一个对象代表一个服务端（service-site），再定义一系列对象为O，其中的对象代表客户端（custom-site）。对于每一个客户端o∈O，定义o.w来表示它的人数，也就是客户端的客户数量。同样的p.w代表它的服务容量，代表p所能够服务的最大人数。我们假设有足够的服务设施，即：