基于NOSQL数据库的路网最短路径查询及优化研究

发布时间：2017-12-12 07:07

  本文关键词：基于NOSQL数据库的路网最短路径查询及优化研究

  更多相关文章： Neo4j A* 路网 最短路径 PostgreSQL

【摘要】：基于路网的路径规划问题作为地理信息与交通工程领域一直备受人们青睐。在过去,路网信息主要以表的形式存储在关系数据库中。从对网络以及图等结构的数据处理来看,传统的关系数据库以关系模式进行存储,但在关系模型上存储图结构以及实现图相关算法时较为复杂,大量的关系表联结使得性能不高。伴随着NOSQL数据库的发展,涌现出了一大批适合不同数据模型的数据库,像文档数据库、键值对数据库、列式数据库和图数据库等。这为许多不适合关系结构存储的数据模型提供了新的发展空间。Neo4j作为NOSQL数据库里图数据库的代表,提供了以节点与关系为实体的存储模型。这种以图为数据模型的存储形式将更符合路网数据模型。因此,本文对基于Neo4j的路网最短路径查询进行了研究。研究过程中通过与关系型数据库比较分析了图数据库的特点,并根据其特点以及最短路径算法提出了一种改进的双向搜索算法。论文的研究内容主要包括以下几点:(1)研究关系型数据库与Neo4j数据库存储结构的特征,实现路网数据在两种平台的数据存储与预处理。具体内容是分析两者的数据模型,将数据转换为适用于两种数据库的不同格式,实现同一数据源在不同存储平台的存储。提出数据处理的方法,包括顶点经纬度坐标及位置的处理,并实现数据库中路网数据的拓扑结构。(2)研究Neo4j数据库特性。为了分析图形数据库特殊的数据模型在图结构上的优势以及与关系数据库的差异,基于两种不同存储平台实现A*算法。研究两种存储平台下路网最短路径查询,并以冷热两种启动方式分析查询过程中内存消耗和缓存对两种数据库的作用以及数据库查询效率方面的性能。(3)基于Neo4j改进的A*算法的研究。通过对图数据库Neo4j的研究发现,其关系结构可以很好支持双向遍历;其次,其在图数据路径查询时存在消耗大量内存的弊端。针对Neo4j的弊端以及结构特点提出了改进的双向搜索A*算法。改进主要有两点:一是提出以最佳节点为相对目的节点的动态搜索思想;二是提出比较两端最小估计值的切换标准。同时结构上使用了可以快速排序的最小二叉堆数据结构。对其改进效果进行了实验验证,发现改进后的算法有很好的效果。
【学位授予单位】：北京工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13

【相似文献】

中国期刊全文数据库 前10条

1 ;第一届全国数据库应用技术年会[J];计算机学报;2006年01期

2 刘向民;;建立数据库应用团队的必要性[J];中国金融电脑;2011年06期

3 ;让数据库“大团结”[J];每周电脑报;2001年07期

4 赵昱;赵华;;不依赖数据库实现不同页面歌曲连播技巧[J];电脑学习;2006年06期

5 王云爱,赵文莉;漫谈网上查询数据库[J];山西煤炭;1999年04期

6 卞静,余豪泽,王久兴,何之璋;基于数据库的函数搜索设计[J];现代计算机(专业版);2005年01期

7 李超;袁兆山;吴雷;;两级数据库的设计和实现技术研究[J];计算机应用研究;2006年07期

8 郭思培;彭智勇;;数据库规范化理论研究[J];武汉大学学报(理学版);2011年06期

9 杨凡;蒋建春;卿斯汉;;弱点数据库的设计及其实现[J];计算机科学;2002年06期

10 徐贵红;含有组合列的约束数据库[J];内蒙古大学学报(自然科学版);2001年01期

中国重要会议论文全文数据库 前7条

1 李德毅;;归纳学习:从数据库中发现知识[A];第十届全国数据库学术会议论文集[C];1992年

2 刘佼;肖稳安;王业成;;全国雷电灾害数据库分析与设计[A];S13 第十届防雷减灾论坛——雷电灾害与风险评估[C];2012年

3 陈恩红;李青;;前言[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

4 尹少宜;陈继东;孟小峰;赖彩凤;;手机数据库PhoneDB的存储和恢复技术[A];第二十二届中国数据库学术会议论文集（研究报告篇）[C];2005年

5 汤庸;黄锦辉;李青;;前言[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

6 李宁;;基于全具象和Agent的虚拟数据库实现[A];第十九届全国数据库学术会议论文集（技术报告篇）[C];2002年

7 ;前言[A];第十二届全国数据库学术会议论文集[C];1994年

中国重要报纸全文数据库 前1条

1 江苏 周转义;用ASP实现动态IP转向[N];电脑报;2003年

中国硕士学位论文全文数据库 前10条

1 乔隽;Web数据库采样技术研究[D];东北大学;2013年

2 朱小强;基于J2EE的CRM客户与协议系统的设计与实现[D];南京大学;2015年

3 于海鹏;基于NOSQL数据库的路网最短路径查询及优化研究[D];北京工业大学;2016年

4 张耀坤;P2P数据库内容认证方案的设计与实现[D];华中科技大学;2007年

5 翟钰;系统脆弱性研究及其数据库的设计与实现[D];西安建筑科技大学;2004年

6 刘才;中学学生信息管理系统[D];吉林大学;2009年

7 黄睿;FCoE交换机ZONE数据库模块的设计和实现[D];北京邮电大学;2011年

8 董华荣;小学高效课堂实验平台设计与实现[D];山西大学;2013年

9 包曙;内蒙古电力公司人力资源管理系统设计[D];内蒙古大学;2012年

10 孙奇;ERP中库存管理与人力资源管理的研究及开发[D];中北大学;2008年

，

本文编号：1281585