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