Research About Automobile Indexing Technology For Road Network In Location Based Service

With the development of satellite navigation、wireless communication and relative technology, there are a large numbers of location based service applications appear in all walks of life. Because the increasing number of cars bring the city huge traffic pressures, the location bases service for road network is the area which nation focus on and also been regarded as strategic advantage in future competition between nations. Moving object database is the data management center in such location bases service system. And moving object index is the core technology in moving object databases. Its performance directly affects the efficiency of moving object database. Obviously moving object index is hot research field.In Second Charpter: Classify previous work about index firstly, analysis the improvement strategies、advantages and disadvantages of performance of index. In third charpter: Take characteristics of the road network into account and establish a road-segment-based road network model. Analysis the advantages and disadvantages of R-Tree and Quad-Tree then propose main index structure based on double layer structure idea, Analysis the characteristic of morton encoding algorithm and hilbert encoding algorithm. propose the secondary indexes based on morton code and patricia Tree. Propose quick Morton encoding algorithm Call QMEA which based on mapping principle. In chapter 4, elaborate the algorithm based on index which proposed in charpter 3. In charpter 5, elaborate the design and implementation of a prototype system. In charpter 6, elaborate experiment which focus on index performance evaluation and analyzed the experiment result. This paper is organized in following order: Propose new index structure and encoding algorithm. elaborate algorithm based on the proposed index structure. Design and implementation of prototype System. Index performance and encoding algorithm evaluation and experimental results Analysis.The main works are detailed as follow:1、Focus on the shortcoming of popular index, The update efficiency and operating efficiency of index is not high. Propose an index called CNR(Constrained Network R-Tree) based on double layer idea. Improved the efficiency by adding auxiliary index structure like: hash table and list. Integrated CNR and Morton code to meet window query with efficient.In charpter 6, the experimental results show that.CNR has better update performance and cost less IO in trajectory query and windows query.2、Propose an index structure called MPT(Morton Patricia Tree) which is based on patricia Tree and binary Morton code. We improve the efficiency of MPT index structure by reforming structure of patricia tree and relative algorithm. Based on the characteristics of Morton code, we integrate index structure and binary morton code to meet the need of neighbor query, and propose the nearest neighbor search algorithm based on MPT at the same time. MPT gain the capability of range query by dividing the two-dimensional space into different size cubes according to predefined rules and converting each cube into Morton code. We analyze the reason why range query error occur and put forward the solution. In charpter 6, the experiment result show that the search speed of MPT index structure is faster than that Hash table and trie tree and so on. The nearest neighbor query based on MPT is more efficient than that based on R-Tree.3、Propose quick morton encoding algorithm Call QMEA which based on mapping principle. Time complexity of QMEA is constant order. In charpter 6, the experiment result show that: QMEA is more efficient than the iterative partitioning encoding algorithm in practical4、Design and build the prototype system. The prototype system has the function like: trajectory query, range query, trajectory prediction.etc.The efficiency of index can test by importing the index modules into prototype system...