论文部分内容阅读
随着GPS设备的不断普及，基于位置的服务逐渐走进我们的日常生活。反向k最近邻(Reverse k Nearest Neighbor, RkNN)查询作为基于位置服务的支持技术之一，已经成为当前的一个研究热点问题。RkNN查询检索的是以查询点为k最近邻的对象集合，目前研究主要集中在单色反向k最近邻查询上，而对于双色反向k最近邻查询研究较少，且现有的算法不能高效地处理查询发起者为一个集合的双色反向k最近邻查询问题。针对现有查询算法的不足，本文提出了一种基于集合的双色反向k最近邻查询——双色反向k最近邻联合查询(Bichromatic Reverse k Nearest Neighbor Combined query, CBRkNNquery)，并给出了高效的CBRkNN查询算法。首先，在分析和总结现有RkNN查询算法的基础上，本文提出了CBRkNN查询问题，并且给出了基于Finch的CBRkNN查询算法。算法首先根据查询集合构造出查询区域，然后检索出落入该区域内的用户构成候选集，最后对候选集中每个用户进行确认，排除错误的查询结果。实验验证了算法的高效性。其次，通过对基于Voronoi图的BRNN查询算法的深入研究，本文引入了影响区域的概念并提出了基于影响区域的CBRNN查询算法。算法将查询集合与Voronoi图结合，给出了组Voronoi图的定义。算法利用组Voronoi图构造出查询集合的影响区域，检索出落入该区域内的用户构成结果集。实验验证了基于影响区域的CBRNN查询算法比基于Finch的CBRNN查询算法效率更高。最后，本文引入k级影响区域的概念并利用该区域减小搜索空间，给出了基于k级影响区域的CBRkNN查询算法(k>1)。算法根据查询集合划分平面，引入凸多边形级别的定义，搜索出级别小于k的凸多边形构成k级影响区域，最后检索出落入该区域内的用户构成结果集。实验验证了基于k级影响区域的CBRkNN查询算法比基于Finch的CBRkNN查询算法效率更高。综上所述，本文针对现有BRkNN查询算法存在的局限性，创新地提出了基于查询集合的CBRkNN查询问题，并分别给出了基于Finch的CBRkNN查询算法、基于影响区域的CBRNN查询算法以及基于k级影响区域的CBRkNN查询算法(k>1)。本文从理论方面证明了算法的正确性，并且通过模拟实验验证了算法的高效性。