首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 218 毫秒
1.
针对计数性布鲁姆过滤器存储数据时计数器溢出的缺陷,提出了一种基于分层计数型布鲁姆过滤器(hierarchy counting Bloom filter,HCBF)的大流检测机制。该方法结合溢出概率函数的特性,将计数型布鲁姆过滤器从一层扩展到多层,并能自适应地配置各层计数型布鲁姆过滤器的参数,能够对大流进行较好的识别。基于互联网数据进行了仿真实验,结果显示:与计数型布鲁姆过滤器相比,在同样溢出概率条件下,提高大流检测精度的同时节省了大量的内存资源。  相似文献   

2.
典型Bloom过滤器的研究及其数据流应用   总被引:1,自引:0,他引:1  
Bloom过滤器是一种空间高效但有一定假阳性的数据表示方法。该文分析比较计数型Bloom过滤器、光谱Bloom过滤器和动态计数过滤器的异同点及适用场合,介绍Bloom过滤器在重复项检测及频繁项挖掘中的应用,总结Bloom过滤器给数据流带来的挑战,包括元素突发问题及数据流相异元素数目变化问题。  相似文献   

3.
传统的包抽样方法对每一个数据包都以同等的比率抽取,这样就导致了大部分被抽中的是大流,而短流和一般流非常少。高速网络的流量检测需要全面的流信息。针对传统流抽样的缺陷,结合现有的SGS(Sketch Guided Sampling)抽样比与流量成反比的公平抽样思想和动态计数型过滤器,提出更加高效的公平抽样算法DCFS(Dynamic Count Fair Sampling)。DCFS算法使用动态统计过滤器DCF(Dynamic Count Filter)统计流量,相对于SGS算法该方法空间更加高效,而且估计准确性也更好。  相似文献   

4.
一种新的基于SCBF的流抽样测量算法研究   总被引:1,自引:0,他引:1       下载免费PDF全文
为提高流测量系统的运行效率,减少其所需存储资源,提出了一种改进的测量并维护其流信息的算法——基于拆分型计数Bloom Filters(Split Counting Bloom Filters)的流抽样。该算法采用基于报文的抽样来实现流抽样,不仅可以使用较少系统资源来维护流信息,同时可适用于不同流量的测量点,提高了测量系统的准确性和可扩展性。  相似文献   

5.
提出一种基于分段模式的统计计数(counter segment)结构。Counter segment通过区分流量大小为每流分配计数器空间,使网络流根据其流量属性占用计数结构的不同段,避免了均匀分配等长计算空间带来的资源浪费,从而提高了存储空间利用率。在每段计数空间均使用两个并行哈希函数,提高了映射关系的精度。仿真表明,该结构能够保持较高的计数精度的同时更有效利用SRAM存储空间。  相似文献   

6.
张进  邬江兴  刘勤让 《软件学报》2010,21(5):1098-1114
对3种已有的计数型Bloom filter--Na(I)ve Counting Bloom Filter(NCBF),Space-Code Bloom Filter (SCBF)和d-left Counting Bloom Filter(dlCBF)--的查询错误概率进行了分析,得出了NCBF的计数器防溢出条件以及SCBF和dlCBF的参数最优设置准则.提出了一种衡量计数型Bloom filter性能的指标:负载适应性.针对dlCBF负载适应性差的问题,对dlCBF进行了改进,提出了一种计数型Bloom filter:Binary Shrinking d-left Counting Bloom Filter(BSdlCBF).通过仿真实验,以计数误差、空间复杂度以及负载适应性为性能指标,对上述4种CBF进行了比较.实验结果表明,BSdlCBF具有最低的空间复杂度、最小的计数误差以及最佳的负载适应性. BSdlCBF赢得上述性能优势的代价在于其计算复杂度比其他3种计数型Bloom filter略高.  相似文献   

7.
张进  邬江兴  刘勤让 《软件学报》2010,21(4):1098-1114
对3 种已有的计数型Bloom filter——Na?ve Counting Bloom Filter(NCBF),Space-Code Bloom Filter (SCBF)和d-left Counting Bloom Filter(dlCBF)——的查询错误概率进行了分析,得出了NCBF 的计数器防溢出条件 以及SCBF 和dlCBF 的参数最优设置准则.提出了一种衡量计数型Bloom filter 性能的指标:负载适应性.针对dlCBF 负载适应性差的问题,对dlCBF 进行了改进,提出了一种计数型Bloom filter:Binary Shrinking d-left Counting Bloom Filter(BSdlCBF).通过仿真实验,以计数误差、空间复杂度以及负载适应性为性能指标,对上述4 种CBF 进行了比较. 实验结果表明,BSdlCBF 具有最低的空间复杂度、最小的计数误差以及最佳的负载适应性. BSdlCBF 赢得上述性能 优势的代价在于其计算复杂度比其他3 种计数型Bloom filter 略高.  相似文献   

8.
廖豪  梁峰  谭建龙 《计算机工程》2010,36(23):31-33,35
在研究数据流过程中,基于现有的概要数据结构Bloom Filter,给出改进的K Bloom Filter结构,从理论上对假阳性误判进行分析,得出两者具有相同的在误判率f0下表示集合规模的上限n0,因此,K Bloom Filter的误判率在可控范围内。提出基于K Bloom Filter的流计数算法,与基于Bloom Filter的流计数算法相比,在相同的空间复杂度O(m)和插入操作时间复杂度O(k)情况下,该算法降低了统计结果的误差。  相似文献   

9.
许多应用场景所产生的数据流中,元素的频数分布符合重尾分布的特点,即大部分元素的频数较小而少部分元素的频数较大.为了解决数据流中所有相异元素及其频数的高效存储问题,提出了一个基于分层的计数型布卢姆过滤器(hierarchical counting Bloom filter,HCBF)保存所有元素频数的方法.该方法采用长度递减、计数单位递增的多层计数型布卢姆过滤器作为存储数据结构,多层过滤器共同组成元素的频数.与两个经典的计数型布卢姆过滤器CBF和DCF相比,HCBF更加适合真实数据流元素频数分布的重尾特点,在不影响查询性能和错误率的前提下,能够显著地降低空间开销.理论分析与实验结果验证了该结论.  相似文献   

10.
偏态数据流中的Bloom Filters自适应机制研究   总被引:1,自引:0,他引:1  
针对Count Bloom Filters(CBF)在对偏态分布的网络数据流进行频度检测时,其使用的固定位数的计数器容易溢出的不足,提出了一种自适应性Bloom Filters(Adaptive Bloom Filters ABF),ABF使用可扩展的逻辑计数器替代CBF中大小固定的物理计数器进行计数,逻辑计数器由数目动态变化的若干个物理计数器组成,初始状态逻辑计数器等同于物理计数器,但逻辑计数器在频度数值上溢时会自适应扩展,覆盖其外部的物理计数器,增加数值容量,保证数值的测量准确性.实验表明ABF能够更好地适应检测频度的变化,并且不显著增加误判率,在对数据偏态分布的频度测量场合比其它Count Bloom Filters更具有优势.  相似文献   

11.
虚拟仪器流量测试的精度研究   总被引:2,自引:0,他引:2  
为了提高应用虚拟仪器进行流量测量的精度,分析了流量传感器的工作原理;比较了采用模拟输入、计数器输入和使用缓冲区的计数器输入三种不同的测试技术方案。在实验的基础上,应用误差理论分析测试数据证明:在LabVIEW环境中使用缓冲区技术进行计数器编程,各种以电脉冲发信的流量传感器的测量精度可以提高0.6%以上。  相似文献   

12.
吴桦  龚俭  杨望 《软件学报》2010,21(4):1115-1126
提出了一种基于双层Counter Bloom Filter 的长流识别算法(algorithm based on double counter bloom filter for long flows identification,简称CCBF).该算法使用两层Counter Bloom Filter 结构,将长流过滤和长流存在分开处 理.分析了该算法的误判率,通过模拟数据分析了算法错误率和内存资源限制的关系,并在相同内存资源限制的条件 下,将该算法与类似算法的准确性进行了比较.结果表明,在数据量较大的情况下,该算法具有比现有算法更小的平 均错误率;对算法的时间效率分析表明,该算法可以达到1 500kpps 的处理速度.各项指标反映出,该算法可以应用于 大规模主干网的长流监测.  相似文献   

13.
基于虚拟线圈的光流法车流量检测   总被引:7,自引:1,他引:7  
在交通系统中常需要知道道路的占有率、车流量等交通参数。该文提出了一种有效的车流量检测方法,这种方法首先在视频图像中设置好虚拟线圈作为检测区域,然后用光流法对检测区域进行图像处理,求出光流场,根据光流场的信息来判断检测区域内是否有车辆通过,通过对检测区域的不断判断来统计车流量信息。试验证明该文提出的车流量检测算法具有实施方便、检测精度高的特点,而且很容易推广用来测量占有率、车速等其它交通参数。  相似文献   

14.
吴桦  龚俭  杨望 《软件学报》2010,21(5):1115-1126
提出了一种基于双层Counter Bloom Filter的长流识别算法(algorithm based on double counter bloom filter for long flows identification,简称CCBF).该算法使用两层Counter Bloom Filter结构,将长流过滤和长流存在分开处理.分析了该算法的误判率,通过模拟数据分析了算法错误率和内存资源限制的关系,并在相同内存资源限制的条件下,将该算法与类似算法的准确性进行了比较.结果表明,在数据量较大的情况下,该算法具有比现有算法更小的平均错误率;对算法的时间效率分析表明,该算法可以达到1 500kpps的处理速度.各项指标反映出,该算法可以应用于大规模主干网的长流监测.  相似文献   

15.
张进  黄清杉  赵文栋  彭来献 《软件学报》2013,24(9):2165-2181
针对高速骨干网流量分析与流量管理对大规模高速统计计数器的需求,提出了一种简单、高效的主动式计数器结构——DALCA,其新颖之处在于对计数器向量进行分层,除第1 层外,其他各层子计数器向量采用多级哈希表的形式进行组织,获得了良好的空间效率和时间效率.与现有的主动式计数器结构BRICK 相比, DALCA 的空间效率与其接近,但是时间效率明显优于BRICK.采用真实的骨干网流量数据,通过仿真实验对DALCA 的性能进行了评估,结果表明:执行查询操作时,DALCA的访存带宽需求约为BRICK 的1/10;执行更新操作时,DALCA的访存带宽需求约为BRICK 的1/6.  相似文献   

16.
对大规模数据流统计的问题进行了研究,针对大流统计的典型结构Elastic Sketch替换策略中存在的问题进行优化,优化策略解决了冷流被误判为热流插入重部的问题.针对重部中保存的不一定是最大流的问题进行优化,提出了基于最大值和组相连的替换策略,保证了存储在重部的一定是最大的流,提高了大流统计的精度,同时大大降低了热碰撞发生的概率.相比于传统的测量统计方法,在提高了测量精度的同时,减少了内存占用.  相似文献   

17.
18.
刘卫江  白磊  景泉 《计算机工程》2007,33(20):116-118
根据网络上的流统计呈现很强的重尾分布的特性,该文提出了使用周期抽样和counting bloom filter(CBF)技术相结合的方法,即Sample-CBF方法来实现长流识别,并根据抽样策略的不同,将其具体化为两种方法:PSample-CBF方法和FSample-CBF方法。理论分析和仿真结果表明,在存在可容忍流长度测量误差的条件下,两种方法都可以准确识别长流,有效地减少存储空间和提高处理速度。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号