基于并行kNN的公路地理数据查询优化方法

刘俊杰，刘士宽，上官甦，刘 玲

（1.中交宇科空间信息有限公司，北京 100101；2.中国公路工程咨询集团有限公司，北京100101）

公路作为交通管理中最重要的地物，也是交管系统数据组织的核心[1]。在勘察设计、施工设计、运营养护等各阶段公路都将产生大量信息，因此空间数据检索技术对公路建设和公路应用系统具有重要支撑作用。如何高效地从海量公路地理空间数据中查询有用信息以指导公路建设运营管理成为研究的热点[2]。

在空间数据处理分析中，搜索一定空间范围内距离给定点最近的空间对象，称为空间近邻查询问题[3]。最近邻的空间对象可以是一个或多个，即空间查询中经典的kNN问题。kNN算法是一种理论上较成熟的查询算法。近年来，学者们从提高分类速度、降低算法对样本库容量的依赖性以及k值选定对算法的影响等方面入手，提出了许多有效的改进方法。PAN J S[4]等提出了快速算法（KWENNS）；Cheema M A[5]等提出了一种基于CircularTrip的kNN算法；宋晓宇[6]等提出了针对空间数据库的组反k最近邻概念，设计了基于R树的剪枝方法，通过提炼获取最终的GRkNN结果；Kim Y[7]等研究了通过MapReduce框架对top-k相似性算法进行改进的方法，实现了divide-and-conquer和 branch-and-bound算法，提出了all pair partitioning和 essential pair partitioning方法，用于最小化map和reduce函数之间的数据传送量；刘义[8]等在索引构建过程中，提出了一种采样算法，可快速确立空间划分函数，再利用R树索引进行k近邻连接查询，提高了查询效率；杜钦生[9]使用Hilbert曲线将多维空间中的点映射到一维空间，并通过块嵌套循环的方法解决了k近邻的连接；王飞[10]等提出了一种基于数据流的计算框架，利用空间填充曲线将多维数据映射为一维数据，从而将k近邻连接查询转化为一维范围查询。

常规索引往往是通过记录的存储地址来确定属性值，而倒排索引[11]则是根据属性值来寻找记录位置。在MapReduce框架[12]下，有些学者提出通过可并行的倒排索引结构处理海量文本数据的方法。基于此，在海量空间数据处理的过程中，也可有效利用数据的空间特性划分空间区域网格，并通过相应的映射函数处理空间对象坐标属性值，从而得到空间对象在网格单元中的具体位置。为了进一步管理空间对象和维护其与网格单元的位置关系，本文将空间网格索引与倒排索引相结合，提出了一种新的倒排网格索引；并针对海量公路空间数据，在倒排网格索引的基础上，重点探讨了基于轮圈的kNN算法在处理大规模公路空间数据集方面的应用。

1 基于轮圈的kNN算法

基于空间k最近邻查询方法，本文通过两个步骤来实现可并行的kNN算法：①初步查找，根据给定的查询点由近及远访问空间网格；②精细查找，通过网格索引查询距离给定点最近的k个空间对象。为了方便说明，本文均针对二维空间的点状数据。空间kNN查询的形式化定义为：

设P为二维空间的一个数据点集合，q为给定查询点，k为正整数，那么kNN查询就是在范围空间中找寻一个包含k个数据点的集合kNN，且满足任意点p'∈kNN 和任意点p∈p-kNN，始终有d(p',q)≤d(p,q)。符号表示含义如表1所示。

轮圈算法是一种非常有效的访问空间网格的算法，其返回的结果是经过一次轮圈后与圆弧相交的所有网格单元。如图1所示，执行一次轮圈算法会依次遍历图中所有阴影表示的网格，并将其加载到一个堆栈H中；再遍历堆栈中的网格单元CH，找到与查询点q最近邻的k个空间点。图1中C_start为起始网格，C为当前访问网格，C_u和C_r为当前访问网格的邻居，需通过计算距离并与当前画圆半径r进行比较来确定下一个将要访问的网格，如通过计算得到mind(C_u,q)

表1 符号定义表

图1 轮圈算法解析图

2 改进的可并行kNN算法

基于轮圈的kNN算法是一种串行执行算法，执行过程中需根据每次轮圈访问的结果确定下一次轮圈的画圆半径。本文结合并行计算、分布式存储等技术，对基于轮圈的kNN算法进行了适当改进，实现了可并行化，从整体上提升了算法查询性能，使其在大规模空间数据查询中具有更强的适应性。对基于轮圈的kNN算法的改进思路为：

1）采用倒排网格索引。网格索引的建立过程与空间kNN查询过程是相对独立的，且倒排网格索引本身具有可并行性，索引建立一次，可完成多次查询。

2）原有算法中轮圈半径r的初始化为r0

3）原有算法终止条件为mind(c,q)≥q.dk，即要找到第k个最近邻，且q点到第k个最近邻的距离不大于q点当前要访问网格的最小距离，算法结束。本文改进算法的终止条件为并行轮圈访问网格所收集的对象点之和|P|不小于k，并再进行一次轮圈访问，收集网格内的对象点到集合P中。

图2 改进算法执行实例图

改进算法的具体执行过程如图2所示。假设算法可并行的最大线程数为2，则q点的两个最近邻，k=2。如图2a所示，第一次有两个轮圈并行执行，在半径为r0和r0+a的轮圈访问中分别收集到p1和p2，此时集合P={ p1,p2}，满足|P|≥k=2，根据改进算法的终止条件，需再进行一次轮圈；如图2b所示，在半径为r0+2a的轮圈访问中又收集到p4，加入到集合P中后P={ p1,p2,p4}，再通过距离计算最终确定q点的两个最近邻（2NN）为{ p1,p4}，查询结束。

3 可并行kNN算法的验证与分析

在公路实际建设过程中，往往会涉及许多空间查询问题，这些问题均与空间最近邻查询相关。通过真实和模拟数据，本文从效率、网格边长、k值3个方面对可并行kNN算法进行验证。

3.1 实验数据

实验数据集包括真实数据和模拟数据两种：真实数据为海南公路基础数据库中描述公路空间实体地理位置的公路控制点，模拟数据为通过数据生成器在横、纵坐标为0～1 000的范围内随机均匀产生的空间对象点（表2）。

表2 实验空间数据集说明

3.2 实验结果与分析

3.2.1 算法效率对比

可并行kNN算法采用网格边长逐步递增的方式选择轮圈半径，并不依赖于上次轮圈访问的结果，且结合多线程并行技术，每次可实现多个轮圈的并行访问。图3反映的是在不同数据规模下，原有算法与改进算法的空间数据查询效率对比结果。

图3 不同数据规模算法执行效率

实验中设置网格边长为1，k=4，可并行kNN算法设置的最大并行执行线程数为2。从图3中曲线的变化趋势来看，当数据集规模不断增大时，两种算法查询空间4个最近邻点的响应时间都在增加；当数据集规模相同时，改进算法的查询时间明显比原有算法短。从图3中曲线的走向来看，随着数据集规模的增大，改进算法的查询时间增长速度变慢，查询效率变得稳定，所以改进算法更能适应较大规模空间数据的查询。

3.2.2 网格边长的设置对算法的影响

由于公路地理数据的空间线性分布性，在建立倒排网格索引时，网格边长的设置将影响网格内空间对象点的密度。对于同一个空间分布，当网格边长设置为较大值时，网格内空间对象点的平均密度就较大，单个轮圈执行时间较长；当网格边长设置为较小值时，轮圈次数可能随之增加，同时创建网格索引的代价也可能相应增大。在两个数据集上的算法执行效率如图4、5所示。

图4 海南公路基础数据库数据集的算法执行效率

图5 模拟随机均匀分布数据集的算法执行效率

实验中数据集规模为100 M，当k=4时，同等情况下改进算法的效率比原有算法高。由图4可知，当网格边长为0.01时，算法的执行效率最高，这是因为该数据集具有公路空间分布特性，数据经纬度坐标分布在18～110之间，此时网格中数据点分布适中，从而算法执行效率最高；而对于模拟随机均匀分布数据集，数据点分布没有规律，只要保证网格中数据点的密度适中，算法就会有较高的执行效率。因此，网格边长的设定对算法的执行效率会产生较大影响，在实际运用中要根据空间对象的具体分布来设定网格边长，一方面有利于提高算法效率，另一方面可节约网格索引的存储空间。

3.2.3k值设定对算法的影响

公路空间数据的查询往往涉及多个空间对象，即对于给定的q点，要找到与其最近邻的多个空间对象点，这就需要设置算法的相关参数k。图6为当k取不同值时，两种算法查询执行效率的变化情况。

图6 不同k值时两种算法的效率对比

图6中设定的网格单元边长为1，当k取不同值时，改进算法的查询效率均比原有算法高。随着k值的增大，改进算法的查询时间增长较为缓慢，查询效率相对稳定；而原有算法的查询时间增长较快，查询效率降低。当k值增大时，需要查询的最近邻点增多，轮圈访问网格的次数相应增加，由于原有算法中轮圈半径的更新需依赖于上次的访问结果，只能一圈一圈地进行遍历，效率较低；而改进算法可实现多线程并行轮圈，每次可同时进行多圈遍历，从而表现出更高的效率。由此可见，改进算法更能适应查询多个空间对象点的情况。

4 结 语

本文针对公路地理数据分布特点提出了一种倒排网格空间索引，通过空间位置坐标将空间对象映射到网格索引中，具有更好的可并行性，且结构简单，实现与维护相对比较容易。基于此，本文对串行轮圈kNN算法做了深入分析，以网格边长递增的方式对轮圈半径进行更新，打破了轮圈半径依赖上轮访问结果的局限，并结合多线程技术提出了可并行kNN算法，有效提高了算法的查询效率。本文从数据集规模、网格边长、k值选取3个方面对比分析了两种算法的效率，验证了改进算法的高效性以及在处理大规模空间数据集方面的实用性。

[1] 李扬,褚春超,陈建营.我国公路交通可持续发展的模式选择[J].公路交通科技,2012,29(12):144-147

[2] Lee K C K, Lee W C, ZHENG B H, et al. Road: a New Spatial Object Search Framework for Road Networks[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(3):547-560

[3] 赵亮,景宁,陈荦等.面向多核多线程的移动对象连续K近邻查询[J].软件学报,2011,22(8):1 805-1 815

[4] PAN J S, QIAO Y L, SUN S H. A Fast k Nearest Neighbors Classification Algorithm[J]. Ieice Transactions on Fundamentals of Electronics Communications and Computer,2004,E87A(4):961-963[5] Cheema M A, YUAN Y D, LIN X M. Circulartrip: an Effective Algorithm for Continuous kNN Queries[M]. Advances in Databases: Concepts, Systems and Applications, Springer Berlin Heidelberg,2007:863-869

[6] 宋晓宇,于程程,孙焕良,等.GRkNN:空间数据库中组反k最近邻查询[J].计算机学报,2010,33(12):2 229-2 238

[7] Kim Y, Shim K. Parallel Top-K Similarity Join Algorithms Using MapReduce[J]. IEEE International Conference on Data Engineering,2012,41(4):510-521

[8] 刘义,景宁,陈荦,等. MapReduce框架下基于R-树的k-近邻连接算法[J].软件学报,2013,24(8):1 836-1 851

[9] 杜钦生.高维空间的k最近邻查询及连接问题研究[D].长春:吉林大学,2015

[10] 王飞,秦小麟,刘亮,等.基于数据流的k-近邻连接算法[J].计算机科学,2015,42(5):204-210

[11] Yan H, Ding S, Suel T. Inverted Index Compression and Query Processing with Optimized Document Ordering[C].Proceedings of the18th International Conference on World Wide Web,2009,4(4):401-410

[12] Cordeiro R L F, Traina A J M, Kang U, et al. Clustering Very Large Multi-dimensional Datasets with MapReduce[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2011:690-698