Efficient Methods For Reverse K-Nearest Neighbor Query On The Multidimensional Objects

With the rapid dvelopment of mobile devices and wireless internet, location basedapplications are getting popular. The spatial query technique plays an important role inlocation based applications. The cost of querying time is one of the key criterions to evaluatedatabase query systems. The spatial database always has large amount of data which makestraditional database queries difficult. In recent years, the research on spatial database queryingis arousing more and more interests and attentions.The application prospect of reverse k-nearest neighbor (RkNN) query in service industryis very broad and quite optimistical, and it has been quite an active area of spatial databasequeries in recent decades. A lot of scholars at home and abroad have carried on a large amountof research to RkNN query and its variants and proposed a lot of practical and effective querytechnique. But previous researches have some limitations, i.e., the low query efficiency andinability in multidimensional case, and can’t meet user various needs.We need to create index before we can query spatial database. In this paper, every datasetis indexed by an RC*-tree, which have made certain changes in R*-tree. It makes the indexstructure better suited for the proposed RkNN solutions. We need to pre-compute thecover-value for each node when the RC*tree is built. The cover-value of a node is the numberof the objects contained in the sub-tree rooted by this node.This paper makes a thorough research on reverse k-nearest neighbor query andcontinuous reverse k nearest neighbor query. And the corresponding solutions are given,namely RC-RkNN and RC-CRkNN. Both RC-RkNN query and RC-CRkNN query are basedon RC*-tree index structure.For reverse k-nearest neighbor query, this paper has sumed up the pruning essence andconnotation. RC-RkNN query adopts the two-step processing method: the filter stage and therefinement stage. Because most of the research hotpot of spatial database queries isconcentrated on the filter stage, the main contents researched in this paper is about the filterstage of the proposed RC-RkNN solutions. Two novel pruning heuristics lemmas aredeveloped in the filter stage and proved. Some examples are given to illustrate theapplications of two pruning heuristics. Database can be updated efficiently with RC-RkNN,and querying results can be retrieved accurately. The value of k in RC-RkNN can be choosenarbitrarily and RC-RkNN is applicable to the multidimensional case.For continuous reverse k nearest neighbor query, employ the filter-refinement-splitframework. In the filter stage, the two pruning heuristics of RC-RkNN are extended to adapt continuous reverse k nearest neighbor query, which has a moving query object and static dataobjects. In this paper, two extended pruning heuristics lemmas also are given and proved.inthe filter stage. And we concretely analyzes the usage methods of two extended pruningheuristics.In order to test the efficiency of RC-RkNN and RC-CRkNN, we carry out a series ofexperiments on four real-world datasets and several artificial datasets. For showing theefficiency of RC-RkNN, we make three different types of experiments. The simulation resultsdemonstrate that RC-RkNN need less querying time in comparison with other methods whenk is larger than6. Similarly, we also make four different types of experiments for continuousreverse k nearest neighbor query. Finally, through the analysis of experiment results, we foundout RC-CRkNN is obviously more efficient than other methods with varying lengths ofquering segments, different dimensions, different cardinalities and distribution of datasetswhen k is larger than4.