Building high accuracy bloom filters using partitioned hashing

摘要: 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 Bloom filters. This is because filters provide a relatively easy method for hardware implementation set-membership queries. However, tradeoff that only probabilistic test and membership queries can result false positives. Ideally, we would like this positive probability be very low. main contribution paper significantly reducing comparison existing schemes. done by developing partitioned hashing which results choice hash functions set far fewer bits filter bit vector than case otherwise. lower fill factor translates much probability. We show experimentally improved ten-fold increase accuracy over standard also scheme performs better other proposed schemes improving