论文概述
论文题目：k-NearestNeighbors on Road Networks: A Journey in Experimentation and In-MemoryImplementation
一、主要内容
K Nearest Neighbor算法又叫KNN算法，这个算法是机器学习中的一个经典的算法。早先的研究中，KNN算法的实现都是基于磁盘的，很少有人研究KNN算法在内存上的实现效率。当前国家最前沿的技术很多都是基于内存的，所以该论文研究了五种经典KNN算法在内存上的实现效率，并且针对多组现实生活中的真实数据对不同KNN算法的时间和空间效率进行了详细的理论分析和可靠的实验验证。值得一提的是，论文作者通过对经典的Incremental Euclidean Restriction (IER)算法进行了简单改进并取到了意想不到的效果，经实验验证，其改进算法在实践中具有良好的时间效率和空间效率。
目前关于KNN问题的高效算法主要有IncrementalNetwork Expansion (INE)算法，Incremental Euclidean Restriction(IER)算法，Distance Browsing算法，Route Overlay and Association Directory(ROAD)算法以及G-tree算法。该论文对这些算法进行了详尽的实验评估和比较，并展示了大量的实验结果和对比图表，做出了卓有成效的工作。
二、研究背景
现如今地图服务已经变得无处不在，这得益于智能手机的大面积普及和其他具有GPS的功能设备的激增，以及价格便宜的无线网络带宽的覆盖。思科报告称，单就2013年移动设备的使用量就超过了五亿，而这些移动设备中77％为智能手机。据GlobalWeb Index报道，在2013年，谷歌地图是智能手机用户最常使用的应用程序，其拥有高达54％的智能手机用户。在地图服务中，最热门的应用就是查找附近的设施（例如，餐馆和自动取款机）。而KNN分类查询算法恰恰在此类问题中有着广泛的应用。虽然KNN算法的研究已经比较成熟，但是在实际应用中KNN算法仍然面临巨大的挑战。例如，N即所有被研究的物体数量往往远大于K即被依赖于分类的物品数量；再如，现实生活中的物体之间的距离不仅与物体的地理位置有关，也与地形路线之间有着复杂的关系。这些都导致了KNN算法实际应用上的巨大困难。该论文就针对当下应用最广泛的五种解决KNN问题的算法进行了严格的实践验证和效率分析，并得到了宝贵的实验数据。
在实际操作中，算法的效率往往受到多种因素的影响，例如数据的规模、数据的分布以及实现算法的数据结构的选择。因此，严谨公正地比较不同算法的时空效率就显得格外重要和具有挑战性。该论文研究问题的核心方法就是实验，通过设计严谨的实验来比较不同算法在解决同一问题时的不同时空效率。
三、算法描述
1．问题定义
我们将现实生活中的道路抽象成一个无向联通图，定义为G =（V，E），其中V是所有顶点的集合，E是所有边的集合。对于任意两个相邻的顶点U，V∈V，我们将它们之间的边定义为e（U，V），边的权重（如：距离或旅行时间）定义为w（U，V）。同时，我们定义d（U，V）为任意两点u和v之间最短路径的距离。给定一个待查询的顶点q和一个目标顶点集合O， KNN询问就是查询在目标顶点集合O中距离顶点q最近的k个点。
2．研究范围
已有的KNN算法根据其基于的索引分为混合索引和分离索引两大类。基于混合索引的算法创造了一个单独的索引来存储对象和道路网络。例如，著名的VN3算法使用了基于一些对象集合的泰森多边形图来划分道路网络；相反的，分离的索引技术使用两个单独的索引来设置对象和道路网络，而后者更具有实际意义并且拥有更多的优点。首先，一个现实生活中的KNN查询常常被应用到多个对象集合，例如，查询最近的k个餐厅或者停车位。在解决这类问题时，混合索引必须重复索引每种类型的对象，这将会导致巨大的空间开销和预处理时间开销。其次，对于一个对象集合的任何变化，混合索引必须更新整个索引并重新处理整个道路网络，而分离索引只需要更改对象的索引即可。分离索引的这个优势在询问频繁更新的对象时更加显著，比如询问对象是此刻可使用的停车位。所以该论文使用的KNN算法是基于分离式索引的，包括了Incremental Network Expansion (INE)算法，Incremental Euclidean Restriction(IER) 算法，Distance Browsing 算法，Route Overlay and AssociationDirectory (ROAD)算法以及 G-tree 算法。此外，为了应对智能手机激增的使用量和相应的基于地图的服务的广泛使用，KNN算法的实践必须使用基于内存的快速查询处理，以满足巨大的查询工作负担。所以该论文主要研究内存上KNN算法的实践效率。
3．算法描述
3.1 Incremental Network Expansion
Incremental Network Expansion（INE）是从Dijkstra算法中派生出的算法。类似于Dijkstra算法，INE算法保存了当前处理过的优先级最高的一些顶点，即保存了到查询顶点q最近的点的集合，初始化时该集合只有顶点q，然后不断将目标顶点集合O中距离该集合最近的一些顶点加入该集合，同时，使用刚加入该集合的顶点松弛各顶点到q的最短距离。重复这个过程直到该集合的元素数量等于k，结束算法。
3.2 Incremental Euclidean Restriction
Incremental Euclidean Restriction (IER) 采用欧氏距离作为启发式搜索，随着检索过程不断减小目标集合O中候选者的范围。首先，IER使用诸如R-tree的数据结构来检索欧式距离描述下的KNN问题，然后估算这k个对象的欧式距离并按距离从近到远将他们排序。现在这k个元素的集合成为KNN查询的候选集合，集合中距离q最远的顶点到q的距离（表示为Dk）变成了最终KNN查询集合的最远距离的一个上界。之后，IER遍历接下来在欧氏距离中距离顶点q最近的顶点p，如果p到q的欧式距离dE(q, p) ≥ Dk，则p不可能成为一个更优解，此时搜索便可以结束了，因为不存在更优秀的解了。否则，将p加入KNN查询集合的候选者集合中，并将原来候选者中距离q最远的点从集合中删除，并更新DK，然后继续该算法直到算法终止或发现不存在下一个最近的顶点。
3.3 Distance Browsing
Distance Browsing(DisBrw)使用Spatially Induced Linkage Cognizance (SILC)索引法解决KNN查询。DisBraw算法拥有较少的优先队列插入操作，因而有更高的效率。
首先介绍SILC索引。对于一个顶点s ∈ V , SILC预处理出s到其他所有节点的最短路径，接着分配给每个与s相邻的节点v不同的颜色，然后分配给每个顶点u ∈ V与v相同的颜色，满足v在从s到u的最短路径上（如图1-1，图中s=v6）。
SILC索引将道路网络划分成了一些四元树，对于包含在四元树区域b中每个顶点v，我们需要计算s到v的欧式距离和最短路上距离的比值，然后存储b中最小和最大的比值λ−和λ+。现在，任意给一个顶点t，通过将t所在区域的λ−，λ+和s到t的欧式距离相乘计算出一个区间[δ−, δ+]。这个区间可以用来淘汰不在KNN中的对象，同时，在扩展KNN下一个节点时，这个区间将不断被缩小，直到KNN算法结束或汇聚成一个足够精确的距离。
图1-1 SILC：基于v6的四元树染色图
3.4 Route Overlay & Association Directory
INE的搜索空间可能十分的巨大，而RouteOverlay and Association Directory (ROAD)算法通过排除不包含目标区域的搜索剪枝对INE进行了优化。
一个冗余网络子系统（rnet）包是道路网络G=(V, E)的一个划分，对于图中的每一条边都至少属于某个冗余网络子系统。冗余网络子系统的划分可以通过递归来完成，通过将道路网络划分为f>1个子系统，接着将f个子系统递归划分为若干个更小的系统来完成道路网络的划分。设原始的图层次为0，没划分一次层次增加1，若干次划分后道路网络被分为多个区域，区域之间的距离被特别标记，当确定某个区域内的所有顶点都不属于KNN查询的解时，可以通过只调用区域间的边来避免重复搜索排除掉的区域内的点，从而提升搜索效率。图1-2展示了图的一种划分。
图1-2 ROAD
3.5 G-tree
G-tree同样采用了图的划分来构造一种树的索引，从而通过子图层次来高效计算道路网络之间的距离。这种划分和ROAD中的划分相似，通过递归按层次不断划分。与ROAD划分不同的是，G-tree的每次划分，每个点都属于不同的区域，不存在交叉。图1-3展示了G-tree的一种划分。
在搜索扩展上，G-tree和ROAD也很相似，都是从高层次依次计算到低层次从而避免距离的重复计算，不同的是，G-tree的层次结构建立在一颗平稳的G-tree上，效率更稳定。G-tree还有一种聚合最短路径的方法，超出了该论文内容，不再叙述。
在计算KNN查询时，G-tree的优势在于建立了一个事件列表，存储G-tree的一些节点并支持动态修改，保证该列表实时更新。针对具有相同目标顶点集合O的KNN查询，G-tree避免了大量的重复计算，效率更高。
图1-3 G-tree
四、算法分析
1．Incremental Network Expansion
Incremental Network Expansion（INE）采用了Dijkstra算法中的贪心思想，通过不断询问与节点q最近的节点来扩展答案。INE算法的优点是思路清晰，实现简单。但同时该算法的缺点也很明显，那就是它需要访问所有靠近顶点q的顶点，这些节点的数量可能远大于k，而且被访问的许多节点本身可能距离q很远，完全没有必要被访问。另外，对于大规模数据，该算法时空复杂度也较高。采用优先队列存储其他顶点到q距离时，该算法时间复杂度可以达到O(|W|log|V|)，其中W为图中边的数量，V为图中顶点的数量。
2．Incremental Euclidean Restriction
Incremental Euclidean Restriction (IER) 算法的编程复杂度要高于INE，而且需要借助R-tree之类的数据结构来进行预处理。优点在于避免了冗余节点的访问，特别是距离q很远的节点几乎不会被访问，很具有实际意义。缺点是极端情况下仍然需要访问所有节点，最差的时间空间复杂度不亚于INR算法。
3．Distance Browsing
Distance Browsing(DisBrw)算法利用SILC索引减少了大量的优先队列插入操作，因而有更高的效率。其中SILC索引对图的区域划分和层次划分很具有启发意义。该算法需要O(|V|1.5)的时间复杂度对节点染色，O(|V|2log|V|)的时间复杂度处理出每一对最短路，其中，v为顶点数量。在实际应用中，效率往往高于前两种算法。
4．Route Overlay & Association Directory
Route Overlay and Association Directory (ROAD)算法通过划分冗余网络子系统和排除无效子系统的搜索剪枝优化了INE算法巨大的搜索空间，时空效率比INE有了明显的提升。
ROAD算法利用捷径的概念避免了INE中大量没有必要的搜索，在一般情况下，ROAD算法具有良好的平均时空复杂度，但是ROAD算法的效率依赖于图划分的优劣，也具有一定的不稳定性。
5．G-tree
G-tree算法提供了一种新的图区域划分和层次划分方法，并就图的层次结构建立了一颗平稳的G-tree树，拥有稳定而高效的时间复杂度，同时该树空间复杂度也很稳定，为O(|V|log|V|)，其中V为顶点数量。需要注意的是，G-tree的时间效率与其距离矩阵的实现方式密切相关，针对不同规模和分布的数据使用不同的哈希表拥有不同的效率，同时实验证明阵列实现比哈希表实现要快一个数量级。
五、算法实例
1．实际问题
在手机地图应用中求距离小明最近的k个餐厅。
2．应用算法
解决KNN查询的经典算法：Incremental Network Expansion（INE）算法。
3. 算法流程
3.1 输入：手机地图中重要地标的位置，道路信息，小明的位置以及餐厅的位置；
3.2 预处理：将地标转化为图的顶点，道路信息转化为图的边，地图信息处理成一个无向连通图G =（V,E），餐厅位置处理成目标点集O，小明的位置处理成初始顶点q；
3.3 分别计算与q相邻的点到q的距离，取距离q点最近的点v，加入KNN查询集合A；
3.4 若集合A中元素数量达到k个，或者图中所有节点都被处理过，算法结束，集合A即算法的解；否则，遍历与v相连的节点w，如果d（q，v）+ d（v，w）< d（q，w），则更新d（q，w）= d（q，v）+ d（v，w），然后重复步骤3.3。其中，d（x , y）为顶点x到顶点y的最短距离。