一种基于Map Reduce的关联规则挖掘算法

提出了一种基于Map Reduce模型的Apriori改进算法,该算法利用Map Reduce模型分布式处理海量的输入数据,结合Apriori算法,得到局部频繁项集,通过聚合处理得到全局频繁项集.实验证明,该算法是有效的.     

数据流重组中Hash-Splay查找算法

针对高速网络取证目前所面临的问题,围绕提高网络数据流重组效率,在数据流重组算法中分析比较了几种典型的查找算法,并将Hash表和Splay树组合成Hash-Splay查找算法.该算法首先建立Hash表,然后将所有的TCP连接结点分配到各个表项,每个表项用Splay树将该表项的所有连接结点组织起来.查找时,根据连接标识通过Hash函数计算出Hash地址,再对该Hash地址对应的Splay树进行查找,找到后按照Splay树的操作规则进行查找、插入和删除等操作.由于根据连接标识找到对应Splay树的时间开销很小,可以忽略不计,因此Hash-Splay算法的复杂度可以看作是每棵Splay树操作的平均复杂度,算法同时具有Hash表和Splay树的优点,查找效率比Hash表和Splay树的都高.     

一种JPEG2000算术编码器的优化算法与实现

通过对索引表和概率间隔区间更新条件的分析,提出了一种JPEG2000算术编码器的部分并行优化算法.在连续编码两个数据对时,通过预测间隔区间的变化,可以一次完成索引表和间隔区间的更新,从而减小了编码数据的关联性,实现了算术编码器的部分并行编码.设计了基于3级流水线的JPEG2000算术编码器,并通过了FPGA验证.试验结果表明,该算法平均每个时钟编码1.58对数据,比每个时钟编码1对数据的普通算法,编码效率提高了58%.     

MC算法生成数据的分组网格化处理

对MC算法生成的数据进行后续处理,首先采用排序归并算法,归并顶点数据.根据相邻三角形共有顶点的特性,确定三角形之间的连接关系.根据属于同一个子等值面的三角形相互连接的特性,采用种子算法,将属于不同子等值面数据进行分组.采用顶点表与三角形表的数据结构存放子等值面的数据,实现MC算法生成数据的分组与网格化.     

多核处理器中基于MapReduce的哈希划分优化

针对传统的并行哈希划分算法不能高效地利用多核处理器的并行资源,且不能较好处理有倾斜的输入数据的问题,提出了一种在多核处理器中基于MapReduce的哈希划分算法,并且提出了存储结构优化、多步划分优化、数据倾斜优化3种优化策略。该算法将输入数据分成若干块后提交给各个线程并行处理,并选择合适的策略避免写冲突,使其能够高效地利用多核处理器的并行资源。文中提出的哈希表能够提高cache效率,从而提升算法的整体性能。引入MapReduce模型可使多步哈希划分在Map过程和Reduce过程中分别进行;数据倾斜优化策略能使算法适应有倾斜的输入数据,且具有较好的效果。实验结果表明:在多核处理器中,文中提出的算法能够适应各种分布的输入数据,并且使哈希划分的整体性能得到提升。     

聚类处理的蚁群算法在旅行商问题中的应用

针对大规模旅行商问题具有区域分布的族类特征,采用最小方差法将城市样本点聚成k个城市群,利用蚁群算法,求出每个城市群内部城市的最短路径及城市群之间的最短路径.提出了一种新的城市群连接方式及标记方法,使得从任一个城市出发,以该方式可对每个城市群的连接城市进行标记,同时,利用循环搜索的方法可得到每个城市群的连接方式,最终得到全局最短路径的一个满意解.最后利用TSPLIB提供的实验数据,对算法的正确性进行了验证.     

PipelineJoin:一种新的基于MapReduce的多表连接算法

MapReduce是一个并行分布式计算模型,已经被广泛应用于处理两个或多个大型表的连接操作.现有的基于MapReduce的多表连接算法,在处理链式连接时,不能处理多个大表的连接,或者需要顺序运行较多的MapReduce任务,效率较低.为此提出了一种基于MapReduce的多表连接算法——PipelineJoin,高效地实现任意多个大表的链式连接.PipelineJoin采用流水线模型和调度器来实现MapReduce任务的流水线式执行,从而有效提高多表连接的效率,同时可以较好地克服链式多表连接算法的缺陷.最后,在不同规模的数据集上进行了大量实验,实验结果表明PipelineJoin算法与原有链式多表连接算法相比,可以有效减少连接所需的时间.     

一种改进的基于云平台的物联网数据挖掘算法

物联网数据挖掘处理的是海量数据,当前数据挖掘的一个研究热点就是在大规模数据集中快速有效地提取用户所需的信息。对传统Apriori算法做相应的改进,使得检索出全部的频繁项集,只要对事务数据库进行一遍扫描就可以完成,将该Apriori算法进行Map/Reduce化,利用云计算的分布式并行计算的性质,将其应用到基于云计算的物联网数据挖掘,实验验证了改进的Apriori算法的有效性。     

基于倾斜影像点云的建筑物提取算法研究

多视倾斜影像密集匹配后能够生成海量点云数据,但数据本身缺乏有效的建筑物分类信息.针对此问题,提出一种基于倾斜影像点云的建筑物提取算法.首先对三维点云进行去噪处理和植被的剔除,将点云进行空间格网分区后降维到二维平面,通过赋予二维平面格网内每个点一定的权值,进而对格网进行特征值重采样.然后对二维平面进行图像形态学处理,利用骨架提取算法找到建筑物的轮廓,将该轮廓和三维点云进行融合后重新整饰建筑物边缘,提取出最终的建筑物点云.两组实验结果表明,该方法提取的建筑物点云轮廓清晰,建筑物立面提取较好,该算法具有较好的稳健性.     

基于自适应指数蝙蝠和SAE的并行大数据分类

为解决深度学习进行大数据分类时效率低的问题，本文提出一种基于自适应指数蝙蝠和堆叠自编码器(SAE)的并行大数据分类方法.在并行计算框架中，Map阶段使用自适应指数蝙蝠算法进行特征选择，自适应指数加权移动平均值蝙蝠算法(AEB)由指数加权移动平均值(EWMA)和自适应权重策略得到.将选择的特征作为Reduce输入进行大数据分类，Reduce阶段使用AEB算法训练的深度堆叠自动编码器(SAE)进行分类，进一步提高了分类精度.实验结果表明，针对不同的训练数据百分比，本文所提方法在准确度和真正例率(TPR)性能方面优于其他现有方法.     

Dtrie-allpair:高效的集合T-覆盖连接算法

传统的T-覆盖连接算法会因生成的候选集庞大而导致系统性能降低,为此,文中提出了一种基于trie的动态索引结构——DTI结构,并构建了基于该结构的相似度连接算法——Dtrie-allpair算法.通过该算法可以直接得到allpair连接的结果,不产生任何候选集,有效解决了高候选集产生的问题,克服了传统算法因生成并验证候选集而带来的开销.文中还研究了数据库中记录的顺序及记录中元素顺序对Dtrie-allpair算法性能的影响,并在msweb、msnbc两个数据集下对Dtrie-allpair算法与All-pair、PPJoin算法进行对比.结果表明:Dtrie-allpair算法具有明显的优势,覆盖阈值较小时优势更明显;对msweb数据集,阈值为2时,Dtrie-allpair算法的效率相对于All-pair、PPJoin算法提高近两个数量级;通过对数据集进行频率降序和长度升序组合预处理可大幅降低Dtrie-allpair算法访问的trie结点数量,从而显著提升性能.     

一种求解交通网络中最短路径问题的人工蜂群算法

用人工蜂群算法解决寻找时间依赖网络中两点之间的最短路径问题, 针对时间依赖网络中先入先出网络的特性, 改进原算法中的路径选择策略, 以优化生成的个体质量. 该算法使用的策略为每个个体（即每条路径）添加一张散列表, 用于记录搜索路径时遇到的路段, 通过查找该表可发现当前个体的更优解. 实验结果表明, 该改进方法能有效提升算法最终解的质量, 并极大缩短运行时间.     

基于GPU的可扩展哈希方法

为了使用可扩展哈希表进行快速的数据访问,需要高效地更新索引以维护哈希表.文中提出了一种基于GPU的可扩展哈希算法g EHT.该算法充分利用GPU的并行计算能力,并采用表重用、预分裂技术,无锁地扩展和收缩表、插入和删除数据,实现了高并发地创建哈希表、更新索引和检索数据.实验结果表明,该算法的查询数据、维护哈希表和更新索引性能优于其他多核CPU的线性哈希及可扩展哈希算法,尤其是在高负载的情况下.     

LCDJ:面向内存集群计算的局部感知连接算法

等值连接是数据库系统中最为重要的操作之一,哈希连接在处理等值连接时,表现出较高的性能.在分布式内存数据库系统中,数据即已分布式地存储于多个节点上,哈希连接通常情况需要将参与连接的两个关系表在连接属性上按照相同的哈希函数进行数据重分区,从而保证连接属性值相同的元组被传输到同一个节点上进行本地连接操作.由于内存数据处理速率远远高于网络的数据传输速率,因此数据重分区占据了连接算法的绝大部分时间,成为分布式内存数据库系统中等值连接操作的性能瓶颈.本文提出了一种新颖的分布式内存数据库环境下的等值连接算法LCDJ(Locality Conscious Distributed Join),在充分利用高效的内存计算的同时尽量减少网络数据传输量.算法首先对每个表连接属性的数据分布进行精确的统计,并结合并行度和计算负载均衡因素,进而建立代价模型来衡量不同调度策略下的时间开销,并求出最优的调度策略.LCDJ实现于基于内存的分布式原型系统Claims中.实验结果表明,本文所提算法有效地降低了网络传输代价,大幅度减少了响应时间,比起当前流行的Hive和Shark等系统有明显的性能提升.     

自适应逃逸动量粒子群算法的数据库多连接查询优化

为了提高数据库多连接查询的优化效率,针对粒子群算法存在的早熟、局部最优等缺陷,提出一种自适应逃逸动量粒子群算法的数据库多连接查询优化方法.该算法首先将遗传算法的交叉机制引入粒子群算法中,以保持粒子群的多样性,避免早熟现象出现;然后,引入动量算法平滑粒子搜索轨迹,加快粒子群的收敛速度;最后,将该算法应用于数据库多连接查询优化求解,以获得最优的数据库多连接查询方案.仿真结果表明,该算法提高了数据库查询效率,缩短了查询响应时间.     

数据密集型计算环境下离群点挖掘算法设计与实现

在数据密集型计算环境中,数据具有海量、高速变化、分布存储和异构等特征,对数据挖掘算法的设计与实现提出了新的挑战.基于MapReduce模型,提出了一种网格技术与基于LOF方法相结合的离群点挖掘算法MR_LOF.Map阶段采用网格进行数据约简,将代表点信息发送给主节点;Reduce阶段使用基于密度的离群点挖掘算法,借助网格期望值E筛选出稠密区域.该算法只需计算稀疏区域对象的LOF值,降低了算法的时间复杂度.实验结果表明,在数据密集型计算环境中,该方法能有效的对离群点进行挖掘.     

无线传感器网络中基于聚簇的域连接算法

针对无线传感器网络中数据处理时节能效率不高的特点,提出一种有效节能的域连接算法(Regions joinalgorithm,RJA).该算法首先结合传感器网络的节点特性和位置信息,提出一种基于聚簇的定向传播模型,该模型把传感器网络按域的划分来构建聚簇,查询只需在聚簇中进行,因而能有效减少传感器网络中信息传输的时间复杂度,同时利用网络中虚电路连接的思想,只将连接属性中与匹配相关的数据投送到链路中的公共区域进行比较运算,并不需要把整个信息表在网络中传送,因而能提高链路传输的效率.理论分析和实验结果表明,该算法与传统算法相比节省能量.     

一种面向数据缺失问题的K-means改进算法

文章针对聚类分析中部分数据缺失问题,提出了一种改进的K均值聚类算法,即改变原算法中计算每个数据到各簇距离的度量方法和新中心点生成方法,从而屏蔽空值数据的影响;通过选择UCI中Iris数据集,随机抽空部分数据进行测试表明,该算法可直接对存在数据空缺的数据集合进行聚类分析,并能有效屏蔽数据空缺对聚类结果的影响.     

需求确定时两级供应链库存控制的多准则交互式优化算法

介绍了需求确定的情况下两级供应链库存控制的一种交互协作的最优化算法．该算法将供应链上的库存控制视为多准则问题,进而实现了供应链多准则问题的一种既对供应链有效又对供应链上每个企业有效的优化方案．     

基于改进爬山算法的Bayesian网结构增量学习方法

已建成的贝叶斯网与领域环境间可能存在较大偏差,加之领域本身固有的动态变化特征,因此在观察到新数据时,改善贝叶斯网的性能和优化网络结构是十分必要的.对传统爬山算法进行研究并改进Gamez等提出的爬山算法,该算法通过引入删除结点时的禁忌表和环路禁忌表,避免搜索不必要的冗余结点,提高搜索效率,并给出禁忌表的更新方法.在ALARM数据集上进行实验,结果表明该算法是有效的.