| The research of path planning based on the road network is favored by people in the field of geographic information and traffic engineering. In the past, network information is stored mainly in the form of table in relational database. From the point of view of data processing on the structure of network and graph, the traditional relational database is stored in relational schema, but it is more complicated to store the graph structure and implement the related algorithm in the relational data model, a large number of connections between the table makes poor performance. With the development of NOSQL database, a large number of database suitable for different data models have emerged, as a document database, key value database, column database and map database etc. It provides a new development space for the data model which is not suitable for the relational structure.Neo4j as a representative of graph database, provides a storage model which takes the node and relation as the entity. In this model data storage form will be more in line with the road network data model. Therefore, in this paper, the shortest path query based on Neo4 j is studied. This paper analyzes the characteristics of the database by comparing with the relational database, and puts forward an improved bidirectional search algorithm based on its characteristics and the shortest path algorithm.The research contents of this paper mainly include the following points:(1) Research on the characteristics of storage structure of the relationship database and the Neo4 j database. realize the data storage of the road network data in two kinds of platforms. The detailed content is to analyze the data model, to store data in the two platforms with the same data source which has been processed. Method of data processing is proposed that includes the processing of vertex latitude and longitude coordinates and position, and implements the topological structure of the data.(2) Research on the performance of Neo4 j database. In order to analyze the advantage of the special data model in the graph structure and the difference between the relation database, this paper implemented a * algorithm based on two different storage platform. The shortest path query based on two kinds of storage platform is studied, and it is analyzed not only effect of the cache on the two databases in the process of two kinds of start up mode of hot and cold but also the performance of database query efficiency and memory consumption.(3) Research on the improved A* algorithm based on Neo4 j. Through the study of the database Neo4 j found that can be well support bidirectional traversal; secondly, it has the disadvantages of consuming a large amount of memory when the path is calculated. In view of the disadvantages of Neo4 j and the structural characteristics, the improved bidirectional search A* algorithm is proposed. The improvement mainly has two points: the first point is to put forward the idea of dynamic search with the best node as the relative destination node; the second point is to compare the minimum estimated value of the two ends of the switch standard. At the same time, using a minimum binary heap structures that can be quickly sorted. The improved results are verified by experiments, and it is found that the improved algorithm has a good effect. |
PDF Full Text Request