为了改进现有的组反k最近邻查询算法的查询速度与准确度,提出了一种基于Voronoi图的组反k最近邻查询方法(group reverse k nearest neighbor guery method based on Voronoi diagram,V_GRk NN)。该方法获得的结果集是将这组查询点中任...为了改进现有的组反k最近邻查询算法的查询速度与准确度,提出了一种基于Voronoi图的组反k最近邻查询方法(group reverse k nearest neighbor guery method based on Voronoi diagram,V_GRk NN)。该方法获得的结果集是将这组查询点中任意一点作为kN N的数据点集合,在实际应用中可以用来评估一组查询对象的影响力。该方法的特点是首先对查询点集Q进行优化处理,降低查询点数量对查询效率的负面影响;接着对数据点集P进行约减,缩小查询搜索范围;然后根据基于Voronoi图的剪枝策略对候选集进行过滤;最后经过精炼获得GRk NN查询的结果集。该方法在数据集处理阶段很大程度上提高了查询速度,在过滤、精炼阶段利用Voronoi图的特性提高了查询的准确性。理论研究和实验表明,所提方法的效率明显优于可选的已有方法。展开更多
Reverse k nearest neighbor （RNNk） is a generalization of the reverse nearest neighbor problem and receives increasing attention recently in the spatial data index and query. RNNk query is to retrieve all the data po...Reverse k nearest neighbor （RNNk） is a generalization of the reverse nearest neighbor problem and receives increasing attention recently in the spatial data index and query. RNNk query is to retrieve all the data points which use a query point as one of their k nearest neighbors. To answer the RNNk of queries efficiently, the properties of the Voronoi cell and the space-dividing regions are applied. The RNNk of the given point can be found without computing its nearest neighbors every time by using the rank Voronoi cell. With the elementary RNNk query result, the candidate data points of reverse nearest neighbors can he further limited by the approximation with sweepline and the partial extension of query region Q. The approximate minimum average distance （AMAD） can be calculated by the approximate RNNk without the restriction of k. Experimental results indicate the efficiency and the effectiveness of the algorithm and the approximate method in three varied data distribution spaces. The approximate query and the calculation method with the high precision and the accurate recall are obtained by filtrating data and pruning the search space.展开更多
文摘为了改进现有的组反k最近邻查询算法的查询速度与准确度,提出了一种基于Voronoi图的组反k最近邻查询方法(group reverse k nearest neighbor guery method based on Voronoi diagram,V_GRk NN)。该方法获得的结果集是将这组查询点中任意一点作为kN N的数据点集合,在实际应用中可以用来评估一组查询对象的影响力。该方法的特点是首先对查询点集Q进行优化处理,降低查询点数量对查询效率的负面影响;接着对数据点集P进行约减,缩小查询搜索范围;然后根据基于Voronoi图的剪枝策略对候选集进行过滤;最后经过精炼获得GRk NN查询的结果集。该方法在数据集处理阶段很大程度上提高了查询速度,在过滤、精炼阶段利用Voronoi图的特性提高了查询的准确性。理论研究和实验表明,所提方法的效率明显优于可选的已有方法。
基金Supported by the National Natural Science Foundation of China (60673136)the Natural Science Foundation of Heilongjiang Province of China (F200601)~~
文摘Reverse k nearest neighbor （RNNk） is a generalization of the reverse nearest neighbor problem and receives increasing attention recently in the spatial data index and query. RNNk query is to retrieve all the data points which use a query point as one of their k nearest neighbors. To answer the RNNk of queries efficiently, the properties of the Voronoi cell and the space-dividing regions are applied. The RNNk of the given point can be found without computing its nearest neighbors every time by using the rank Voronoi cell. With the elementary RNNk query result, the candidate data points of reverse nearest neighbors can he further limited by the approximation with sweepline and the partial extension of query region Q. The approximate minimum average distance （AMAD） can be calculated by the approximate RNNk without the restriction of k. Experimental results indicate the efficiency and the effectiveness of the algorithm and the approximate method in three varied data distribution spaces. The approximate query and the calculation method with the high precision and the accurate recall are obtained by filtrating data and pruning the search space.
