Research On K Nearest Neighbor Trajectory Query On Road Networks

With the mature of wireless communication, mobile computation and location position technologies, a variety of location-based service applications come to our life because of rapid demand. Recently, researchers focus on location-based queries, especially k nearest neighbor (k-NN) query. And many k-NN query methods have been proposed. The query on spatial database can be divided into two species:the one based on the Euclidean space and the one based on road network. Actually, queries on road network are more meaningful. Therefore, users desire an efficient method for finding the k nearest neighbor trajectories on road network.The thesis presents aggregate k nearest neighbor trajectory query method which can update the results (UANNT). And to solve the problem that candidate trajectories are generated slowly on skewed dataset, grouping k nearest neighbor trajectory query algorithm (k-GNNT) and qualifiers-based k nearest neighbor trajectory query algorithm (k-ANNT*) are presented. The main contributions of this thesis are summarized as follows:First, the thesis presents k nearest neighbor trajectory query method which can update the results. A query trajectory is defined as a points set. Through candidate generation and candidate verification, k nearest neighbor trajectory can be gotten. When users move through the query trajectory, the proposed algorithm can update the trajectory results, which can get the k nearest neighbor trajectory of remaining trajectories without extra candidate generation.Second, when a query trajectory contains outliers in skewed dataset, its matching pairs popped from global min-heap will be blocked, which makes the candidate trajectories be generated slowly. If the query trajectory contains more points, query performance will be more affected. To solve the problem, the thesis proposes two improved algorithms:k-GNNT and k-ANNT*.k-GNNT algorithm divides query trajectories into several groups to reduce the size of global min-heap, so blocking can be solved. Then k nearest neighbor trajectories can be found through the evaluation function.k-ANNT* algorithm’s core is to generate more tight candidate trajectory set by filling up missing matching pairs. When the number of the missing pairs reaches the threshold, k-ANNT* finds the missing pair and push it to candidate set. It will reduce some useless matching pairs popped from the global min-heap.Finally, the theoretical analysis and experimental evaluations show that the k nearest neighbor trajectory query algorithms proposed by the thesis are accurate and efficient on different datasets.