计算机工程 ›› 2011, Vol. 37 ›› Issue (22): 56-58.doi: 10.3969/j.issn.1000-3428.2011.22.016

• 软件技术与数据库 • 上一篇    下一篇

基于SPB树的公路网络最短路径查询

邓定雄 1,关佶红 2   

  1. (1. 复旦大学计算机学院,上海 200433; 2. 同济大学计算机科学与技术系,上海 201804)
  • 收稿日期:2011-10-12 出版日期:2011-11-18 发布日期:2011-11-20
  • 作者简介:邓定雄(1987-),男,硕士研究生,主研方向:空间数据库查询;关佶红,教授、博士生导师
  • 基金项目:
    国家自然科学基金资助项目(60873040)

Shortest Path Query for Road Network Based on SPB Tree

DENG Ding-xiong 1, GUAN Ji-hong 2   

  1. (1. School of Computer Science, Fudan University, Shanghai 200433, China; 2. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China)
  • Received:2011-10-12 Online:2011-11-18 Published:2011-11-20

摘要: 针对在线地图服务和路程安排等领域中的点对点最短路径查询方法,提出一种新的数据结构——最短路径B+树(SPB树),以有效存储预先计算好的点空间信息和与之对应的最短路径信息。实验结果证明,利用SPB树在公路网络上进行最短路径查询比经典的Dijkstra算法最高快出3个数量级。

关键词: 最短路径问题, 查询处理, 公路网络, 预处理, B+树, 索引结构, Z-order曲线

Abstract: This paper adopts the widely used preprocessing techniques to facilitate shortest path query, and proposes a new index structure, namely Shortest Path B+ tree(SPB tree), which can encode both the shortest path information and vertices’ spatial position compactly. Using this index structure, the point-to-point shortest path query in road network can be answered up to three orders of magnitude faster than using the classical Dijkstra algorithm. Besides, SPB tree is space efficient which occupies reasonable memory consumption and can be constructed efficiently. Extensive experimental studies validates the effectiveness and efficiency of using SPB tree in point-to-point shortest path query.

Key words: shortest path problem, query processing, road network, preprocessing, B+ tree, index structure, Z-order curve

中图分类号: