基于MapReduce的加权Voronoi图并行算法设计及应用

针对大规模数据的加权Voronoi图实现的复杂性和计算精度低问题, 采用欧氏距离法, 设计和实现了一种基于MapReduce编程模型的并行栅格加权Voronoi图的生成算法, 并将其成功应用于石家庄桥东区超市的推荐服务。该算法计算精度高, 同时可适用于任意点、线、面及复合发生元的加权Voronoi图的计算。实验结果表明, 算法在处理大规模栅格数据时能明显提高栅格Voronoi图的生成速度, 并能为用户推荐综合因素优选的超市。     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

基于Voronoi图的植物叶脉建模方法

提出了一种生成树叶叶脉模型的算法.叶片轮廓用B样条曲线绘制,分形LS文法用来实现对第一、二级叶脉的模拟,并使用Voronoi图对叶面进行网状分割生成第三级细脉.在生成Voronoi图的过程中,采用基于Poisson-disk模型的Dart-throwing随机采样算法得到均匀分布的Voronoi点集.仿真结果验证了该算法的可行性.     

基于MapReduce的Bagging决策树优化算法

针对经典C4.5决策树算法存在过度拟合和伸缩性差的问题,提出了一种基于Bagging的决策树改进算法,并基于MapReduce模型对改进算法进行了并行化。首先,基于Bagging技术对C4.5算法进行了改进,通过有放回采样得到多个与初始训练集大小相等的新训练集,并在每个训练集上进行训练,得到多个分类器,再根据多数投票规则集成训练结果得到最终的分类器;然后,基于MapReduce模型对改进算法进行了并行化,能够并行化处理训练集、并行选择最佳分割属性和最佳分割点,以及并行生成子节点,实现了基于MapReduce Job工作流的并行决策树改进算法,提高了对大数据集的分析能力。实验结果表明,并行Bagging决策树改进算法具有较高的准确度与敏感度,以及较好的伸缩性和加速比。     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究，提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分，然后再根据对偶特性构建Voronoi图．该算法健壮性很高，适用于处理各种非完全共面三维点集．     

基于Delaunay三角剖分生成Voronoi图算法

针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。     

F1owS:一种MapReduce数据流公平调度方法

MapReduce Job的调度机制一直是学术研究的热点。在分析MapReduce数据流调度模型的基础上,提出一种面向MapReduce数据流的公平调度方法FlowS。该方法采用数据流池来分配资源以保证MapReduce数据流的隔离性,并且采用数据流池动态构建算法来确保资源的公平分配。实验表明,该调度方法可以有效提高Hadoop集群对MapReduce数据流的处理效率。     

基于MapReduce的三元N-gram算法的并行化研究

大规模语料库的训练是使用三元N-gram算法进行中文文本自动查错中一个重要的基础工作。面对新媒体平台每日高达百万篇需处理的语料信息,单一节点的三元N-gram语言模型词库的构建存在计算瓶颈。在深入研究三元N-gram算法的基础上,提出了基于MapReduce计算模型的三元N-gram并行化算法的思想。MapReduce计算模型中,将运算任务平均分配到m个节点,三元N-gram算法在Map函数部分的主要任务是计算局部字词分别与其前两个字词搭配出现的次数,Reduce函数部分的主要任务是合并Map部分统计字词搭配出现的次数,生成全局统计结果。实验结果表明,运行在Hadoop集群上的基于MapReduce的三元N-gram并行化算法具有很好的运算性和可扩展性,对于每日120亿字的训练语料数据集,集群环境下该算法得到训练结果的速率更接近于线性。     

基于最小生成树的大规模数据分类模型及其MapReduce实现

数据的快速增长,为我们提供了更多的信息,然而,也对传统信息获取技术提出了挑战。这篇论文提出了MCMM算法,它是基于MapReduce的大规模数据分类模型的最小生成树（MST）的算法。它可以看做是介于传统的KNN方法和基于聚类分类方法之间的模型,旨在克服这两种方法的不足并能处理大规模的数据。在这一模型中,训练集作为有权重的无向完全图来处理。顶点是对象,两点之间边的权重是对象间的距离。这一距离,不同于欧几里得距离,它是一个特定的距离度量。这样,可以找到图中最小生成树集,其中,图中每棵树代表一个类。为了降低时间复杂度,提取了每棵树中最具代表性的点来代表该树。这些压缩了的点集,可以通过计算无标签对象和它们之间的距离,来进行分类。MCMM模型基于MapReduce实现并且部署在Hadoop平台。该模型可扩展处理大规模的数据,是因为Hadoop支持数据密集分布应用,并且这些应用可以和数以千计的节点和数据一起运作。另外,MapReduce 和Hadoop能在由商品机组成的集群上很好的运行。MCMM模型使用云平台并且通过使用MapReduce 和Hadoop进行云计算是有益处的。实验采用的数据集包括从UCI数据库得到的真实数据和一些模拟数据,实验使用了4000个集群。实验表明,MCMM模型在精确度和扩展性上优于KNN和其他一些经常使用的基础分类方法。     

基于Voronoi 最小邻近点集的Delaunay 三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay 三角化 生成算法,该算法以Delaunay 三角形及其对偶Voronoi 图的局部性特征为基础,通过在局部 搜索最小Voronoi 邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提 高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用 领域。     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。     

粗糙域Voronoi图离散生成算法研究

Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A‘算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度,对粗糙域下A’算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明,A’算法估价函数权值与粗糙域粗糙特性正相关,并以此获得r算法估价函数的最优权,大大降低了粗糙域Voronoi图离散生成算法的复杂度。     

A parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping

This paper presents a parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping. The binary tree splitting method is used to adaptively group the point set in the plane and construct sub‐Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in each group consumes the majority of time and that construction within one group does not affect that in other groups, the use of a parallel algorithm is suitable. After constructing the sub‐Voronoi diagrams, we extracted the boundary points of the four sides of each sub‐group and used to construct boundary site Voronoi diagrams. Finally, the sub‐Voronoi diagrams containing each boundary point are merged with the corresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experiments demonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function of the size of the point set, the number of processors, the average number of points in each block, and the number of boundary points. Copyright © 2013 John Wiley & Sons, Ltd.     

The Hausdorff Voronoi Diagram of Point Clusters in the Plane

We study the Hausdorff Voronoi diagram of point clusters in the plane, a generalization ofVoronoi diagrams based on the Hausdorff distance function. We derive a tight combinatorial bound on the structural complexity of this diagram and present a plane sweep algorithm for its construction. In particular, we show that the size of the Hausdorff Voronoi diagram is (n + m), where n is the number of points on the convex hulls of the given clusters, and m is the number of crucial supporting segments between pairs of crossing clusters. The plane sweep algorithm generalizes the standard plane sweep paradigm for the construction of Voronoi diagrams with the ability to handle disconnected Hausdorff Voronoi regions. The Hausdorff Voronoi diagram finds direct application in the problem of computing the critical area of a VLSI layout, a measure reflecting the sensitivity of the VLSI design to spot defects during manufacturing.     

Voronoi diagrams of set-theoretic solid models

The definition of a Voronoi diagram is extended to arbitrary set-theoretic solid models. A method for approximating such diagrams using recursive subdivision is described. The method relies on octrees, which have been used for computing the distances between whole solid models. Two- and three-dimensional images generated using the algorithm are presented     

Approximation of Generalized Voronoi Diagrams by Ordinary Voronoi Diagrams

A numerically robust algorithm for the ordinary Voronoi diagrams is applied to the approximation of various types of generalized Voronoi diagrams. The generalized Voronoi diagrams treated here include Voronoi diagrams for figures, additively weighted Voronoi diagrams, Voronoi diagrams in a river, Voronoi diagrams in a Riemannian plane, and Voronoi diagrams with respect to collision-avoiding shortest paths. The construction of these generalized Voronoi diagrams is reduced to the construction of the ordinary Voronoi diagrams. The methods proposed here can save much time which is otherwise necessary for writing a computer program for each type of generalized Voronoi diagram.     

Generating and updating multiplicatively weighted Voronoi diagrams for point,line and polygon features in GIS

A Voronoi diagram is an interdisciplinary concept that has been applied to many fields. In geographic information systems (GIS), existing capabilities for generating Voronoi diagrams normally focus on ordinary (not weighted) point (not linear or area) features. For better integration of Voronoi diagram models and GIS, a raster-based approach is developed, and implemented seamlessly as an ArcGIS extension using ArcObjects. In this paper, the methodology and implementation of the extension are described, and examples are provided for ordinary or weighted point, line, and polygon features. Advantages and limitations of the extensions are also discussed. The extension has the following features: (1) it works for point, line, and polygon vector features; (2) it can generate both ordinary and multiplicatively weighted Voronoi diagrams in vector format; (3) it can assign non-spatial attributes of input features to Voronoi cells through spatial joining; and (4) it can produce an ordinary or a weighted Euclidean distance raster dataset for spatial modeling applications. The results can be conveniently combined with other GIS datasets to support both vector-based spatial analysis and raster-based spatial modeling.