Study And Implementation On Diversity-aware Moving K-Nearest-Neighbor Queries

In recent years,with the development of location based service and the popularity of smart devices,spatial query technology has a deep impact on daily life.However,the query technology is not only confined to the familiar neighbor query.In order to better reflect the actual application,moving query and diversity-aware query gradually become the research content.In existing studies,moving query related research involves only neighbor query and diversity related queries only has snapshot query which can't solve the continuous queries.Aiming at the problems above,this thesis introduces the study and realization of diversity-aware moving k nearest neighbor query technology.We first give a formalized definition about the scoring function of diversity and correlation before presenting moving query algorithms.Through the function we can determine the score of a set of points and the scored highest collection can be used as the query results.Then we introduce two diversity-aware k nearest neighbor query algorithms.One is an accurate query algorithm,another is a 2-approximate query algorithm.In view of the two diversity-aware query algorithms we propose three diversity-aware moving query algorithms.First of all,we propose the accurate maintenance query algorithm 1-DMkNN which is based on the accurate query algorithm and the results are accurate in the process of moving.This thesis defines the concept of activity radius,through which to maintain the order of the result set in priority queue and get query results from the head of this queue.In addition,due to the long execution time of accurate algorithm,we propose a pruning algorithm based on the upper bound of the value of diversity,and through a lot of experiments to verify the effectiveness of the 1-DMkNN algorithm and accuracy.Second,we propose the approximate maintenance query algorithm p-DMkNN which is based on accurate query algorithm and the results are approximate in the process of moving.The algorithm uses safe region to ensure the area of the query results can meet the degree of approximation.The construction of the safe region only depends on the current query results.In this thesis,we verify the effectiveness and accuracy of the p-DMkNN algorithm through a large number of experiments.Finally,based on approximate query algorithm we propose 2-DMkNN algorithm which is the accurate maintenance algorithm of query results.The result of the query result meets 2 approximate ratio.The algorithm maintains the result set by queue and activity radius in the process of query point moving and we get the result set from the queue.In this thesis,we verify the effectiveness and accuracy of the 2-DMkNN algorithm through a large number of experiments.In all,this thesis combines the moving query with the diversity-aware queries and puts forward three kinds of maintaining diversity k nearest neighbor query algorithm which can be used in the process of query point movement to maintain the diversity of query results.We verify the effectiveness and accuracy through a large number of experiments of the three algorithms.