论文部分内容阅读
Voronoi图是一种按距离进行空间划分的基础数据结构,反应的是一种同等对待所有生成元的理想状态,但在实际应用中,生成元的影响范围受各种因素的影响,因此需在普通Voronoi图的基础上,对生成元赋予权重,构成加权Voronoi图。加权Voronoi的生成方法主要分为矢量法和栅格法。矢量法计算精度高,但数据结构复杂,处理线状和面状生成元较困难。当面临海量复杂的实际地图数据时,矢量方法不能很好地满足现实需求。栅格法虽然生成精度受到限制,但可以进行任意生成元的构建,能较好地处理复杂空间实体。另外,实际地图数据呈现大规模、海量化趋势,串行的栅格方法计算效率不高,并行化处理为其提供了一个有效的改进和优化方案。传统的Voronoi图并行方法通常是基于MPI、OpenMP、GPU等并行环境,虽然能够高效并行地生成Voronoi图,但受到底层配置和实现细节等因素的限制,而MapReduce因其高可靠性、高效率且能部署于廉价硬件设备等优点,简化了分布式程序设计,提高了计算性能,能够较好地解决大规模数据的Voronoi图计算问题。因此,本文对加权Voronoi图在MapReduce模型下的并行生成算法及其应用进行了深入研究,主要工作包括：(1)对加权Voronoi图的基本概念、应用、生成算法等相关理论进行了阐述,探讨了Hadoop平台的相关技术,为后续研究提供了理论指导。(2)针对传统加权Voronoi图栅格生成算法计算效率不高的缺陷,提出了一种基于MapReduce模型的加权Voronoi图并行算法,并在Hadoop集群上对算法的加速比和可扩展性进行了实验分析。(3)本文将加权Voronoi图应用于超市推荐和污水处理厂规划布局问题。针对超市推荐问题,以大众点评网的超市用户评分数据为依据,给出了一种综合多种用户评价指标的权重确定方法,应用加权Voronoi图,为用户推荐最优的大型综合性超市。针对污水处理厂规划布局问题,通过将断裂点模型中的“规模”参数引入到加权Voronoi图中,构建了基于加权Voronoi图的污水处理厂的责任区域界定模型,为污水处理厂的规划布局提供参考。