Research On Methods For Mnn Query And Maxbrnn Query In Road Networks

Spatial databases is a hot research field in recent years, while reverse nearest neighbor query has been extensively studied as an important operator in spatial query. With further research, a variety of methods for query based on reverse nearest neighbor were proposed to satisfy new requirement, such as mutual nearest neighbor query and maximizing reverse nearest neighbor query. But the methods for the two queries can not be suitable for the services which provided in road networks as they are currently limited to European space. So, this paper studied mutual nearest neighbor query and maximizing reverse nearest neighbor query in road networks.Firstly,this paper analyzes the deficiency of mutual nearest neighbor query that the query can only be used in European space. And the problem of mutual nearest neighbor query in road networks is proposed in this paper. To address this problem, the paper provides a fundamental algorithm that retrieves k1 nearest neighbors of q as candidate objects and then removes the false misses. Based on it, an optimal algorithm is proposed, which can remove some false misses directly according to the count of mark points which fall on the edge of shortest path between object and query.Secondly,this paper analyzes the deficiency of maximizing bichromatic reverse nearest neighbor query that the query can only be used in European space. And the problem of optimal location query in road networks is proposed in this paper. To address this problem, effective point set of all single-customer point set and all boundary points are found with the Dijkstra algorithm. All boundary points are queried to determine the multi-customer point set whose effective point set isn't empty. After the weight sum of all customer points in the multi-customer point set is got, the effective point set of the multi-customer point set with the maximum weight sum is calculated. Based on this, the optimal location set is found. Then two optimal strategies are proposed in order to improve efficiency.Finally, the methods for two queries proposed above are tested by synthetic data set and real data set. The effectiveness and practicality of two methods are verified through the experiment.