移动云计算环境下的双色反近邻查询算法

Bichromatic reverse nearest neighbor query algorithm in environment of mobile cloud computing

研究在移动云计算环境下的最大双色反最近邻查询优化问题,设计新的高效的双色反最近邻查询算法——SILM算法.SILM算法是基于MapReduce框架下的倒排网格索引结构,在Map函数中对分片数据区域使用PCT轮圈算法.对包含在圆区域内或与圆相交的网格的权值记为1,在Reduce函数中使用网格处理算法对分片数据区域进行扫描及合并,对重叠的网格的权值进行累加,输出网格空间中权值最大的网格区域.SILM算法可以在多计算节点上进行分布式计算,更适合于在移动云计算环境下处理大规模并行查询请求.通过实验对SILM算法的效率进行验证.实验结果表明,当数据量较大（数据点个数大于2.0×10~6）时,SILM算法的查询效率是目前解决最优选址问题最佳算法的2倍.

A new and high-efficiency bichromatic reverse nearest neighbor query algorithm - SILM algorithmwas designed based on the inverted grid index structure within the MapReduce framework by thestudy on max bichromatic reverse nearest neighbor query optimization problem in the environment of mobilecloud computing. For the split data area, PCX round algorithm was applied in the Map function andthe weight of circular area or grids intersected with the circle was denoted as 1. Then the split data areaswere scanned and merged by grid processing algorithms in the Reduce function, and the weights of overlappinggrids were accumulated. The grid area with the largest weight of the grid space was outputted.SILM algorithm can not only realize the distributed computation on multiple calculation nodes, but alsocomplete the large-scale parallel query requests in mobile cloud computing environment. The experimenton the high-efficiency of SILM algorithm was conducted. Results show that the efficiency of SILM algorithmis 2 times more than that of the best algorithm on solving the optimal location problem when thenumber of data points is larger than 2. 0 × 106.