K Nearest Neighbor Query Optimization Based On Historical Result Cache On Road Network

K Nearest Neighbor(kNN)in the road network returns the k points of interest(POI)with the shortest path distance from the query point,which is one of the important technologies based on Location Based Services(LBS).Therefore,it has attracted the attention and research of scholars.At present,the kNN query methods in the road network can be roughly divided into two categories.One is the online expansion method with no index structure.The expansion method similar to Dijkstra is mostly used,which requires a lot of online calculation.The other is to build an index structure based on the characteristics of kNN queries,which requires pre-calculation of the shortest path and storage space of the node.The focus of existing methods is on the response efficiency of a single query.While in practical applications,a large number of query requests have some queries with the same or similar positions,and the query results are also the same or similar,making use of these historical results to assist in answering new questions.The inquiry request becomes possible.According to the characteristics of kNN query,this paper focuses on the optimization method of kNN query processing based on historical result cache.A shared detection model is proposed,which uses the path of historical kNN results to calculate shared prefix nodes,so that more nodes can share historical kNN results,and improve the utilization of cache results.Propose a cache storage structure based on hash,which not only guarantees the storage of detailed historical results but also supports efficient query;in order to save the cache space and improve the reuse rate of the historical results as much as possible,a cache revenue model is proposed.The cache revenue is calculated based on shared detection and query statistics,and there are options Store historical kNN results in a flexible manner.Due to the limited cache space,a cache construction and update algorithm based on the revenue model is proposed to update the historical results of kNN in the cache.In order to verify the effectiveness and efficiency of the kNN historical query result caching method and multiplexing technology proposed in this paper,this paper compares the proposed cache-based k-nearest neighbor query algorithm(CBkNN)with the original A large number of comparisons were made between the online expansion algorithm INE using cache technology and the cache-based MkNN.Experimental results show that the CBkNN algorithm is 40%faster than the INE algorithm without cache,and the query response time of CBkNN is 20%less than that of the MkNN algorithm with cache.