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

doi:10.3969/j.issn.1000-3428.2011.22.016

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

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

邓定雄 ¹，关佶红 ²

(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 ¹, GUAN Ji-hong ²

(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

摘要/Abstract

摘要： 针对在线地图服务和路程安排等领域中的点对点最短路径查询方法，提出一种新的数据结构——最短路径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

中图分类号:

TP311

邓定雄, 关佶红. 基于SPB树的公路网络最短路径查询[J]. 计算机工程, 2011, 37(22): 56-58.

DENG Ding-Xiong, GUAN Ji-Gong. Shortest Path Query for Road Network Based on SPB Tree[J]. Computer Engineering, 2011, 37(22): 56-58.

参考文献

[1] 向剑平, 王悦, 胡剑. 基于道路网络的受限优化路径搜索算法[J]. 计算机工程, 2011, 37(12): 53-55.
[2] 冯惠妍, 郭俊凤. 道路网络中的连续最近邻查询[J]. 计算机工程, 2010, 36(8): 79-82.
[3] Dijkstra E W. A Note on Two Problems in Connection with Graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
[4] Goldberg A V, Harrelson C. Computing the Shortest Path: A* Search Meets Graph Theory[C]//Proc. of SODA’05. Vancouver, Canada: ACM Press, 2005: 156-165.
[5] Kaplan G H, Werneck R F. Reach for A*: Efficient Point-to-point Shortest Path Algorithms[C]//Proc. of ALENEX’06. Miami, USA: [s. n.], 2006: 129-143.
[6] Sanders P, Schultes D. Highway Hierarchies Hasten Exact Shortest Path Queries[C]//Proc. of ESA’05. Geneva, Switzerland: [s. n.], 2005: 568-579.
[7] Geisberger R, Sanders P, Schultes D, et al. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks[C]// Proc. of WEA’08. Cape Cod, USA: [s. n.], 2008: 319-333.
[8] Sankaranarayanan J, Alborzi H, Samet H. Efficient Query Processing on Spatial Networks[C]//Proc. of GIS’05. Bremen, Germany: [s. n.], 2005: 200-209.
[9] Samet H, Sankaranarayanan J, Alborzi H. Scalable Network Distance Browsing in Spatial Databases[C]//Proc. of SIGMOD’08. Vancouver, Canada: [s. n.], 2008: 43-54.
[10] Sankaranarayanan J, Samet H, Alborzi H. Path Oracles for Spatial Networks[C]//Proc. of VLDB’09. Lyon, France: [s. n.], 2009: 1210-1221.
[11] Samet H. Foundations of Multidimensional and Metric Data Structures[M]. [S. l.]: Morgan Kaufmann, 2006.
[12] Gargantini I. An Effective Way To Represent Quadtrees[J]. Communication of ACM, 1982, 25(12): 905-910.
[13] Morton. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing[Z]. IBM, 1966.

[1]	周诗源, 王英林. 基于布谷鸟搜索优化算法的多文档摘要方法[J]. 计算机工程, 2020, 46(7): 58-64,71.
[2]	马鹏, 王泽宇, 钟卫东, 王绪安. 基于改进小波包分解的相关功耗攻击降噪方法[J]. 计算机工程, 2020, 46(7): 129-135,142.
[3]	孟庆强,何浩奇,毕倪飞,赵斌,吉根林. 面向多属性的不等值连接操作算法[J]. 计算机工程, 2019, 45(6): 60-66.
[4]	孙营,王波涛. 基于可变形部件改进模型的夜间车辆检测方法[J]. 计算机工程, 2019, 45(3): 202-206.
[5]	孙小虎, 韩文军, 潘娟, 许刚. 基于聚合与动态调度的变电站三维可视化研究[J]. 计算机工程, 2019, 45(12): 300-307.
[6]	王思翔,张磊,段晓毅,崔琦,高献伟. 基于希尔伯特黄变换滤波预处理的相关性能量分析攻击[J]. 计算机工程, 2018, 44(7): 160-165,171.
[7]	孙振华,南新元,蔡鑫. 基于动态数据驱动的生物氧化槽进气量预测[J]. 计算机工程, 2018, 44(6): 279-282,287.
[8]	陈东,邵增珍,魏争争,刘衍民. 基于中国观鸟数据的移动对象周期模式发现[J]. 计算机工程, 2017, 43(4): 1-7.
[9]	杨浩,林喜军,曲海鹏. 分布式网络下改进的Top-k查询算法[J]. 计算机工程, 2017, 43(2): 79-84.
[10]	段晓毅,王思翔,崔琦,孙渴望. 一种带掩码AES算法的高阶差分功耗分析攻击方案[J]. 计算机工程, 2017, 43(10): 120-125.
[11]	高敬阳,赵彦. 基于样本抽样和权重调整的SWA-Adaboost 算法[J]. 计算机工程, 2014, 40(9): 248-251,256.
[12]	葛星,沈耀,徐常亮. 基于云计算的多重查询优化系统[J]. 计算机工程, 2014, 40(9): 46-50,58.
[13]	李松,张丽平,刘艳,郝晓红,杨和禹. 障碍物环境下的动态单纯型连续近邻链查询[J]. 计算机工程, 2014, 40(8): 52-57.
[14]	王恩东，温源，张宇，施光源. 应用于SAN的自动精简配置架构设计与实现[J]. 计算机工程, 2014, 40(6): 8-12.
[15]	刘万贤，彭华，于沛东. 基于软判决的PN码序列多项式估计改进算法[J]. 计算机工程, 2014, 40(6): 53-57.

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

Shortest Path Query for Road Network Based on SPB Tree

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10