Building high accuracy bloom filters using partitioned hashing Export

@article{citeulike:4131642, abstract = {The growing importance of operations such as packet-content inspection, packet classification based on non-IP headers, maintaining flow-state, etc. has led to increased interest in the networking applications of Bloom filters. This is because Bloom filters provide a relatively easy method for hardware implementation of set-membership queries. However, the tradeoff is that Bloom filters only provide a probabilistic test and membership queries can result in false positives. Ideally, we would like this false positive probability to be very low. The main contribution of this paper is a method for significantly reducing this false positive probability in comparison to existing schemes. This is done by developing a partitioned hashing method which results in a choice of hash functions that set far fewer bits in the Bloom filter bit vector than would be the case otherwise. This lower fill factor of the bit vector translates to a much lower false positive probability. We show experimentally that this improved choice can result in as much as a ten-fold increase in accuracy over standard Bloom filters. We also show that the scheme performs much better than other proposed schemes for improving Bloom filters.}, address = {New York, NY, USA}, author = {Hao, Fang and Kodialam, Murali and Lakshman, T. V.}, citeulike-article-id = {4131642}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1269899.1254916}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1269899.1254916}, doi = {10.1145/1269899.1254916}, issn = {0163-5999}, journal = {SIGMETRICS Perform. Eval. Rev.}, keywords = {data\_structure, sys\_performance}, number = {1}, pages = {277--288}, posted-at = {2009-03-04 11:06:37}, priority = {2}, publisher = {ACM}, title = {Building high accuracy bloom filters using partitioned hashing}, url = {http://dx.doi.org/10.1145/1269899.1254916}, volume = {35}, year = {2007} }

TY - JOUR ID - citeulike:4131642 L3 - citeulike-article-id:4131642 N2 - The growing importance of operations such as packet-content inspection, packet classification based on non-IP headers, maintaining flow-state, etc. has led to increased interest in the networking applications of Bloom filters. This is because Bloom filters provide a relatively easy method for hardware implementation of set-membership queries. However, the tradeoff is that Bloom filters only provide a probabilistic test and membership queries can result in false positives. Ideally, we would like this false positive probability to be very low. The main contribution of this paper is a method for significantly reducing this false positive probability in comparison to existing schemes. This is done by developing a partitioned hashing method which results in a choice of hash functions that set far fewer bits in the Bloom filter bit vector than would be the case otherwise. This lower fill factor of the bit vector translates to a much lower false positive probability. We show experimentally that this improved choice can result in as much as a ten-fold increase in accuracy over standard Bloom filters. We also show that the scheme performs much better than other proposed schemes for improving Bloom filters. IS - 1 JF - SIGMETRICS Perform. Eval. Rev. SN - 0163-5999 AD - New York, NY, USA EP - 288 TI - Building high accuracy bloom filters using partitioned hashing PB - ACM VL - 35 SP - 277 KW - data_structure KW - sys_performance AU - Hao, Fang AU - Kodialam, Murali AU - Lakshman, TV PY - 2007/// UR - http://dx.doi.org/10.1145/1269899.1254916 ER -