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

摘要

根据公路工程地理数据的空间和属性特征,建立了一种倒排网格索引,通过坐标来反映空间对象在网格中的具体位置.重点探讨了kNN查询算法,对串行轮圈访问kNN算法进行了改进,打破了轮圈半径对其上一次遍历结果的依赖性,以网格边长递增的方式更新轮圈半径,并结合多线程技术实现了多个轮圈的并行访问.通过在模拟的海量公路空间数据集上的实验,从数据集规模、网格边长、k值选取等方面对比分析了两种算法的查询效率.结果表明,改进后的kNN算法对于大规模空间数据集的查询效率有很大提高.