基于素数的多源模式匹配方法的研究

模式匹配是获取不同模式间语义关联关系的技术,是数据集成过程中的关键操作.随着可检索在线数据库数量的迅速增加,大规模的模式匹配工作的需要使多源模式匹配方法成为模式匹配领域研究的重点.针对现有多源模式匹配方法的缺陷,本文提出了一种基于素数的多源模式匹配方法,并提出了具体算法-PMSM.该方法将素数理论引入模式匹配过程中,使单纯的字符匹配转换为素数计算,提高了匹配效率,同时保留了现有多源模式匹配方法的优点.实验证明,PMSM切实可行.     

基于小波和动态时间弯曲的时间序列相似匹配

提出了一种基于小波和动态时间弯曲(DTW)距离的时间序列索引和相似匹配方法. 该方法采用小波变换进行数据降维,利用R·-tree建立多维索引结构. 给出了查询序列的DTW距离边界和其在小波空间的查询超矩形的计算方法,从而将原始空间的基于DTW距离的相似匹配转换为小波空间基于欧氏距离的相似匹配. 证明了此匹配方法不会产生漏报,给出了基于DTW距离的范围查询算法和近邻查询算法. 实验结果表明该方法具有较高匹配精度和其较低的计算代价.     

基于最小生成树的多层次k-Means聚类算法及其在数据挖掘中的应用

针对传统聚类算法存在挖掘效率慢、 准确率低等问题, 提出一种基于最小生成树的多层次k-means聚类算法, 并应用于数据挖掘中. 先分析聚类样本的数据类型, 根据分析结果设计聚类准则函数; 再通过最小生成树对样本数据进行划分, 并选取初始聚类中心, 将样本的数据空间划分为矩形单元, 在矩形单元中对样本对象数据进行计算、 降序和选取, 得到有效的初始聚类中心, 减少数据挖掘时间. 实验结果表明, 与传统算法相比, 该算法可快速、 准确地挖掘数据, 且挖掘效率提升约50%.     

基于MapReduce的大规模文本聚类并行化

建立快速有效的针对大规模文本数据的聚类分析方法是当前数据挖掘研究和应用领域中的一个热点问题.为了同时保证聚类效果和提高聚类效率,提出基于"互为最小相似度文本对"搜索的文本聚类算法及分布式并行计算模型.首先利用向量空间模型提出一种文本相似度计算方法;其次,基于"互为最小相似度文本对"搜索选择二分簇中心,提出通过一次划分实现簇质心寻优的二分K-means聚类算法;最后,基于MapReduce框架设计面向云计算应用的大规模文本并行聚类模型.在Hadoop平台上运用真实文本数据的实验表明:提出的聚类算法与原始二分K-means相比,在获得相当聚类效果的同时,具有明显效率优势;并行聚类模型在不同数据规模和计算节点数目上具有良好的扩展性.     

基于订阅划分的多维索引并行匹配算法

针对基于内容的发布/订阅系统匹配算法中的计数算法和树形算法在多操作符匹配结构中效率不高的问题,提出了一种基于订阅划分的多维索引并行匹配算法(SPMP-match).该算法利用二叉树原理对订阅进行分组,然后组织成树形索引结构,采用一种边匹配谓词边观察的策略,及时终止无成功匹配订阅的情形.该算法仅对可能和一个事件匹配成功的所有订阅进行匹配,不会产生无价值的时间消耗,并且在查找匹配成功的订阅时,只须要查看所有可能和某事件匹配成功的订阅表,避免了扫描整个订阅集合.     

具有独立通配符间隔的模式匹配算法

模式匹配作为一种关键技术已被广泛应用于生物序列分析和文本过滤等领域.通配符间隔可以匹配特定长度子序列,为模式匹配问题带来了更多的灵活性.为增加灵活性和一般性给出一种新的模式匹配问题定义,其中通配符间隔可以独立设置,并基于模式分解设计出一种有效的计算匹配数量的算法.实验结果显示,与同类算法相比本算法在性能上具有更优的时间复杂度和空间复杂度.     

并行环境下基于图着色理论的空间数据部署

在面向计算部署到数据节点端执行的分布式并行环境下,提出一种基于图着色理论的适用于矢量空间数据的部署方法,将空间数据粒度的部署问题转化为图顶点着色的过程,提高了任意空间区域的信息查询效率.给出基于图着色理论的数据部署方法,并通过节点的任务量进一步改进算法,使得该算法可实现海量空间数据粒度的离散化部署,提高了空间数据检索和查询的并行化程度,充分利用了并行计算资源.     

BDCode:一种面向大数据存储系统的纠删码算法

针对含有大量数据的大数据存储系统,提出了一种基于编码技术的面向大数据备份的优化算法(BDCode).该算法通过对不同编解码服务器设置不同的虚拟节点存储组来保证系统的可用性,节点和数据块的并行解码计算提高了系统中数据损坏时的恢复效率.实验表明,所提出基于编码的大数据系统备份机制可以提高系统的存储利用率,并行解码方式的引入能加速减少数据损坏时的恢复时间,并能达到零号的系统负载均衡;此外不同的用户设置不同的编码参数,增加了大数据系统的鲁棒性.实验通过设置不同的数据块m和校验块k的比例来提升利用率,并行解码速度相比以前的串行提高近两倍.使用BDCode比CRS编码效率平均高36.1%,解码效率平均高19.3%;比RS码编码效率平均高58.2%,解码效率平均高33.1%.     

基于文本频率冗余的单模式匹配算法的研究

针对入侵检测系统中经典的BM、KMP等单模式匹配算法进行了分析,根据入侵检测数据的特点和匹配算法的基本原理,提出了文本频率冗余度的概念,设计实现了评估文本频率冗余度的算法.实验测试了其对于单模式匹配算法效率的影响,结果显示基于文本频率冗余智能地选择匹配算法,对于提高入侵检测系统的实时性能有实际的应用价值.     

基于边界条件GAN的不平衡大数据模糊分类

针对大数据分类中的不平衡问题,本文提出一种基于边界条件生成式对抗网络(Boundary Conditional Generative Adversarial Networks,BCGAN)的不平衡大数据模糊分类算法,通过在多数类数据和少数类数据的决策边界附近引入一个边界少数类到过样本,生成更合适的少数类数据来提高分类性能.将处理过的平衡数据转换成概率索引表,数据和属性分别以行和列的形式呈现,计算每个数据属性中存在的唯一符号的隶属度,然后设计相关模糊朴素贝叶斯(Correlative Fuzzy Naive Bayes,CFNB)分类器进行数据分类.本文给出MapReduce框架下大数据模糊分类的并行实现.实验结果表明:所提基于BCGAN的不平衡大数据模糊分类准确度优于其他现有方法,说明该方法具有可行性和有效性.     

基于矩形窗口分区编码的圆形裁剪新算法

裁剪是计算机图形学中基本问题之一,其核心问题是效率问题,而矩形窗口是常用的裁剪边界.在分析现有圆裁剪算法的基础上,提出了基于矩形窗口分区编码的圆裁剪算法,首先根据圆的八分对称性求出圆周的关键点,然后按规则进行编码,从而判断圆与矩形窗口的相交关系,并对圆进行相应的裁剪输出.实验结果表明,该算法减少了复杂运算的次数,避免了多余的无用计算,具有较高的运算效率.     

多边形区域内储层建模结点三角剖分算法研究

结合储层建模结点数据的特点 ,提出了一种对多边形区域内建模结点数据进行快速三角剖分的算法 .如果区域边界边与剖分三角形可能相交 ,根据边界边顶点与剖分三角形确定的矩形区域的关系 ,对于不同情况 ,通过计算矢量叉积 ,或最坏情况下通过计算交点 ,来确定边界边与剖分三角形是否真正相交 .同时 ,讨论了在剖分过程中 ,对边界边链表进行实时更新 ,逐步减少边界边的思路 .虽然整个算法的时间复杂度最坏情况为 O( 3× m×n) ( m为多边形区域内结点形成的三角形个数 ,n为边界边个数 ) ,但在实际应用中 ,对大批量的储层建模结点数据进行三角剖分时 ,文中提出的算法具有比较高的处理效率     

面向入侵检测系统的模式匹配算法研究

针对入侵检测系统对基于攻击特征的网络数据包的检测效率低和丢包率高的问题,在分析典型的模式匹配算法的基础上,提出了一种Boyer Moor Horspool Fast(BMHF)匹配算法.引入一个新的判断函数Q(X)指出字符X在模式串中出现的次数,当出现次数为1时可以利用已匹配的信息加大移动距离,同时利用文本串中不匹配字符后面的一个字符进行匹配,从而得到一个移动距离.将不同移动规则下获得的移动距离的最大值作为实际的移动距离,依次进行,直到匹配完成.实验结果表明,BMHF算法的CPU运算时间比典型的模式匹配算法可平均节省5.7%,平均匹配次数减少12.5%.     

基于移动平台的异构并行字符串匹配算法

针对信息处理中常见的字符串匹配问题,通过对经典的Brute Force算法和KnuthMorris-Pratt算法进行分析,根据GPU异构并行计算任务的分配特性,设计一种针对Knuth-Morris-Pratt算法的数据重叠划分并行方案,并提出一种基于移动平台的异构并行字符串匹配算法KMP_MOP.在PowerVR移动平台环境下使用千万级长度的字符串数据对算法的性能进行测试,同时对算法在其他平台的执行情况进行比较,验证了并行算法的性能可移植性.实验结果表明,KMP_MOP算法能充分利用移动平台中的GPU性能,有效提高具有GPU的移动平台设备的字符串匹配效率.     

基于Spark的证据邻域粗糙并行分类高效算法

传统邻域分类器因良好的分类性能在分类问题中得到广泛应用。但数据规模和维度的不断增加,提高了邻域分类器的处理难度。为解决这一问题,该文基于Spark实现邻域决策错误率并行属性约简算法,删除数据中的冗余属性,减少数据间的不确定性。该算法能减少分类过程中数据计算时间,提高分类计算效率。邻域分类器在分类决策过程中采用的多数投票机制没有考虑到邻域样本的空间差异性与标签不确定性,易导致错误分类。该文在Spark框架下将D-S证据理论引入邻域分类器,并行融合整个邻域空间的证据支持信息,提出基于Spark的邻域证据并行分类算法。实验结果表明,该文提出的算法相较于传统邻域分类器,在处理大规模数据时计算时间更少、效率更高,对未分类样本的分类精度更高。     

关联挖掘在Deep Web查询中的研究与应用

对Deep Web进行模式匹配查询时,通常会碰到复杂的模式匹配。由于复杂模式匹配技术在对所有可能联接进行匹配时,需要的空间开销比简单匹配的空间开销大得多,所以现有的模式匹配技术大部停留在简单匹配技术上。为了解决这一难题,本文提出了关联规则挖掘这一方法在复杂匹配中的应用,将模式匹配视为一种关联挖掘,实现web查询接口的匹配,以此将Internet上众多数据库进行集成。     

一种面向GIS的静态R-树数据组织方法

针对GIS空间数据提出了一种基于空间聚类的静态R-树生成方法.该方法用典型点法进行静态R-树数据组织,用空间对象的最小约束矩形代替空间对象本身进行空间聚类计算,形成若干聚类,并以R-树的构建规则进行适当调整,同时通过改进R-树的一些性能指标如覆盖区域、重叠面积和边界周长等提高其查询性能.通过将该算法与其他静态R-树算法如Low x算法、Hilbert R-树算法进行比较,论证了该算法的可行性.     

针对信号安全数据网主机指令日志新的安全审计算法

通过对多家信号安全数据网核心设备厂商进行的调研,发现列控中心、联锁系统、临时限速服务器和无线闭塞中心都没有对其主机指令日志进行审计.主要原因是现有的模式匹配算法并不适合信号安全数据网的主机日志.为此提出了一种针对信号安全数据网主机指令日志的改进审计算法,该算法结合两种改进的模式匹配算法.描述了该算法的匹配原理,结合现有的无线闭塞中心日志数据进行了实验测试.实验结果表明该审计算法效率较高,可以满足功能需求.     

一种计算迎风面密度的优化算法

提出了一种基于最小外接矩形的计算迎风面密度的优化算法.该算法的核心问题是如何高效地求解建筑物沿着某一风向的投影面宽度(迎风面宽度).具体解决方案为:将不规则建筑物水平轮廓根据风向角度进行一定角度的旋转操作,使得旋转后建筑物水平轮廓的最小外接矩形的宽即为建筑物水平轮廓未旋转时的迎风面宽度.由于最小外接矩形及其旋转操作在当前很多图形系统软件中一般都有接口支持且运行效率非常高,用户也可以直接调用相关接口进行二次开发.因此,本方法具有较高的运行效率和应用便利性.     

Spark平台下KNN-ALS模型推荐算法

考虑Spark大数据平台内存计算框架在迭代计算的优势,提出Spark平台下KNN-ALS模型的推荐算法.针对矩阵分解算法只考虑隐含信息而忽视相似度信息的缺陷,将相似度信息加入评分预测中,并采用适合并行化的交替最小二乘法进行模型最优.在MovieLens数据集上的实验表明:该算法能够提高协同过滤推荐算法在大数据集下的处理效率,且加速比也达到并行处理的线性要求,相比其他方法有较好的精度.