CAJ | 학술논문

许多应用场景所产生的数据流中,元素的频数分布符合重尾分布的特点,即大部分元素的频数较小而少部分元素的频数较大.为了解决数据流中所有相异元素及其频数的高效存储问题,提出了一个基于分层的计数型布卢姆过滤器(hierarchical counting Bloom filter,HCBF)保存所有元素频数的方法.该方法采用长度递减、计数单位递增的多层计数型布卢姆过滤器作为存储数据结构,多层过滤器共同组成元素的频数.与两个经典的计数型布卢姆过滤器CBF和DCF相比,HCBF更加适合真实数据流元素频数分布的重尾特点,在不影响查询性能和错误率的前提下,能够显著地降低空间开销.理论分析与实验结果验证了该结论.
허다응용장경소산생적수거류중,원소적빈수분포부합중미분포적특점,즉대부분원소적빈수교소이소부분원소적빈수교대.위료해결수거류중소유상이원소급기빈수적고효존저문제,제출료일개기우분층적계수형포로모과려기(hierarchical counting Bloom filter,HCBF)보존소유원소빈수적방법.해방법채용장도체감、계수단위체증적다층계수형포로모과려기작위존저수거결구,다층과려기공동조성원소적빈수.여량개경전적계수형포로모과려기CBF화DCF상비,HCBF경가괄합진실수거류원소빈수분포적중미특점,재불영향사순성능화착오솔적전제하,능구현저지강저공간개소.이론분석여실험결과험증료해결론.
In many scenes,elements frequency distribution meets the heavy-tailed distribution,which means most elements have low frequencies and a small number of elements have high frequencies.In order to solve the problem of how to count frequencies of all elements efficiently in data stream,a novel solution is proposed based on hierarchical counting Bloom filter(HCBF) data structure.Compared with two classical counting Bloom filters,CBF and DCF,the solution significantly reduces space complexity and does not raise time complexity and error rate.Theoretical analysis and simulation results demonstrate the efficiency of the proposed solution.