The Query Method Of Reverse K Nearest Neighbor Query In Spatial Database

With the increasingly popular of spatial databases, location based services (LBS)are increasingly popular way in the data storage location-based services, the spatialdatabase technology is very important, there are a variety of techniques in spatialdatabase query, where the RkNN (Reverse k Nearest Neighbor) queries for spatialdatabase technology is of great significance, the so-called RkNN query point is to findthe point which its pre-k neighbor points include the query data. The research forRkNN not only in uncertain data but also in certain data. No matter for the certaindata or uncertain data, the results are generally set by pruning–verification phase. Thereverse k nearest neighbor has more intelligent for decision-making system, datamining and has great use value to optimize the allocation of resources.For the reverse k nearest neighbor, the reaearch usually include certain database anduncertainy database, when the query data is certain, if the query data have morenumbers, the traditional query is through the query for each query points in turn, butthis method need high time complexity. When the query data is uncertainy, we givethe research with probability threshold value k neighbor query, the traditionalprobabilistic threshold k neighbor query when k is bigger is low efficiency. Thus, westudy the k neighbor under the certain data and uncertain data query has greatsignificance.In this paper, for the index database, we have modified the traditional R*-treeindex, base the R*-tree, we add the completion of the statistical number of nodesMBR to form RN-tree, the purpose for doing so can is to let the traverse in databaserapidly, reduced data during query traversal, improved I/O performance. For the groupreverse k nearest neighbor and probability reverse k nearest neighbor on uncertaindata, we use the minimum coverage circle to cover all the possible data, then, weconsider the minimum circle as the whole data. If there exists more than one query data in the reverse k nearest neighbor, in thissituation we research it as group RkNN query, we propose two pruning strategies,using the two strategies can reduce the candidates in the next verification phase, thenthe running time can reduce, with the help of the two strategies, especially for thelarger k, the experiment result is nice, because in the process of the pruning strategies,we use the RN-tree for keeping the data, as a result, little data can be considered in thenext phase.For the probabilistic reverse k nearest neighbors query processing on uncertainData, we adopt pruning-verification two phases for acquiring the finial result sets, thepruning phase include we propose an algorithm filter PINCH, with the geometricrelationship with the uncertain data query point to form a convex polygon area, anypoint in the interior of a convex polygon data points are possible belong to the finalresults. However any data outside the data does not meet the requirements.Meanwhile, we combine the relationship with the query data and each MBR and theFINCH to form the pruning filter algorithm.