摘要: 基于Bloom搜索过滤器的搜索过滤机制会发生误判,且在查询目标进入过滤器后,查询整个关键字的步骤会耗费太多成本。该文提出一套新的搜索过滤器架构。经实验验证,该过滤器能减少误判率的发生,降低整个过滤器的搜索成本,提高搜索过滤器的整体性能。
关键词:
Bloom搜索过滤器,
关键字集合,
误判,
查表目录
Abstract: Bloom filter based filtering mechanisms have one major drawback, that is, after a query item passes through the filter, the entire key set has to be searched ever for false positives. The search cost is therefore bound to be higher than necessary. This paper developes a new search filter which can lower the possibly of false positives, and significantly reduce the overall search cost, since a large amount of unnecessary search operations can be avoided.
Key words:
Bloom filter,
key set,
false positive,
lookup table
中图分类号:
高家利;廖晓峰. Bloom搜索过滤器的优化设计与实现[J]. 计算机工程, 2009, 35(7): 264-266.
GAO Jia-li; LIAO Xiao-feng. Optimized Design and Implementation of Bloom Filter[J]. Computer Engineering, 2009, 35(7): 264-266.