Using Bloom Filters to Speed-up Name Lookup in Distributed Systems

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 co...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2002-01, Vol.45 (6), p.645-652
Main Authors: Little, M C, Shrivastava, S K, Speirs, N A
Format: Article
Language:English
Subjects:
Names
Servers
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/45.6.645