面向高速网络连接记录管理的高效哈希表

针对高速网络环境下连接记录管理的性能需求,提出了一种改进的高效哈希表PRH-MTF(伪随机哈希-移至最前).首先在定义输入关键字即连接标识符的基础上,通过选择适当的运算符,设计了高效鲁棒的哈希函数PRH.为有效解决哈希冲突,根据网络数据流局部性特点,应用MTF启发法,改进了传统的链式冲突解决方法.以分组火车模型作为数据包到达模式,分析了PRH-MTF哈希表的算法复杂度,推导出了平均查找长度.最后通过实际高速网络数据流和模拟攻击的方式,对PRH-MTF哈希表进行了实验评估.实验结果表明,PRH-MTF哈希表在查找性能和抗攻击能力等方面均优于传统的简单排序哈希表.     

面向内存计算的连接算法

内存和CPU技术的快速发展标志着内存计算时代的来临.本文系统地回顾了基于内存计算的连接算法,具体在嵌套循环连接、哈希连接、排序归并连接和单机环境、分布式环境两个分类的维度上分析了已有算法的优点与不足,展望了未来的研究方向,最后介绍了基于Claims原型系统关于分布式连接方面的研究工作.     

一种基于多哈希表的堆式动态存储管理方法

给出了一种基于多哈希表的堆式动态存储管理方法,其基本思想是利用哈希表的快速查找优点,通过查找以空闲块大小为关键字的哈希表SizeHashTable实现最佳拟合法的分配策略,并通过查找以空闲块头地址及尾地址为关键字的双哈希表AddressHashTable解决回收空闲块中结点合并问题,最终高效率地实现堆式动态存储管理.本文给出的相关算法在Windows平台下用VisualC++进行了实现.     

一种基于多哈希表的堆式动态存储管理方法

给出了一种基于多哈希表的堆式动态存储管理方法，其基本思想是利用哈希表的快速查找优点，通过查找以空闲块大小为关键字的哈希表SizeHashTable实现最佳拟合法的分配策略，并通过查找以空闲块头地址及尾地址为关键字的双哈希表AddressHashTable解决回收空闲块中结点合并问题，最终高效率地实现堆式动态存储管理．本文给出的相关算法在Windows平台下用Visual C 进行了实现．     

除留余数法建立哈希表的方法改进

查找是从大量的数据中得到所需信息经常要进行的工作。为了更好的查找,在存入数据时一种常用而有效的方法是用除留余数法来建立哈希表,用线性探测法处理冲突。目前,大部分书籍上在建立哈希表时都是一边存储,一边解决冲突。该方法由于哈希表中存在的"堆积"现象,大大降低了查找效率,并且从思想上来看,沒有很好的符合哈希法的初衷,是不顾后效的。文章对该方法做了改进,有效的克服了该方法的缺点。     

一种带有盐度值的安全哈希加密算法的设计与实现

当直接采用安全哈希算法对用户的密码进行加密时,虽然对密码执行了哈希运算,解决了在数据库中以明文的形式存储用户密码的潜在安全隐患问题,但是这种加密策略在面对字典、彩虹表攻击时就显得有些脆弱了,并没有达到更高的安全性.为了解决上述问题,本文设计并实现了一种带有盐度值的安全哈希加密算法.通过带有盐度值的哈希运算,可以使得生成的密文进一步随机化,进而使得攻击者需要为每个盐度值创建一条字典记录,这将使得攻击变得非常复杂,最终使攻击者利用字典,彩虹表进行攻击的成功率降低.     

C#哈希表在零因子图研究中的应用

在零因子图的研究中,关于整数分拆数的计算以及结合律的验证等问题是人工较难完成的,而利用C#提供的哈希表进行编程可以有效地解决这两个问题.     

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

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

基于动态获取高频率键的MapReduce性能优化算法

在云计算技术领域中,MapReduce能够帮助人们快速处理海量数据,因此在学术界以及工业界越来越受到重视。但是MapReduce在处理以文本为中心的应用时,中间结果中数据重复较多。针对该情况,已有的高频率缓冲(frequency buffering,FB)算法提出在环形内存缓冲之前添加哈希表,并将高频率键存储在哈希表中。该算法通过采样来实现,有额外开销并且统计出的高频率键并不一定准确。该文提出一种基于动态获取高频率键的MapReduce性能优化算法,通过在环形内存缓冲之前增加计数Bloom过滤器(counting Bloom filter,CBF)和哈希表,将高频率键动态地存储在哈希表中。该算法获得的高频率键更准确,同时大大减少了数据排序和磁盘I/O的开销。实际测试结果表明:该算法明显提高了作业的执行速度,比原始MapReduce提高17.04%,比FB算法提高9.31%。     

基于D维映射的布谷鸟哈希表

哈希的数据结构和算法是海量信息存储的有效方式,特别是对于与网络流量测量、监控和安全相关的应用。目前存在许多哈希表算法,如布谷鸟哈希、Peacock Hash、Link Hash和Double Hash等,但是这些哈希算法仍存在着一些问题,如占用内存空间过大、插入查找等操作时间过长以及插入过程中遇到死循环而导致插入失败需要进行重新哈希等。针对这些问题,文中提出了基于D维映射的布谷鸟哈希算法,对哈希表进行属性划分,并增加链表结构,然后与辅助数据结构布隆过滤器和位图进行结合,并通过预先识别踢出操作是否有必要来减少不必要的内存访问次数,提高了哈希表的负载因子和插入查找效率。     

基于GPU的可扩展哈希方法

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

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

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

一种针对任意整数序列的超“快速排序”算法研究

提出了一种基于哈希函数的超“快速排序”算法。根据数组下标递增的特点,对待排序的任意整数序列建立有效的哈希函数,通过循环映射链接完成排序。分析了算法的时间和空间复杂度,实验验证了算法的运行效率。结果表明：算法的时间和空间复杂度均为O（n）,在问题规模较大时,效率优势明显。     

基于任务量划分的紧嵌套循环自动并行化方法

采用计算任务量大小的方法,解决了在紧嵌套循环自动并行化过程中存在循环并行化的并行粒度确定问题以及循环自动并行化中数据划分的数据访问局部性问题,在多核系统中实现了紧嵌套循环自动并行化时的数据访问局部性方案和并行化方法,从而构造了一个基于任务量划分的循环自动并行化模型,降低了程序自动并行化中小任务量并行带来的开销.     

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

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

基于哈希表的STL面片冗余顶点快速滤除算法

为了滤除STL面片数据中的冗余顶点,提出了基于哈希表的快速算法,使用链地址法处理冲突,根据顶点坐标设计高效哈希函数,直接滤除冗余顶点,从而提高运行效率,节省存储空间,经测试验证,该算法效率远远高于三轴分块排序算法,本算法已经成功应用于华塑CAE系统,也适用于其他各种以STL为数据交换格式的系统。     

Apriori算法的研究及在商业决策中的应用

通过分析关联规则中的经典算法Apriori,针对传统Apriori算法效率上的不足,提出一种基于哈希技术的改进Apriori算法,该算法将频繁项集存储在哈希表中,采用线性直接地址法使得哈希表中存储的频繁项集不冲突,提高算法的效率,具有较好的实用性.     

基于抗几何变换的离散深度哈希算法

现有的深度哈希算法首先利用连续松弛策略学习连续的近似码,然后通过量化运算将其转化为离散哈希码,导致哈希码出现次优问题.为了解决上述问题,提出了一种基于抗几何变换的离散深度哈希算法,利用抗几何变换和语义监督信息直接指导离散哈希码的学习.首先,本文将离散哈希码学习和深度特征学习集成在一个统一的网络框架中,利用语义监督来指导...     

二次映射式K路合并排序算法

在映射式Ｋ路合并排序算法的基础上提出了一种二次映射式Ｋ路合并排序算法，解决了当记录总数较少、关键宇最大值较大时，映射式Ｋ路合并排序算法存在的存储开销浪费大的问题，并保持时间复杂性不变。     

DHT 原理及功能探讨

作为结构化 P2P 系统底层架构的分布式哈希表--Distributed Hash Table(DHT),已成为 P2P 网络中节点组织和查询的热点问题,同时针对分布式哈希表的理论和应用情况已有了一定的研究.阐述了分布式哈希表的基本原理,并细化了现有的分布式哈希表分层的思想,主要是总结了 DHT 的功能,并将它按照功能分割为三层,详细论述了每一层的具体功能和实现模块,提出了与应用程序交互的数据管理层的内容.