基于分布式哈希表标识的配电数据网路由优化方法研究

针对海量配电终端接入的路由存储开销问题,文章提出一种基于分布式哈希表(distributed hash table,DHT)标识的配电数据网路由优化方法。首先分析工业以太网构建的配电数据网低存储开销的技术需求;然后通过引入DHT存储设备接入信息和Chord快速查找哈希表等策略,设计基于DHT标识的低存储开销的路由优化方法;最后通过实验仿真验证所提方法性能的有效性。实验仿真结果表明,所提方法具有存储开销小、额外时延小、额外信道占用比例小等优点。

基于Trie树的哈希表

受到AC算法与链式哈希的启发,提出了一种基于Trie树的哈希表。该算法通过增加一个后继状态计数器,能够为后续的查找等运算提供更加简单和快速的信息。分析与实验表明该算法具有较高的效率、较强的稳定性,且降低了能耗。

面向GPU并行编程的哈希表性能评测与分析

哈希表是一种重要的索引数据结构,具有天然的并行性;GPU的单指令多线程工作模式大大提高了运算速率,但是哈希表内存访问的天然随机性、线程间的同步、GPU有限的内存等问题,给哈希表在GPU上的实现带来了很多挑战。针对上述挑战,目前已有众多的研究工作尝试利用GPU对哈希表进行加速,并取得了良好的效果。然而,已有的哈希方案尚未有全面、系统、统一的对比,使编程人员无法很好地了解在某一特定的应用场景中哈希表的性能排序,给哈希方案的选择带来一定的挑战。文章调查、分析并测评了几种基于GPU的典型哈希方案,并基于测评结果总结了影响哈希表性能的关键因素,最后对于哈希表的选择和使用,给出了相关建议。

一种基于分布式哈希表的混合对等发现算法

使用分布式哈希表(distributed hash table,简称DHT)的应用系统必须在O(1)发现算法和O(logN)发现算法系列中选择适应的DHT协议.但是,不同网络波动程度的应用场景要求理想的DHT协议根据网络波动率能够自适应地调整.提出一种发现算法ROAD(routing on active and demand),在延时和波动率之间自适应地调整以提供更好的性能.设计ROAD的关键挑战是构建路由表和降低延时的算法.通过构建加速路由表,加快发现服务的速度,降低消息转发的延时,并通过幂次序组播算法改善对超级点的依赖性.模拟实验显示,与现有DHT算法相比,ROAD维护了一种高效发现延时与波动率的折衷.选择不同质量类型的超级点,ROAD可以扩展成满足不同服务需要的发现机制.

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

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

Dual-Chord:一种更加有效的分布式哈希表

在基于分布式哈希表构造的对等网中,关键字的搜索效率一直是一个非常重要的指标.Chord提出在Chord环上构建结构化的分布式哈希表.Chord协议中查找的过程是单一的顺时针方向.Dual-Chord通过对路由表的扩展,使得系统的查找策略可以根据关键字在Chord环上位置离当前节点的远近来确定查找的方向,这样大大的提高了在对等网中的查找效率.同时,Dual-Chord综合考虑了网络延时对查找的影响.在设计中也根据节点间的网络延时来优化查找的性能.实验表明,在对等网中Dual-Chord协议定义的查找算法效率比Chord定义的查找算法要高.

一种哈希表快速查找的改进方法

哈希表由于其速度快的优点在数据查询中有着广泛的应用。本文在结合冲突解决机制和数据元素被查找的先验概率的基础上,提出了一种提高哈希表查找效率的优化方法,并对该方法在链地址法处理哈希冲突的情况下进行了理论分析,与原哈希表方法相比,该方法降低了冲突时执行查询的查找长度,从而使查询响应时间更短。最后对该方法进行了实例验证,实验结果表明,新方法是有效并且简便的。

基于哈希表的STL格式文件拓扑重建的算法

针对STL文件所包含的三角面片之间缺乏必要的拓扑关系,在对STL格式文件进行分析和读取时,采用了基于哈希表的拓扑重建算法。首先,以哈希表作为查找表,查找每一个三角形的顶点并将冗余顶点去除;然后,建立1个包含所有不重复顶点的点表和包含所有三角形在点表中索引值的面表,通过建立的点表和面表快速地实现拓扑结构的重建,使其后续的切片效率大大提高。

一种基于分布式哈希表的Web服务目录系统

分析了集中式UDDI注册中心存在的缺点。结合P2P技术,基于分布式哈希表提供的高效的数据定位功能,提出了一种分布式Web服务目录系统,讨论了该系统下Web服务的发布与发现过程以及目录系统的维护。在该服务目录系统中,服务的描述信息分布在各个节点上,能够克服集中式UDDI注册中心的缺陷。

基于哈希表的高性能URL过滤器研究

防火墙通过 URL 过滤控制对因特网信息资源的访问 .为了在高速防火墙上实现 URL 过滤 ,本文提出了位图法以改进URL过滤器的哈希表数据结构 ,提高哈希表查找速度 ;提出了快速压缩法 ,降低过滤器的空间占用 .经过位图法和快速压缩法改进 ,并应用高速缓存优化后 ,采用实验对 U RL 过滤器进行性能评价 ,发现 URL 过滤的平均时间下降了 2 5 3.7% ,空间下降了2 5 .7% .

GBLHT:一种GPU加速的批量插入线性哈希表

为改善线性哈希表这一有效索引结构的插入性能,在分析现有方法的基础上,结合CUDA并行编程模型,设计并实现了一种基于GPU的批量插入线性哈希表GBLHT;借助原子函数atomicAdd,GBLHT可以充分利用GPU强大的并行吞吐量来实现大规模记录的无锁批量插入;通过实验对比传统串行插入方法、CPU批量插入方法以及GBLHT的插入性能,发现在不同参数设置条件下,GBLHT的插入性能比传统串行方式提升了7～14倍,与4线程的CPU批量插入方法相比则提升了3～6倍.

CAM辅助的哈希表查找性能分析

现有大规模IP流处理方式中,哈希机制极具优势而在高速网络环境下被广泛采用,但其查找性能直接受限于访存次数。该文主要研究了CAM(Content Addressable Memory)辅助的哈希表(CAHT)查找性能。利用合理的近似,推导了单函数CAHT查找时平均访存次数的理论下限;结合单函数CAHT的分析结论给出了多函数CAHT查找时达到平均访存次数最小的条件。最后,使用实际网络数据验证了分析结果的有效性,为准确评估CAHT处理能力提供了必要的理论依据。

哈希表和多比特Trie相结合的IPv6分阶段路由查找算法

IPv6具有128位的地址长度、无分类编址,这使得IPv6网络中的核心路由器路由查找处理负担更重、要求更高,已有的基于IPv4的路由查找算法扩展到IPv6后无法适应新的需求,需要建立新的基于IPv6的路由查找算法.在分析了IPv6地址前缀长度和分布特点的基础上,提出一种哈希表和多比特Trie(retrieval)相结合的IPv6路由查找算法.算法首先根据地址前缀值来进行分类,然后针对常用的地址前缀值,以48比特为路由查找起点,分阶段、高效的进行路由查找,对于非常用的地址前缀值采用直接哈希查找.算法仿真表明,在大多数情况下,只需要一次存储器访问,就能查找到下一跳路由信息,算法查找效率高.算法结构简单,易于硬件实现.

基于哈希表与多比特树的路由查找算法

网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求。为此，将哈希表和多比特树相结合，提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层Tree中，采用哈希表存储路由下一跳的信息，根据目的IP地址在三层Tree结构中按最长前缀匹配的原则进行快速路由表项定位，并通过表项的信息在对应的哈希表中读取下一跳信息，进行数据转发。在多核平台上的测试结果表明，该算法在百万条路由环境下可达到双向10GB／s的速度，平均查找次数介于1～2次之间，平均延时小于30μs。

基于局部性的分布式哈希表资源定位技术

提出了一种基于局部性的分布式哈希表资源定位技术,将非结构化对等网络引入Chord中,充分利用节点在物理网络上的邻近性和节点间兴趣的局部性。模拟测试表明,该技术在路径长度和访问延迟方面的性能优于原Chord。

基于哈希表的动态向量降维方法的研究及应用

提出并实现了一种简洁的基于哈希表的动态向量降维方法。该方法用哈希表作为文档特征向量的存储数据结构,省去了预先构建向量模板的环节,实现了高维次稀疏特征向量的动态降维,有效减少了分类算法的数据计算量,能够显著提高分类器的性能。

基于素数序列的Java哈希表性能优化

分析了Java哈希表的实现特点并给出了导致其性能恶化的一种数据模式。针对这种数据模式的特点,提出了基于素数序列的哈希表优化方法,从而几乎完全避免了该模式下哈希表的性能恶化。实验与理论结果表明:对提出的模式数据,优化方法产生的Hash碰撞比JDK中的方法下降接近100%,而且对随机数据下的Java哈希表性能也有改善。

基于B＋树的分布式哈希表路由结构

在基于分布式哈希表构造的对等网络中,路由表的结构影响关键字的查询效率。B+树是一种有效查找的树型索引结构。考虑便于管理网络中众多的节点路由信息,提出一种基于B+树的路由结构,它通过为节点的路由信息建立索引,不仅提高了查询效率,将查找长度控制在树的高度内,而且使每个节点维护的路由信息尽可能少,减少了存储开销。

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

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

两级哈希表存储模式的高效多模式匹配算法

为了弥补多字符串模式匹配效率低下的缺陷,给出了一种基于双哈希表的多模式匹配算法。这个算法通过两个相关联的哈希表对模式串进行存储,同时采用一个转移表将发生失配时的跳跃距离存储。处于匹配阶段时:如果模式串无公共前缀,那么仅仅于第一个哈希表中进行查找;如果模式串有公共前缀,那么就在两个哈希表中顺序查找。经分析发现,此算法在最短模式串长度很长的环境中尤为适用,相对于经典算法,其时间复杂度较低,且其尝试次数也比较少。最后经实验可以证明,该算法具备较好的时空性能。