基于格网划分的道路最近邻查询算法

Road Nearest Neighbor Query Algorithm Based On Grid Partition

针对现有道路最近邻查询算法均以数据点作为道路端点进行查询,并未考虑数据点在道路上的情况,使得在大数据量时查询效率不够理想的问题,利用格网划分算法进行解决。利用分治法的思想,将查询区域进行格网划分,缩小有效的查询区域,快速定位查询点所在道路,进而找到最近邻数据点。研究结果表明:当数据量足够大时,格网划分算法与增量网络扩张(INE)算法相比,查询时间明显降低,效率明显提升,格网划分查询的时间复杂度为O(1);当数据量较少时,格网划分算法与INE算法相比,查询时间减少并不明显,表明格网划分算法更适用于大数据量最近邻查询。

For the existing road nearest neighbor query algorithms,the data points were used as the road vertex to query and the situation of the data points on the road was not taken into account,which made the query efficiency was not ideal in the case of large amount of data. This problem was solved by the grid partition algorithm.By using the idea of divide and conquer method,this method reduced the effective query area by dividing query area into grid,quickly located the road where the query point is located,and then found the nearest neighbor stronghold.The research results show that when the amount of data are large enough,the query time of grid partition algorithm is decreased obviously compared with incremental network expansion( INE)algorithm,and the time complexity of grid partition query is O(1).When the amount of data is small,the query time of grid partition algorithm is not much higher than that of INE algorithm,which indicates that grid partition algorithm is more suitable for nearest neighbor query with large amount of data.