海量数据离散化算法的并行设计与实现

连续属性的离散化是机器学习和数据挖掘的重要预处理步骤,如何高效处理海量数据连续属性离散化已成为急需要解决的问题。近年来兴起的Hadoop技术能够有效处理基于海量数据的应用。为此,设计和实现一种基于MapReduce编程模型的连续属性离散化并行算法,并给出算法设计的方法和策略。在保证离散效果的情况下,使用不同大小数据集在不同节点的集群环境下的实验结果表明,所设计的并行离散化算法具有较高的执行效率和较好的可扩展性,适合用于海量数据的快速离散化处理。     

一种离散点插值的新算法

提出了一种按离散测量点构造曲面的新方法,即对每一测量点定义一个矩形作用域,并在每一个作用域上构造一个特殊的Hermilte插值曲面,最后通过各作用域在高度上的叠加来构造一张插值曲面。证明了新算法的完备性和对测量点的依赖性,并通过实例计算证明了新算法的有效性。     

基于切片原理的海量点云并行简化算法

针对传统点云简化算法效率低且处理点数少的缺陷,结合快速成型领域的切片原理顾及特征计算复杂度低的特点,设计并实现了适合千万级海量激光雷达（LiDAR）点云的并行切片简化算法。该算法根据切片原理对点云模型分层并按照角度排序,利用NVIDA的统一计算设备架构（CUDA）和可编程图形处理器（GPU）高度并行的性能优势,使用GPU多线程高效并行地执行单层切片点云简化,提高了算法效率。最后,应用3组不同数量级点云模型分别进行简化对比实验。实验结果表明：在保持模型特征与压缩比不变的情况下,所提算法效率高出传统基于CPU的串行切片算法1～2个量级。     

双线性插值算法及其并行实现

双线性插值算法是放大图像的一种有效算法,但是随着图像放大比例的增加,该算法的处理速度比较慢,所以基于这种现状,该文提出了双线性插值算法的一种并行实现方法,为高效快速的放大图像提供了解决方案。实验结果表明,并行后的算法能够有效的提高处理图像的速度和效率。     

基于GPU的实时光线投射算法

介绍了一种基于GPU（可编程图形处理单元）的快速实时光线投射算法。为满足大规模体数据集的绘制要求,利用当前GPU的新特性,直接将体数据作为纹理载入显存,采用预积分分类方法在GPU中对体数据进行重采样和分类,避免了计算机主内存与GPU纹理内存之间数据交换的瓶颈问题;利用硬件支持的三维纹理和片元着色器,实时计算每个体素的梯度,实现高质量的光照,保证高质量的图像绘制效果。实验结果表明该方法在医学三维数据场可视化中,能够实时、高效地生成高质量的交互式体可视化图像。     

基于并行数据库的海量商务数据管理系统研究

为了使海量商务数据得到高效、稳定、安全的处理,提出了一种针对基于并行数据流技术的海量数据管理系统,详细探讨了该系统中并行数据加载模块和并行数据查询模块的关键技术及具体体系结构,并对其中的并行查询技术提出相关的优化方案。     

并行海量信息处理中间件的研究与实现

数据库中间件技术已成为构建大规模海量信息处理系统的重要途径,本文研究并实现了一个并行海量数据库中间件,实现了海量数据的高性能并行加载和查询,满足TB量级的海量信息处理应用需求。     

基于多核并行的海量数据序列模式挖掘*

为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与其他处理器核协同,以最终获得所有的全局序列模式。算法通过并行局部归约技术消除了局部序列的重复生成与计算,并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。     

基于Hadoop平台的海量文本分类的并行化

文本分类是信息检索与数据挖掘的研究热点与核心技术,近年来得到了广泛的关注和快速的发展。近来年 随着文本数据呈指数增长,要有效地管理这些数据,就必须在分布式环境下用有效的算法来处理这些数据。在Ha- doop分布式平台下实现了一简单有效的文本分类算法—TFIDF分类算法,即一种基于向量空间模型的分类算法, 它用余弦相似度得到分类结果。在两个数据集上做了实验,结果表明,这一并行化算法在大数据集上很有效并可以在 实际领域中得到良好的应用。     

快速离散化双线性插值算法

双线性插值算法在数字图像处理中有广泛的应用.它具有比最近邻点法更好的连续性,但计算速度慢.为提高其计算速度,提出了离散化双线性插值算法.把像素分割成子像素,用双线性插值函数计算子像素中心坐标处的像素值,可以得到每一个子像素的卷积函数C,用C来代替双线性插值函数.理论分析表明离散化算法减少了加法和乘法的浮点运算次数.通过图像旋转实验表明该算法与双线性插值算法相比计算速度有较大的提高,连续性略有损失,图像质量基本相同.     

一种基于行列法离散点边界搜索算法*

平面上构建离散点的边界在地理信息系统(GIS)中应用广泛,提出了基于行列法的平面离散点边界搜索的新算法,目的是解决平面离散点边界问题,通过确定步长大小,按步长对离散点分别进行行搜索和列搜索,得到离散点的边界曲线,介绍了行列边界算法的基本思想和实现过程。该算法能够正确地搜索包含凹凸特征的离散点边界,与传统边界生成算法相比,它具有通用、实现简单等特点。该算法在油田GIS领域边界划分中得到了很好的应用,能够准确地构建油田边界。     

利用离散边界点判断的反向最远邻查询算法

目前大部分的反向最远邻查询方法对查询点是否存在反向最远邻的情况不进行判断,当查询点不存在反向最远邻的结果集时,也进行全部的操作,增加了查询消耗。针对这种情况,提出了利用离散边界点判断查询点是否存在反向最远邻结果集的方法,利用离散边界点、四分邻域区和半平面修剪策略进行过滤操作,并验证过滤后得到的结果集中数据点的有效性。实验测试了查询点的位置对查询的影响和数据集的大小以及数据分布对查询的影响,并与利用凸包判断的方法进行了对比分析。实验结果表明,当查询点不是离散边界点时,查询消耗几乎为0,当查询点移动到边界时,查询消耗增加。实验表明提出的方法可以得到查询点的反向最远邻结果集。     

基于薄板样条插值算法的巨幅影像分块并行处理

薄板样条函数是空间插值中的一种重要方法。对于巨幅影像数据使用薄板样条函数进行空间插值时,可能会出现运行时间太长,以及计算机内存空间不足或程序运行无响应的问题。针对这些问题,根据薄板样条函数光滑、连续的特点,基于GDAL开源函数库,提出对巨幅影像数据的分块读取,在块内利用并行技术求解线性方程组,确定薄板样条函数,最后进行空间插值的方法。结果表明,该方法可以有效的解决这些问题。     

一种新的区域图像插值算法

针对传统的3种图像插值算法在插值后分别存在灰度不连续、轮廓模糊、计算量大等问题,提出了一种新的区域插值算法。该算法先对图像依据纹理平坦或复杂进行区域的相对划分,然后根据待插值点在源图像中所属的区域对应地使用不同的插值算法。与一些典型插值算法进行仿真比较,验证了该算法在基本不改变插值精度的前提下,可以有效地降低运算时间。     

A new parallel algorithm for parsing arithmetic infix expressions

A new parallel algorithm for transforming an arithmetic infix expression into a par se tree is presented. The technique is based on a result due to Fischer (1980) which enables the construction of the parse tree, by appropriately scanning the vector of precedence values associated with the elements of the expression. The algorithm presented here is suitable for execution on a shared memory model of an SIMD machine with no read/write conflicts permitted. It uses O(n) processors and has a time complexity of O(log²n) where n is the expression length. Parallel algorithms for generating code for an SIMD machine are also presented.     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.     

解离散系数滤波器设计问题的分支定界算法

基于离散系数滤波器设计问题已有的半定规划松弛模型,利用文献[6]的方法给出了该问题的二次规划松弛模型,该模型能给出比半定规划模型更好的界,然后运用分支定界方法求解该模型。与随机扰动方法相比,该方法能得到一个性能更好的次优解,对于精度要求较高的滤波器设计问题,这种方法非常有效,并通过了仿真实验的证实。     

Univied Parallel Lattice Structures for Block Time—Recursive Real—Valued Duiscrete Gabor Transforms

In this paper,the 1-D real-valued discrete Gabor transform(RDGT)proposed in the previous work and its relationship with the complex-valued discrete Gabor transform(CDGT)are briefly reviewed.Block time-recursive RDGT algorithms for the efficient and fast computation of the 1-D RDGT coefficients and for the fast reconstruction of the original signal from the coefficients are developed in both critical sampling and oversampling cases.Unified parallel lattice structuires for the implementation of the algorithms are studied.And the computational complexity analysis and comparison show that the proposed algorithms provide a more efficient and faster approach to the computation of the discrete Gabor transforms.     

一种基于CUDA的并行多目标进化算法

传统的多目标进化算法多是基于Pareto最优概念的类随机搜索算法,求解速度较慢,特别是当问题维度变高,需要群体规模较大时,上述问题更加凸显。这一问题已经获得越来越多研究人员以及从业人员的关注。实验仿真中可以发现,构造非支配集和保持群体多样性这两部分工作占用了算法99%以上的执行时间。解决上述问题的一个有效方法就是对这一部分算法进行并行化改造。本文提出了一种基于CUDA平台的并行化解决方案,采用小生境技术实现共享适应度来维持候选解集的多样性,将多目标进化算法的实现全部置于GPU端,区别于以往研究中非支配排序的部分工作以及群体多样性保持的全部工作仍在CPU上执行。通过对ZDT系列函数的仿真结果,可以看出本文算法性能远远优于NSGA-Ⅱ和NPGA。最后通过求解油品调和过程这一有约束多目标优化问题,可以看出在解决化工应用中的有约束多目标优化问题时,该算法依然表现出优异的加速效果。