The Study On Multiple Tpyes Reverse Nearest Neighbor Queries

With the wide application of spatial databases and the development of computing resources, people have increasing higher expectation on location-based services (LBS), which means that must handle more complex queries. Nearest neighbor (NN) and reverse nearest neighbor (RNN) queries are very important queries in LBS. NN queries is to find the nearest object of the inquiry points。Depending on NN, RNN search is looking for points which have the query point as their nearest neighbor, in other words, the query point is a NN of all points of results set. RNN search is typically used by market analysis and business decision-making systems. Reverse nearest neighbor search technology provide decision supporting and therefore have considerable commercial value.Classic reverse nearest neighbor queries do not take into account more than one feature type, so their application are limited in the decision-making system, and sometimes they cannot meet the user’s individual requirements. Although existing multiple type reverse nearest neighbor (MTRNN) queries account for many kinds of featrue tpyes, they do not consider the influence factors between the feature types and cannot reflect the actual situation of the real. Therefore, the further expansion and improvement of MTRNN queries will be very meaningful.Based on analysis and summary of the merits and demerits in MTRNN query algorithm, the further studies made in this article as follows:First, Accroding to the problem that filtering policies for existing MTRNN query are not efficient by not considering the influence factors between the feature types, a new queries method WMTRNN, named weighting multiple types reverse nearest neighbor is presented. It based on the weighted influence interactions among feature types, used R-tree index structure combining the closing and opening region pruning strategy, which satifying to the LBS’s feature requirements. Simulation experimental results show that the WMTRNN algorithm can be more accurate on the query result, and the filtering effect is significant in the context of large data.Second, considering the determining objects in MTRNN queries cannot meet the individual requirements and some complex scenarios in today’s computing environment, the new queries method PMTRNN for uncertain objects, called probabilistic multiple types reverse nearest neighbor is proposed. It uses a new pruning strategy combining the probability pruning and sptial pruning based on probabilistic model of discrete random variables. Simulation experiments show that the PMTRNN query algorithm is able to finish queries on uncertain database (generated by uncertain objects) in a reasonable time. The query efficiency is effectted by the size of an uncertain object, the probability threshold, the number of instances of an uncertain object and the depth of probability pruning.