一种基于位向量流分类算法的改进

在流分类算法中,聚合位向量(ABV)算法分类速度快、并行性好,但内存开销过大;位向量折叠(AFBV)算法对ABV算法进行了改进,降低了运行时内存的消耗,但其冗余计算增加了时间开销。针对上述不足,文章提出一种改进的位向量流分类算法,该算法无需进行位向量聚合,减少了内存开销,并按规则的源/目的IP地址前缀建立分组表,根据表中分组所包含IP地址数目降序排列,使得算法具有良好的时间性能。实验结果表明,本算法在大规模规则库下具有良好的时间和空间效率。     

改进的基于DBSCAN的空间聚类算法研究

针对DBSCAN算法I/O开销和内存消耗大的缺点,提出了基于层次合并的密度算法.该算法减少了DBSCAN算法中需要查询的点的数量,从而克服了DBSCAN算法I/O开销和内存消耗大的缺点.算法分析表明该算法对DBSCAN的改进是有效的.     

递归流包分类算法的改进

为解决递归流包分类(RFC)算法在大规则、多维、IPv6应用环境下出现内存消耗过大的问题,在RFC算法的基础上,提出了将源、目的地址字段与其他字段分开处理的新算法.首先,对地址字段使用几何学点定位分类模式处理,并将区间列表组织成平衡树结构以达到快速定位;其次,其他字段采用位图压缩表来代替预处理表;最后将这两部分的匹配结果组合得到最终的规则标识符.新的算法综合考虑了空间和时间性能,不仅大大地减少了存储开销,而且能保持相对快的查找速度.     

软件实验DNA k-mer index四字链表字典树检索算法

针对软件实验中常涉及到的DNA碱基序列k-mer 问题,提出一种基于四字链表字典树的快速检索算法。根据不同的k值建立深度为k的四字字典树,最大程度地避免字符串中重复公共前缀而造成的空间浪费,压缩内存消耗,降低空间复杂度;以叶子节点作为k-mer 结束标志建立索引查询链表,并输出k-mer 的所有序列号与位置号,最终完成DNA序列k-mer 问题的建立索引与快速查找任务。实验表明,该算法具有很高的查找效率,且可以减少查询时间,能够高效解决DNA序列的k-mer index问题。     

基于聚类分析的大学生体质异常数据提取方法

针对大学生体质异常数据提取内存开销大、覆盖率低等问题,提出基于聚类分析的大学生体质异常数据提取方法。通过Relief算法调整数据特征距离,筛选出异常数据的相关特征,采用K-means算法聚类分析异常数据,将单条信息汇集为一类信息,改进K-means算法的K值选取,实现大学生异常数据精准提取。经验证,该方法具有较高的覆盖率,拥有较小的内存开销与时间开销,能够有效降低异常数据提取过程中内存与时间消耗。     

面向结构体数据布局优化的高效内存管理

面向结构体数据布局优化的内存池由于自身的使用特点,在传统的内存管理方式下,扩展内存需要移动数据,代价很高。为了避免移动数据,提高内存池性能,该文设计实现了基于共享内存地址映射技术的零数据移动内存管理系统DM3,辅助内存池管理内存。DM3利用POSIX标准编程接口提供的共享内存机制,在用户层操控物理内存到程序虚地址空间的映射,实现高效内存管理。首先,DM3针对结构体数据布局优化的内存使用特点,选择特定地址空间分配,既照顾到内存池扩展需求,又避免影响程序中其他内存请求。其次,在已分配的地址空间不能满足进一步扩展需求时,DM3通过内存地址重映射,实现地址空间转移而避免实际移动数据。通过在多个操作系统上的实验比较了DM3和传统的realloc方式,结果表明:DM3系统性能优越,最高可获得9.76倍加速比。DM3使用POSIX标准实现,具有跨平台移植性和易用性。应用DM3管理内存有效地增加了内存池性能。     

时间滑动窗口上数据流极值聚集的空间优化

传统的数据流极值聚集方法在极端情形下为获得连续的精确解,会因维护大量候选项而导致巨大的内存开销,为此文中提出了一种时间滑动窗口上内存有界的极值聚集方法.在候选项数量达到指定阈值时,该方法随机抽样新到达窗口的数据,使得内存维护有限数量的候选项,连续返回极值近似解.设计了一种空间有界的摘要数据结构REx-link,可以在有界的内存中基于随机抽样进行维护,实现时间滑动窗口上的数据流极值聚集.从理论上证明了随机算法的出错概率存在上界,并通过仿真实验分析了算法的返回结果与精确解的近似程度.分析表明,计算精度和空间开销的折中是实际应用可接受的.     

ZigBee网络中基于借地址的高效分布式地址分配算法

借地址机制用于解决ZigBee网络在采用DAAM (distributed address assignment mechanism)为节点分配地址时因组网参数的限制而产生的孤节点问题。现有的借地址机制可以提高地址分配成功率,但存在其组网开销和时延较大的问题。为此提出一种高效的借地址分配算法EDAA BA (efficient distributed address assignment algorithm based on borrowed address),采用首先向同枝子孙节点借地址的方式为路由孤节点分配地址、加入借地址信息即时回复机制以及将16位地址中DAAM未使用到的剩余地址分配给终端孤节点等改进机制达到减少组网开销和时延的目的。理论分析和仿真结果表明：EDAA BA算法在保持较高地址分配成功率的前提下,其组网耗时和组网开销方面性能优于现有的两种改进方案。     

路由器级拓扑发现目标地址选择问题研究

路由器级拓扑发现对于获取Internet网络拓扑结构具有重要意义,而如何获得拓扑发现的目标地址是其面临的一个主要问题.现有的方法主要使用Internet上公布的BGP(Border Gateway Protocol)前缀,若对其不加处理,对所有的网络前缀都进行探测,所产生的网络负荷和算法收敛时间将难以接受.同时,在选择目标地址时也需要考虑完备性,以保证对目标网络的覆盖程度.文中对已有的"桩网络法"进行改进,实验证明提高了目标地址的真实性以及对目标网络覆盖的完备性.     

支持多种Linux版本的动态内核性能测试技术

基于Intel IA32架构,提取了相对稳定的Linux操作系统框架.该框架主要集中于源代码树中的/arch目录中,由一些简短、高效的与体系结构相关的汇编代码构成.据此,设计了性能测试方案,包括基于地址表格改写的入口插接方案和基于代码拼接的出口插接方案.方案在运行的操作系统中,通过动态改写系统内存的插接技术实时地插入测试代码,测试代码可以使用高级语言来书写.实验表明,所提方案适用于通用的Linux 2.4和Linux 2.6内核系列,其时间开销仅为基于中断动态插接技术的6%左右,且能发现系统硬件和操作系统的关键性能问题.     

面向函数的代码克隆检测

在软件开发过程中绝大多数克隆代码集中在函数内部,为了更加快速有效地检测出克隆代码,提出了一种基于函数内部特征矩阵的代码克隆检测算法。该算法通过提取函数内部特征,从而达到将具体代码的比较转化为对特征矩阵进行相似度计算。实验结果表明,该算法可以检测出所有克隆函数,并与基于字符串代码克隆检测算法和基于串匹配的程序代码相似性识别方法相比,该算法在运行时间及精度上均优于基于字符串代码克隆检测算法和基于串匹配的程序代码相似性识别方法。其次,通过使用N-grams算法对函数名进行相似度检测,使得该算法在运行效率上得到了显著提升。     

一种新的基于CRC的文本内容认证方法

提出了一种基于CRC的文本脆弱水印算法.利用CRC差错检测方法,该算法将要保护的文本按m个文字一个级联分成若干个级联,将每个级联与密钥合成后的位串除以设定的生成多项式,再把6位的余式位串分成三组,作为水印信息嵌入到级联的最后一个文字的RGB的三个分量.提取水印时,将该级联的余式位串求出.如果与提取的水印相同,则认为此级联没有纂改,否则有纂改.该方法检测到纂改的概率为1-1/26m,并且至少能将纂改定位于级联内.     

Novel Privacy Preserving Method of Countering the Threats from Priori Knowledge

Recently,many data anonymization methods have been proposed to protect privacy in the applications of data mining.But few of them have considered the threats from user's priori knowledge of data patterns.To solve this problem,a flexible method was proposed to randomize the dataset,so that the user could hardly obtain the sensitive data even knowing data relationships in advance.The method also achieves a high level of accuracy in the mining process as demonstrated in the experiments.     

迭代函数系统的快速生成方法

提出了迭代函数系统的快速生成方法，采用无逃逸行为的生成算法和最少点绘制的生成算法进行分形图像的生成，算法可以并行执行，实验证明并行算法的执行时间仅为传统随机迭代算法中单个仿射变换的生成时间，为分形图像的快速生成提供了新的途径．     

基于匿名方法的数据发布隐私泄露控制技术研究进展

介绍主要的数据匿名保护模型,总结分析基于泛化和隐匿、基于聚类、基于交换和分解的数据匿名化算法的研究成果和存在的问题,指出数据发布的匿名化技术还需要在同质性攻击和背景知识攻击、动态性数据的隐私保护、个性化的隐私保护、数据发布自适应机制、面向应用的隐私保护和多属性数据集的隐私保护等几个方面做进一步的研究。     

并行后缀树的构造及查询算法

针对生物信息领域中传统后缀树构造算法在时间和空间上的限制,从结构并行的角度提出了一种新颖的、适用于生物信息学应用的并行后缀树结构和相应的构造算法·该算法首先将给定字符串分成若干连续的片段,并在各个处理机上分别构造这些片段的后缀树,形成了一种分布于多个处理机上的并行后缀树结构·该并行算法不仅大大缩短了后缀树的构造时间,而且避免了主存大小的限制·经分析,其性能优于现有的任何一种并行算法·在此基础上,提出了一种高效的基于这种并行后缀树的字符串匹配算法,解决了传统后缀树的基本查询问题·     

基于编码通道数的JPEG2000压缩率控制算法

提出一种基于小波量化权值和编码通道数的JPEG2 0 0 0压缩率控制算法 .在位平面编码之前 ,根据当前码块所处的子带和码块内包含的编码通道数预先分配压缩码字数 .在编码过程中 ,编码码字数超过分配码字数时就截断码流 ,即实时截断码流 .与标准的率失真 (PCRD)优化算法相比 ,该算法不会在计算码率失真斜率和搜索最优分层截断点时产生运算开销 .实验结果表明 ,在 0 5b/像素下 ,所提算法对于Lena图像的存储器损耗和编码时间也只有标准PCRD优化算法的 6 8%和 18 7% ,但图像质量只低 0 8dB .这种算法资源损耗少 ,显著提高了运算速度 ,更有利于超大规模集成电路实现     

钻井用钻头和钻柱扭转振动的仿真分析

介绍了钻井过程中钻头和钻柱扭转振动模型的建立方法和对其进行仿真分析的过程。在建模型时主要考虑了钻井过程中由于钻头与岩石相互作用及钻柱的弹性变形而引起的钻头和钻柱扭转振动,并采用数值计算方法求解钻柱扭转振模型,     

Memory Efficient String Matching Algorithm for Network Intrusion Management System

As the core algorithm and the most time consuming part of almost every modern network intrusion management system (NIMS), string matching is essential for the inspection of network flows at the line speed. This paper presents a memory and time efficient string matching algorithm specifically designed for NIMS on commodity processors. Modifications of the Aho-Corasick (AC) algorithm based on the distribution characteristics of NIMS patterns drastically reduce the memory usage without sacrificing speed in software implementations. In tests on the Snort pattern set and traces that represent typical NIMS workloads, the Snort performance was enhanced 1.48%-20% compared to other well-known alternatives with an automaton size reduction of 4.86-6.11 compared to the standard AC implementation. The results show that special characteristics of the NIMS can be used into a very effective method to optimize the algorithm design.     

混合算法在流量工程中的应用

针对大规模网络中的流量工程问题,设计了结合遗传算法与模拟退火以及结合遗传算法与爬山法的两种混合算法.仿真实验表明,结合遗传算法和模拟退火的混合算法在整体性能上较单独使用遗传算法有明显的提高,结合遗传算法和爬山法的混合算法在处理超大规模的网络和海量业务要求的流量工程问题时具有时间上的明显优势.