摘要
有效的路径查询处理是地理信息系统、导航系统及计算机网络等高级应用中的一个关键需求 .文中研究如交通网络和通信网络等节点数很大的网络中的最佳路径查询算法 .为了保证最佳路径查询的响应时间 ,采用实例化最佳路径视图的策略 ,即预先计算和存储最佳路径 .文中提出了 HEPV (Hierarchical Encoded Path View )结构 ,证明了在 HEPV上进行路径查询的最佳性 ,同时给出了相应的最佳路径查询算法 .
Efficient path query processing is a key requirement for advanced applications including GIS (Geographic Information Systems), navigation systems, and computer networks. The author investigates the best path query algorithm in the context of networks with large number of nodes and links, such as transportation networks and computer networks. To guarantee efficient response for best path queries, this paper employs a path view materialization strategy for pre computing and store the best paths, proposes the HEPV (Hierarchical Encoded Path View) approach, gives the optimality theorem of path retrieval over HEPV, as well as proposes best path retrieval algorithm.
出处
《计算机学报》
EI
CSCD
北大核心
2000年第2期184-189,共6页
Chinese Journal of Computers
关键词
路径查询
最佳路径
算法
交通网
通信网
path query, best path, path view, hierarchical graph model
