一种基于并行Bloom Filter 的高速URL 查找算法
摘 要：URL 查找是众多网络系统中重要的组成部分，如URL 过滤系统、Web 缓存等.随着互联网的迅速
发展，URL 查找面临的主要挑战是实现大规模URL 集合下的高速查找，同时保证低存储和低功耗.本文提出了
一种基于并行Bloom Filter 的URL 查找算法，CaBF.该算法高度并行化，提供大规模URL 集合下的高速最长前
缀匹配，并很好地适应集合中不同数量的URL 组件.理论分析和真实网络数据集上的实验表明，该算法相比现有
算法可以降低假阳性概率达一个数量级（或者在满足相同假阳性概率的前提下降低存储和硬件逻辑资源消耗）.
此外，该方法的体系结构很容易映射到FPGA 等硬件器件上，提供每秒超过150M 次的URL 查找速度.
关键词：URL 查找；布鲁姆过滤器；最长前缀匹配；现场可编程门阵列
