论文部分内容阅读
针对现实生活中动态路网的地理信息查询问题,提出了一种基于路由机制的动态路网中k近邻查询的算法。其主导思想是利用空间换时间,用路由表保存历史查询结果,用查询路由表的方法代替传统的最短路径计算,通过历史数据减少系统重复计算并对车辆行驶路径进行规划,用更新路由表的方法适应路况的变化。围绕路由表这一核心,改进相应的k近邻算法的过滤、精炼过程。通过路由表对动态路网进行少量的预处理,减少系统在k近邻搜索中的候选点数量,缩小查询范围,提高搜索效率。
Aiming at the problem of geographic information query of dynamic road network in real life, an algorithm of k-nearest neighbor query in dynamic road network based on routing mechanism is proposed. The main idea is to use space for time, use the routing table to save the history of the query results, with the query routing table instead of the traditional shortest path calculation, the system through the historical data to reduce double counting and vehicle routing path planning, with the updated routing table Method to adapt to changes in road conditions. Around the core of the routing table, we improve the filtering and refining process of the corresponding k-nearest neighbor algorithm. Through the routing table, a small amount of preprocessing of the dynamic road network can reduce the number of candidate points in the k-nearest neighbor search, reduce the scope of the query, and improve the search efficiency.