基于路由机制的时变路网k近邻算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (2): 30-34.

基于路由机制的时变路网k近邻算法

张栋良，唐俊

(上海电力学院电力系自动化工程学院上海200090)；(同济大学嵌入式系统与服务计算教育部重点实验室上海201804)

出版日期:2018-11-16 发布日期:2018-11-16

k-Nearest Neighbor Algorithm in Dynamic Road Network Based on Routing Mechanism

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 针对现实生活中动态路网的地理信息查询问题，提出了一种基于路由机制的动态路网中k近邻查询的算法。其主导思想是利用空间换时间，用路由表保存历史查询结果，用查询路由表的方法代替传统的最短路径计算，通过历史数据减少系统重复计算并对车辆行驶路径进行规划，用更新路由表的方法适应路况的变化。围绕路由表这一核心，改进相应的k近邻算法的过滤、精炼过程。通过路由表对动态路网进行少量的预处理，减少系统在k近邻搜索中的候选点数量，缩小查询范围，提高搜索效率。

关键词: 路由机制，k近邻算法，时变路网

Abstract: Aiming at the issue of geography information query, a new k-Nearest Neighbor algorithm for dynamic road network was proposed based on routing mechanism. With the idea of "space for time"，we saved history query results in routing tables,and substituted the traditional method by requiring tables. We updated the route tables to adapt the time varying road status. With the kernel of routing table, we improved the filtering and refining procedure of kNN algorithm. I3y preprocess of dynamic road network using routing table, the amount of candidate points in k-NN computing is reduced, and the rang of query and the searching efficiency are promoted.

Key words: Routing mechanism, k-nearest neighbor algorithm, Dynamic road network

张栋良，唐俊. 基于路由机制的时变路网k近邻算法[J]. 计算机科学, 2013, 40(2): 30-34. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed