Research And Implementation Of K Nearest Neighbor Query Processing In Public Transportation Network

Existing electronic map applications,such as Baidu Map,AutoNavi Map and Google Map,only provide services such as "find the nearest k POIs nearby" or "provide bus plans from s to d",but cannot answer the question "find the first k POIs to arrive in a bus transfer".This type of query is to find k nearest neighbors（kNN）on the public transport network,that is,to return k POIs,these POIs arrive at the earliest time from the query location at a certain moment,and the number of transfers required is less than the constraints specified by users.There are often multiple routes between nodes in the public transportation network,and the combination of routes is more complex than that of the traditional road network.Therefore,the existing algorithm to solve the kNN problem in the road network cannot be directly applied to the environment of the public transportation network.In this paper,we first define the kNN query problem in public transportation network,and then propose two algorithms,TT-INE and TT-IER,respectively,based on the idea of incremental network extension and incremental Euclidean constraint.It is used to solve the problem of kNN query under dense and sparse POIs distribution.TT-INE algorithm is used for network query with POI intensive distribution.The node compression is used to reduce the scale of the road network,the path filtering is used to reduce the number of path combinations of node traversing,and the pruning strategy is used to reduce the query path.TT-IER is suitable for network query with sparse POI distribution.Based on Euclian environment,grid index is used to determine the position relationship between query point q and POI,heuristic shortest path calculation to improve the efficiency of shortest path calculation and POI precision and accurate final POI results to improve the efficiency of query.Comparison experiments based on real public transport networks in Beijing show that the response time of the TT-INE algorithm using pruning strategy is nearly two orders of magnitude less than that of the naive algorithm.When the POI to the number of sites ratio is 1%,the response time of TT-IER algorithm is one order of magnitude less than that of TT-INE.