基于最小完美哈希函数的数据挖掘算法

提出了一种基于最小完美哈希函数的关联规则的挖掘算法.这一基于Apriori的算法在综合了传统哈希剪枝技术的同时,充分利用了最小完美哈希函数的优点,从而在保证静态数据库关联规则挖掘的同时,使对关联规则的哈希结构数据进行动态调整成为可能.这一算法不仅提高了挖掘效率,而且通过抑制哈希地址冲突提高了算法的稳定性和可用性.

基于多级相关图的大规模词典完美哈希函数构造算法

在哈希函数中,如果两个不同的单词被映射到同一个槽,那么我们称为冲突。当哈希函数存在冲突时,将降低词典查找的速度。由于完美哈希函数完全避免了冲突,因此在许多对查找性能要求较高的应用中广泛使用。本文就此提出了一种基于多级相关图的大规模词典完美哈希函数的构造算法。词典单词的每个字符(首字母除外)都用两个平滑函数平滑为两个字符,构建平滑后词典对应的多级相关图,多级相关图的结点度都比较小,而且分布比较均匀,因此更容易生成完美哈希函数。实验表明:基于多级相关图的哈希函数构造算法适用于大规模词典,填充因子接近1,同时工作空间比已有算法都要小。

基于最小完美哈希函数的K-mer计数算法

在DNA序列中对长度为k的子序列K-mer进行计数是生物信息学分析的关键环节,为解决传统K-mer计数中出现的耗时长、内存占用量大的问题,文中提出一种基于最小完美哈希函数的K-mer计数算法。该算法能够无哈希冲突地将K-mer映射到尽可能最小的整数范围内,对最小完美哈希表的查询在常数时间内完成,能够高效处理动态变化的大规模数据集。在处理大肠杆菌基因序列时,本文算法MPH-KMC相对jellyfish2算法,耗时缩短3倍,内存消耗缩小11倍。

基于哈希表的稀疏图像压缩算法研究

随着互联网技术的不断发展,以图像为主要载体的多媒体信息大大丰富了我们的生活。但由于图像数据量庞大,存储和传输时受到很大限制,使得图像压缩成为图像处理中的一个重要环节。图像压缩就是利用图像自身的相关性来消减图像的冗余信息,保留有用的信息。经过多年的研究,人们已经提出了多种图像压缩方法,并在许多领域取得了良好的应用效果。但这些方法主要是针对普通密度的图像,而对于稀疏图像的压缩,目前有效的压缩方法还屈指可数。对图像压缩技术的发展历程进行了回顾,给出了一种基于哈希表的对稀疏数据压缩方法,并利用VC++6.0平台,实现了基于哈希表的数据压缩系统。

IDS日志数据挖掘的改进算法

提出了一个基于最小完美哈希函数的关联规则的挖掘算法。基于Apriori的算法,在综合了传统哈希剪枝技术的同时,利用最小完美哈希函数的优点,保证了静态数据库关联规则挖掘,可以对关联规则的哈希结构数据进行动态的调整。该算法提高了挖掘效率,通过抑制哈希地址冲突提高了算法的稳定性和可用性。

基于m-n变进制规则的动态图软件水印算法

针对软件水印分存算法恢复缓慢、数据扩张的缺点,提出一种基于m-n变进制规则的动态图软件水印算法,利用水印信息、m-n变进制数、排列数与置换图之间的对应关系,实现水印的分存和编码。当水印嵌入时,根据变进制规则将水印信息分存为一组变进制数,构造一个完美哈希函数将变进制数映射为对应的排列数,把得到的排列数编码为置换图结构嵌入到程序的执行代码中,水印提取是水印嵌入的逆过程。实验结果表明,该算法能减小程序的负载,降低水印嵌入和提取的时间复杂度,增强水印的隐蔽性和纠错能力。

基于数据挖掘的IDS日志算法的改进

提出了一个基于最小完美哈希函数的关联规则的数据挖掘算法。基于Apriori的算法,在综合了传统哈希剪枝技术的同时,利用最小完美哈希函数的优点,保证了静态数据库关联规则挖掘,可以对关联规则的哈希结构数据进行动态的调整。该算法提高了挖掘效率,通过抑制哈希地址冲突提高了算法的稳定性和可用性。

基于Windows的在线判题系统的安全性研究

在线判题系统(OJ)是ACM/ICPC竞赛选手用来进行程序设计练习和比赛的平台,现有OJ在遇到恶意提交代码方面经常造成服务器故障、崩溃或硬盘阻塞等安全威胁。为参加ACM/ICPC竞赛选手提供安全、可靠和高性能的OJ平台,在保证安全性的同时又不影响使用性。论文从源码级控制、应用程序级控制与防止恶意提交方面作了深入研究,提出基于sandbox(Windows沙箱)、ACL(访问控制列表)、完美哈希和帐号保密等技术的安全体系结构,通过在Windows下搭建OJ平台验证了采用此体系结构的OJ彻底解决了前面的安全问题。OJ安全可靠,性能优良。

基于压缩域的脑成像大数据体可视化方法

脑科学是当今国际科技研究的前沿邻域,而对高精度脑成像数据进行可视化是脑神经科学在结构成像方面的基础性需求。针对高精度脑成像数据可视化过程中存在的数据量大以及绘制效率低的问题,提出了基于分类分层矢量量化和完美空间哈希相结合的压缩域可视化方法。首先对体数据进行分块,记录每块的平均值并依据块内体数据的平均梯度值是否为0进行分类;其次运用分层矢量量化对平均梯度值不为0的块进行压缩;然后用分块完美空间哈希技术存储压缩得到两个索引值;最后对上面的压缩体数据进行解码得到恢复体数据,采用分块完美空间哈希对原始体数据与恢复体数据作差得到的残差数据进行压缩。绘制时,只需将压缩得到的数据作为纹理加载到GPU内,即可在GPU内完成实时解压缩绘制。实验结果表明,在保证较好图像重构质量的前提下,该算法减少了数据的存储空间,提高了体可视化的绘制效率,从而可以在单机上处理较大的数据。

DNS权威服务器FPGA加速技术研究

现有DNS权威服务器处理DNS请求及响应报文依赖软件网络协议栈, CPU资源占用率高、开销大,处理性能受限.本文基于SmartNIC架构对DNS权威服务器的功能进行卸载加速,提出并设计了高性能DNS权威查询响应流水线PHDR Pipe (perfect Hash DNS response pipeline),基于完美哈希(perfect Hash)实现对区文件的预先处理,避免哈希冲突导致的多次访存,降低流水线最坏情况下处理延迟,从而有效提升系统吞吐率并降低响应延迟.基于开源的FAST平台的实验结果表明,与通用的BIND9系统相比响应延迟降低了约10倍,吞吐量接近10 Gb链路线速,同时资源开销小且具有良好的可扩展性.

稀疏超图:从理论到应用

给定正整数r、e和v,如果某个r-一致超图的任意e条不同边的并都包含至少v+1个顶点,则称其是(v, e)-自由(free)或者(v, e)-稀疏的.稀疏超图的概念由Brown、Erd?s和Sós在20世纪70年代提出.目前,研究给定顶点数的稀疏超图所能包含最大边数的上下界已成为极值组合学研究领域内的核心问题之一.该问题的研究方法丰富多变,涉及组合、概率、代数和数论等多个领域.本文介绍Brown、Erd?os和S′os关于稀疏超图的两个重要猜想的最新研究进展以及稀疏超图在极值组合与信息科学中的若干应用,包括朱烈曾作出突出贡献的完美哈希(Hash)矩阵、可分哈希矩阵等几类信息安全中的研究问题.此外,本文在某些参数下给出完美哈希矩阵与求并-自由(union-free)超图的新构造.本文的构造改进了相应问题的已知最优下界.