Query Algorithms In Semimetric Road Network

Spatial databases have become a hot research direction in the field of the database, in which road network as an important part has currently been widely applied in various map services, commercial online navigation systems and location-based query application. Querying in road network has got more and more attention. Due to the large number of roads, high density, cross frequent and complex characteristics of road network, how to efficiently query is crucial in road network.Query methods proposed in road network are mostly based on distance metric of network distance. Road network violates the property of triangle inequality while currency conditions of roads is considering, which is called semimetric road network. Due to the violation of the property of triangle inequality in semimetric road network, common index structure can not work effectively in the road network. The problem in querying in semimetric road network is great cost of time and precomputation. How to efficiently query in semimetric network is important and difficult.While querying in semimetric road network, efficient quering methods are proposed to deal with problem of great cost of time and precomputation. Firstly, due to great cost of directly querying in semimetric road network, we propose two methods to transform semimetric road network to metric one. One of the method is randomly deleted edges algorithm, which is proposed to transform semimetric road network to metric one and simply and easily to implement. But the information loss of randomly deleted edges algorithm is large. In order to transform semimetric road network to a metric one with minimal the information loss and reduce the cost of query process, which is an NP-hard problem, other heuristic algorithm is proposed. Sorting deleted edges algorithm can transform semimetric road network to metric one with approximately minimal information loss. Secondly, QM-tree index structure is proposed, which uses the property of triangle inequality to prune the subtree containing no candidates and ensure the correctness and efficiency of the queries. Thirdly, in the phase of querying, methods of range query and K-nearest neighbor query in semimetric road network are proposed. The phase of querying consists of two parts, namely the part of querying and the part of validating query results. The part of querying uses the triangle inequality to prune the subtree which is impossible to be query results to find query results quickly, ensuring the efficiency of queries. The part of validating query results validates the elements in the list pointed by pointer of the results of the query nodes and query nodes, which ensures the correctness of the query.Finally, many experiments on real data sets are made. Through analyzing and summarizing the experimental results, sorting deleted edges is proved to transform semimetric road network to a metric one with minimal the information loss; The methods based on QM-Tree efficiently and accurately deal with the range query and K nearest neighbor query in semimetric road network.