收稿日期：2017-04-06。
项目来源：交通运输部2014年度科技资助项目（2014364J03090）。
刘俊杰1,2，刘士宽1,2，上官甦1,2，刘 玲1,2
（1.中交宇科空间信息有限公司，北京 100101；2.中国公路工程咨询集团有限公司，北京100101） 摘 要：根据公路工程地理数据的空间和属性特征，建立了一种倒排网格索引，通过坐标来反映空间对象在网格中的具体位置。重点探讨了kNN 查询算法，对串行轮圈访问kNN 算法进行了改进，打破了轮圈半径对其上一次遍历结果的依赖性，以网格边长递增的方式更新轮圈半径，并结合多线程技术实现了多个轮圈的并行访问。通过在模拟的海量公路空间数据集上的实验，从数据集规模、网格边长、k 值选取等方面对比分析了两种算法的查询效率。结果表明，改进后的kNN 算法对于大规模空间数据集的查询效率有很大提高。 关键词：倒排网格；kNN ；索引；轮圈
中图分类号：P208 文献标志码：B
文章编号：1672-4623（2018）05-0035-03
公路作为交通管理中最重要的地物，也是交管系统数据组织的核心[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
地理空间信息
·36·第16卷第5期
中；再遍历堆栈中的网格单元C H，到与查询点q最近邻的k个空间点。图1中C_start为起始网格，C为当前访问网格，C_u和C_r为当前访问网格的邻居，需通过计算距离并与当前画圆半径r进行比较来确定下一个将要访问的网格，如通过计算得到min d(C_u,q) < r < max d(C_u,q)，则下一个将要访问的网格为C_u。同理，可按照圆弧的走向计算得到其他所有需要访问的网格，直到返回起始网格为止。
图1 轮圈算法解析图
2 改进的可并行kNN算法
基于轮圈的kNN算法是一种串行执行算法，执行过程中需根据每次轮圈访问的结果确定下一次轮圈的画圆半径。本文结合并行计算、分布式存储等技术，对基于轮圈的kNN算法进行了适当改进，实现了可并行化，从整体上提升了算法查询性能，使其在大规模空间数据查询中具有更强的适应性。对基于轮圈的kNN算法的改进思路为：
1）采用倒排网格索引。网格索引的建立过程与空间kNN查询过程是相对独立的，且倒排网格索引本身具有可并行性，索引建立一次，可完成多次查询。
2）原有算法中轮圈半径r的初始化为r0<max d (C q,q)，以保证q点所在网格能被访问到，而下一轮圈的半径更新为r=min{ r+a,q.d k}。本文将轮圈半径更新方法修改为r=r0+i×a（i从0开始取值），这样每次轮圈半径均根据网格边长a进行递增，不必依赖上一轮圈的查询结果。结合多线程机制，可实现多个轮圈并行地对网格进行遍历，达到可并行化的效果。
3）原有算法终止条件为min d(c,q)≥q.d k，即要到第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 实验空间数据集说明
实验数据集空间对象点数据说明
真实数据集10 000 000（500 M）海南公路基础数据库数据
模拟数据集 2 500 000（120 M）数据生成器生成的随机数据3.2 实验结果与分析
3.2.1 算法效率对比
可并行kNN算法采用网格边长逐步递增的方式选
表1 符号定义表
符号形式含义说明
O,p空间对象、空间点
p.x,p.y空间点横、纵坐标（二维）C,C[i,j]网格单元、第i行第j列的网格d(p,q)p点和q点的欧氏距离
中国急救网
q.kNN q点的k个最近邻集
a空间网格的边长
C p包含点p的网格单元
q.d k q点与其第k个最近邻的欧氏距离min d(C,q)q点与网格单元C之间的最小距离max d(C,q)q点与网格单元C之间的最大距离
·37·
第16卷第5期
刘俊杰等：基于并行kNN 的公路地理数据查询优化方法择轮圈半径，并不依赖于上次轮圈访问的结果，且结合多线程并行技术，每次可实现多个轮圈的并行访问。图3反映的是在不同数据规模下，原有算法与改进算法的空间数据查询效率对比结果。
算法响应时间/s
数据集规模/MB
图3 不同数据规模算法执行效率
实验中设置网格边长为1，k =4，可并行kNN 算法设置的最大并行执行线程数为2。从图3中曲线的变化趋势来看，当数据集规模不断增大时，两种算法查询空间4个最近邻点的响应时间都在增加；当数据集规模相同时，改进算法的查询时间明显比原有算法短。从图3中曲线的走向来看，随着数据集规模的增大，改进算法的查询时间增长速度变慢，查询效率变得稳定，所以改进算法更能适应较大规模
空间数据的查询。3.2.2 网格边长的设置对算法的影响
由于公路地理数据的空间线性分布性，在建立倒排网格索引时，网格边长的设置将影响网格内空间对象点的密度。对于同一个空间分布，当网格边长设置为较大值时，网格内空间对象点的平均密度就较大，单个轮圈执行时间较长；当网格边长设置为较小值时，轮圈次数
可能随之增加，同时创建网格索引的代价也可能相应增大。在两个数据集上的算法执行效率如图4、5所示。
算法响应时间
/s 网格边长a
图4 海南公路基础数据库数据集的算法执行效率
12345678算法响应时间/s
a
图5 模拟随机均匀分布数据集的算法执行效率
实验中数据集规模为100 M，当k =4时，同等情
况下改进算法的效率比原有算法高。由图4可知，当网格边长为0.01
时，算法的执行效率最高，这是因为该数据集具有公路空间分布特性，数据经纬度坐标分布在18~110之间，此时网格中数据点分布适中，从而算法执行效率最高；而对于模拟随机均匀分布数据集，数据点分布没有规律，只要保证网格中数据点的密度适中，算法就会有较高的执行效率。因此，网格边长的设定对算法的执行效率会产生较大影响，在实际运用中要根据空间对象的具体分布来设定网格边长，一方面有利于提高算法效率，另一方面可节约网格索引的存储空间。
3.2.3 k 值设定对算法的影响
公路空间数据的查询往往涉及多个空间对象，即对于给定的q 点，要到与其最近邻的多个空间对象点，这就需要设置算法的相关参数k 。图6为当k 取不同值时，两种算法查询执行效率的变化情况。
查询执行时间/s k 值
改进并行算法
串行轮圈算法
图6 不同k 值时两种算法的效率对比
图6中设定的网格单元边长为1，当k 取不同值时，改进算法的查询效率均比原有算法高。随着k 值的增大，改进算法的查询时间增长较为缓慢，查询效率相对稳定；而原有算法的查询时间增长较快，查询效率降低。当k 值增大时，需要查询的最近邻点增多，轮圈访问网格的次数相应增加，由于原有算法中轮圈半径的更新需依赖于上次的访问结果，只能一圈一圈地进行遍历，效率较低；而改进算法可实现多线程并行轮圈，每次可同时进行多圈遍历，从而表现出更高的效率。由此可见，改进算法更能适应查询多个空间对象点的情况。
4 结 语
本文针对公路地理数据分布特点提出了一种倒排网格空间索引，通过空间位置坐标将空间对象映射到网格索引中，具有更好的可并行性，且结构简单，实现与维护相对比较容易。基于此，本文对串行轮圈kNN 算法做了深入分析，以网格边长递增的方式对轮圈半径进行更新，打破了轮圈半径依赖上轮访问结果的局限，并结合多线程技术提出了可并行kNN 算法，有效提高了算法的查询效率。本文从 （下转第40页）
地理空间信息
张琨维·40·第16卷第5期
palm m5004 关键技术
4.1 带有时间维的地理国情追溯变更历史算法
构建以GIS为软件平台的带有时间维的数据库的关键在于处理复杂的数据关联。地理国情数据库中存在拓扑关联与属性关联两种复杂的关联，进行一个要素的变更时，可能联动两个甚至两个以上的要素，并引起属性变更[7]。
更新时，建立现状数据库与历史数据库两套数据文件，每发生一起变更，先将原始数据作为历史数据存储在历史数据库中，然后对现状数据进行编辑、删除，使之成为反映现势状态的国情数据，再通过
两个数据库同种要素的空间叠置分析，构建带有时间维的更新数据，并实现历史追溯。
4.2 地理国情变更的拓扑技术
地理国情数据的变更输入与初始输入是两种截然不同的状态。初始输入是在新建数据库的基础上，将一个县或一个区域的多幅图件输入完毕后，自动生成拓扑关系；变更输入则是在现有拓扑关系的基础上，做若干编辑修改处理，而这种删改原有拓扑关系的数据文件是比较复杂的，不仅是删改一个对应的数据，而是多个数据。
在进行大数据量变更时，涉及图形较多，大量原有弧段发生变化，有些删除，有些一分为二，还有部分新增弧段，通过引入变更行为的概念将所有弧段赋予变更行为，遍历所有数据重新组织弧段，废止原有拓扑关系，生成新的拓扑关系。通过该方式可大量减少在原有拓扑关系上“修修补补”的工作量。
5 结 语
地理国情普查数据的增量式更新是提高地理国情变更调查工作效率和变更数据成果质量的重要技术方法。对地理国情普查数据增量式更新技术的分析和研究，为综合利用3S技术，实现地理国情信息对政府、企业和公众的服务，为国家战略规划制定、空间规划管理、区域政策制定、灾害预警、科学研究和社会公众服务等提供了必要的技术支撑。
参考文献
[1] 国务院第一次全国地理国情普查领导小组办公室.地理国
情普查内容与指标:GQJC 001-2013[S].北京：测绘出版社, 2013:1-3
[2] 陈俊勇.地理国情监测[R].武汉：武汉大学,2012:1
[3] 李德仁，眭海刚，单杰.论地理国情监测的技术支撑[J].武
汉大学学报(信息科学版),2012,37(5):505-512
[4] 国务院第一次全国地理国情普查领导小组办公室.地理国情
普查数据规定与采集要求:GDPJ 03-2013[S].北京：测绘出版社,2013:5-13
[5] 国务院第一次全国地理国情普查领导小组办公室.地理国情
普查基本统计技术规定:GDPJ 02-2013[S].北京：测绘出版社,2013:29-31
[6] 国务院第一次全国地理国情普查领导小组办公室.成果资
料汇交与归档基本要求:GDPJ 07-2013[S].北京：测绘出版社,2013:3-5
[7] 史文中，秦昆，陈江平，等.可靠性地理国情动态监测的理
论与关键技术探讨[J].科学通报,2012,57(24):2 239-2 248
第一作者简介：连恒，硕士研究生，工程师，研究方向为地图制图与空间数据库建设。
（上接第37页）数据集规模、网格边长、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
第一作者简介：刘俊杰，硕士研究生，工程师，现从事地理信息方面工作。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议