面向分布式查询认证的分层Hash链表

针对认证跳表、签名链等方案所存在的不足,对分布式查询认证展开研究.提出分布式查询认证的定义,给出其应满足的认证性的形式化描述.以认证跳表为基础,在考虑完备性和边界隐私保护的前提下,设计一种新的认证数据结构——分层Hash链表(hierarchical Hash list,HHL),给出了HHL的定义以及构建、认证和更新算法.通过对HHL中冗余Hash节点的分析,提出了效率更高的改进分层Hash链表(N-HHL),利用统计学方法和分层数据处理对HHL的代价进行分析,得出其拥有O(log n)代价.通过模拟敌手多种破坏数据认证性的手段,对HHL的安全性进行分析,结果表明HHL能够检测出多种破坏查询结果认证性的行为,从而证明其安全性.将HHL与已有的典型分布式查询认证方案——签名链方案——进行比较,实验数据表明HHL在认证代价方面优于签名链方案.

一种改进的基于N-List的频繁项集挖掘算法

针对在海量数据中频繁项集挖掘耗时问题,近年来提出的N-List结构可有效提高挖掘效率。基于N-List提出一种新的频繁项集挖掘算法HNSFI(Hash table and subsume frequent itemsets mining based on N-List)。该算法利用PPC-tree生成N-List,引入哈希表存储N-List表示的项集,加快N-List相交操作运算时间;引入包含因子概念,利用其性质通过组合方法可以直接生成部分频繁项集,进一步提高算法时间性能。在三种不同的数据集上对该算法进行了测试和分析,实验结果表明在稠密数据集中该算法的时间性能是最优的。

基于分而治之及Hash链表的图分类算法

主流的图结构数据分类算法大都是基于频繁子结构挖掘策略。这一策略必然导致对全局数据空间的不断重复搜索,从而使得该领域相关算法的效率较低,无法满足特定要求。针对此类算法的不足,采用分而治之方法,设计出一种模块化数据空间和利用Hash链表存取地址及支持度的算法。将原始数据库按照规则划分为有限的子模块,利用gSpan算法对各个模块进行操作获取局部频繁子模式,再利用Hash函数将各模块挖掘结果映射出唯一存储地址,同时记录其相应支持度构成Hash链表,最后得到全局频繁子模式并构造图数据分类器。算法避免了对全局空间的重复搜索,从而大幅度提升了执行效率;也使得模块化后的数据可以一次性装入内存,从而节省了内存开销。实验表明,新算法在分类模型塑造环节的效率较之于主流图分类算法提升了1.2～3.2倍,同时分类准确率没有下降。

基于局部签名Hash表的证书撤销列表方案

在大规模应用环境中,不合理的证书撤销方案会带来巨大的运算量和网络传输负担。该文分析几类主要的证书撤销列表(CRL)机制,提出PSHT-CRL方案,综合分段CRL、重定向CRL和重复颁发CRL方案的特点,采用Hash表、局部签名和链接等方法,在确保安全性的基础上,提高用户查询和证书更新时的效率,以解决其他证书撤销方案中遇到的问题。对PSHT-CRL方案的安全性和效率进行分析,与其他CRL方案作了比较。

基于Zend虚拟机的Hash碰撞及DoS攻击分析

由于服务器或应用程序中Hash碰撞漏洞的存在,攻击者可能会利用该漏洞向服务器注入大量无用数据,致使CPU进程停留在碰撞数据的处理操作上,从而实现DoS攻击的目的。针对此问题,本文提出一种在Zend虚拟机中原始键值Key在完全碰撞和完全不碰撞2种情况下,程序执行效率与原始键值数量n的关系分析算法。通过DJBX33A算法和存储碰撞数据的双向链表结构,构造PHP中2n(n∈[3,31])个元素的数组并以之为测试对象,得到2种情况下程序运行时间与n的关系,结果表明:当n≤16时,2种情况下程序执行时间均随n的增长而增长;当n>16时,只有第2种情况下程序执行时间会随n的增长而增长。并对Zend虚拟机中DoS攻击进行了分析。

一种基于分段CRC码级联Hash极化码的设计

极化码作为一种线性分组码,具有较低的编码复杂度和确定的构造,但当其为中短码长时,性能会有所降低。提出一种基于分段循环冗余校验(cyclic redundancy check,CRC)码级联Hash极化码的设计方法,该方法在原有Hash极化码(Hash-Polar)的基础上,采用CRC分段校验进行双校验,分段CRC码在译码过程中能辅助路径度量,即对译码路径进行修饰,以此提高路径选择的可靠性,提高性能;另外,分段校验是将校验码分散地添加到输入的信息序列中,译码时对于CRC不通过的情况,可提前终止译码路径以省去不必要的译码计算量。最后,译码结束时,Hash校验码对修饰后的L条路径进行校验,选出最佳译码路径。仿真结果表明,所提出的设计方法比CRC辅助的Hash极化码(Hash-CRC-Polar)误码性能更优异。在高斯信道下,当码长为128bit、码率为1/2、误码率为10时,所提出的基于分段CRC校验码的Hash极化码比Hash-CRC-Polar获得了约0.25 dB的增益。

Linux文件系统数据缓冲区的分析研究

文章深入研究了Linux文件系统的数据缓冲区管理，包括数据缓冲区的整体结构、数据缓冲区采用的数据结构和实现方法。

提高Eclat算法效率的策略

为了提高Eclat算法的效率,从剪枝、项集连接和交叉计数3方面对Eclat算法进行优化.将后缀相同的项集归为一个等价类,使剪枝更充分,剪枝时引入双层哈希表加快搜索候选项集子集的速度;提出项集集合划分链表,以减少项集连接过程中比较判断的环节;提出事务标识(Tid)失去阈值,以加快交叉计数的速度.在此基础上提出一种优化的Eclat_opt算法(ZAKI),把它与Eclat原算法以及其他2种Eclat改进算法Diffset(ZAKI),hEclat(熊忠阳)进行对比实验的结果表明,Eclat_opt算法的效率在稀疏数据集上最高,总体时间性能最好.

基于贝叶斯概率模型的邮件过滤算法探讨

讨论了邮件过滤模块,通过分析研究该模块中垃圾邮件关键词的统计概率分布,提出了基于贝叶斯概率模型的邮件过滤算法,并对该算法的合理性和复杂度进行了分析。可以根据垃圾邮件内容的特征,建立贝叶斯概率模型,计算出一封邮件是垃圾邮件的概率,从而判断其是否为垃圾邮件。

基于在线网络拓扑分析的变电站操作票专家系统

本文提出了一种基于在线网络拓扑分析的操作票专家系统。该操作票专家系统采用产生式表示法和树状网络表示法相结合的形式表示知识库,并把邻接表应用到网络拓扑关系中,采用Hash查找法搜索邻接表,并根据在线SCACD实时数据,确定需操作元件,然后采用正向推理搜寻知识库,形成与实际运行方式和操作任务相符的操作项。应用结果表明该系统设计方案可行,智能程度高,稳定可靠性强。

基于路由表哈希匹配算法的压缩策略

哈希算法是一种最优的匹配算法。但是在现今的网络应用中,该匹配算法的应用有一定的局限性。在分析了路由表地址匹配的延迟过程之后,得出产生延迟的主要原因是现今的路由表容量比较有限,从而造成在路由表中无法找到IP目的地址。提出了一种以现实的最大路由表容量为准来解决路由匹配延迟的压缩策略。其目的是去掉无法找到路由表目的地址的现象,通过对压缩后路由表容量的仿真试验,结果显示,在路由表中查找目的地址失败的问题已经解决,所以该策略是可行的。

基于散列的频繁项集分组算法

Apriori算法是频繁项集挖掘的经典算法。针对Apriori算法的剪枝操作和多次扫描数据集的缺点,提出了基于散列的频繁项集分组(HFG)算法。证明了2-项集剪枝性质,采用散列技术存储频繁2-项集,将Apriori算法剪枝操作的时间复杂度从O(k×|L k|)降低到O(1);定义了首项的子项集概念,将数据集划分为以I i为首项的数据子集并采用分组索引表存储,在求以I i为首项的频繁项集时,只扫描以I i为首项的数据子集,减少了对数据集扫描的时间代价。实验结果表明,由于HFG算法的剪枝操作产生了累积效益,以及分组扫描排除了无效的项集和元组,使得HFG算法在时间性能方面与Apriori算法相比有较大提高。

STL模型冗余顶点全域哈希处理算法

目的:为解决重构STL模型文件网格时筛选冗余顶点会消耗大量时间和内存的问题,根据模型文件存储特点提出了一种基于全域哈希冗余筛选算法。方法:根据全域哈希思想,在成组哈希函数中随机选择一个进行运算,消除了已有哈希函数在对不同模型文件数据进行处理中容易出现大量冲突的问题。结果:引入平均链表长度、最大链表长度和检索复杂度三个检验标准对构造的哈希函数和改进的传统哈希函数进行实验对比分析,并通过对三个检验标准的绝对值和相对值进行比较,链表长度平均减少了17.1%,检索复杂度平均提高了45%。结论:实验证明基于全域哈希的冗余数据处理算法能够减少重构过程中筛选时间,提高数据处理效率。

μC/OS-Ⅲ中的高效时钟节拍管理机制

为了有效管理时钟节拍并确保系统的实时性,μC/OS-Ⅲ不仅增加了一个专门的系统任务来管理时钟节拍,而且采用哈希散列表机制来进一步减少时钟节拍处理过程所花费的时间。本文讨论μC/OS-Ⅱ在时钟节拍管理方面的不足,并介绍μC/OS-Ⅲ中的高效时钟节拍管理机制。

基于哈希表与十字链表存储的Apriori算法优化

Apriori算法在数据挖掘过程中需要多次扫描数据库,会造成I/O上有较大时间开销和负载,影响算法的运行速度,同时在计算频繁项集的过程中,需要进行大量迭代搜索与计算,算法的时间复杂度和空间复杂度较高。基于此,提出一种基于哈希表与十字链表存储的优化算法HTACL-Apriori。通过理论分析和数据进行实验对比,验证了优化后的HTACL-Apriori算法相对于传统的Apriori算法在时间效率和空间效率方面有明显的提高,达到了预期效果。

基于CIDR表的哈希地址二分查找算法的改进

为了解决核心交换机中路由表的爆炸式容量问题,业界引入了一种无类域间路由CIDR结构,它有效地减少了路由表容量,但是IP地址查找算法却不能令人满意。通过对基于哈希地址前缀长度的二分查找匹配算法的分析,得出由于CIDR表的存储容量有限,因而二分查找算法的优点没有体现出来。针对此问题,利用几个定点地址前缀长度扩展方法,对该算法进行改进,得到了一种满足CIDR表要求的快速查找匹配算法。经过仿真实验,改进后算法更好地满足了快速转发IP分组的需求。

一种硬件哈希表压缩方法及其性能研究

在高速、大容量的基于流的报文分类应用中,采用硬件哈希表具有成本低、扩展性好等优点。但由于需要在硬件哈希表中保存流标识,而流标识的长度依不同应用可能长达几十字节,一方面需要较大的存储空间,另一方面也严重影响了哈希查表的性能。提出了一种硬件哈希表压缩方法,可以有效压缩保存在哈希表中流标识的长度,减小所需存储器容量,提高查表性能,同时实现复杂度低,具有较高的实用价值。

时间复杂度为O(N)的联接算法

本文提出基于Ｈａｓｈ位阵列结构的等值联接算法，它利用Ｈａｓｈ位阵列及链表来实现等值匹配查找，时间复杂度为Ｏ（Ｎ），而且实现此算法的结构比较简单，容易实现。普通联接算法的时间复杂度为Ｏ（Ｎ２）

优先队列的并行插入和删除

优先队列广泛地使用在许多并行算法中(例如,多处理机调度和某些组合优化算法)。在这些算法中,共享优先队列的存取冲突限制了加速比的提高。本文提出一种链表优先队列的并行插入和删除方法,具有较小并行开销和较大的并行度,并且保证和串行存取算法的优先顺序完全一致,即删除操作返回已经插入和正在插入的所有元素中的最佳元素。同时,我们还介绍了目前性能最好的堆的并行插入和删除算法,并对准和链表结构并行插入和删除算法的性能和适用范围进行了比较,进一步提出了散列结构的优先队列。在ENCORE Multimax520多处理机上的实验结果验证了我们的理论分析结果:使用链表结构的并行分枝限界算法性能上可获得很大提高。

基于有向哈希树的认证跳表算法

作为一种重要的认证数据结构,认证跳表在数据认证机制中有着广泛的应用。由于哈希模式对认证跳表的代价有显著的影响,因此提出哈希模式和数据存储模式分离的思想,设计了一种新的认证哈希模式——有向哈希树,并在其基础上设计了新的认证跳表算法。应用分层数据处理、概率分析等数学方法对所提出算法的代价进行了理论分析,并与已有的认证跳表算法做了性能比较。结果表明,本算法在时间、通信和存储代价方面有了较大的改进。