季长清,余　胜,王宝凤,陶　帅,汪祖民,王润方

(1. 大连大学 物理科学与技术学院,辽宁 大连 116622；2. 大连大学 信息工程学院,辽宁 大连 116622)



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

季长清1,2,余胜1,王宝凤2,陶帅2,汪祖民2,王润方2

(1. 大连大学 物理科学与技术学院,辽宁 大连 116622；2. 大连大学 信息工程学院,辽宁 大连 116622)

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

关键词：最大双色反最近邻查询；倒排网格索引；移动云计算

近年来，随着移动定位技术(mobilepositioningtechnology,MPT)和地理信息系统(geographicinformationsystem,GIS)等技术的发展，空间数据查询技术受到学术界的广泛关注.反最近邻(reversenearestneighbor,RNN)查询[1-5]作为空间数据查询技术中最重要的查询技术之一，学术界对该查询技术展开了深入研究，已提出了多种用于解决RNN查询问题、双色反最近邻(bichromaticreversenearestneighbor,BRNN)查询……