Using Bloom Filters to Speed-up Name Lookup in Distributed Systems
Mark Little · The Computer Journal · 2002
Bloom filters make use of a ‘probabilistic’ hash-coding method to reduce the amount of space required to store a hash set. A Bloom filter offers a trade-off between its size and the probability that the filter returns the wrong result. It does this without storing the entire set, at the cost of occasionally incorrectly answering yes to the question ‘is $x$ a member of $s$?’. How Bloom filters can be used to speed up the name to location resolution process in large-scale distributed systems is discussed. The approach presented offers trade-offs between performance (the time taken to resolve an object's name to its location) and resource utilization (the amount of physical memory to store location information and the number of messages exchanged to obtain the object's address).