Bloom Filters & Data Synchronization - 11/22/2002

Sachin Agarwal

Bloom filters are provide an efficient way to condense set membership information into a string of bits (called a bloom filter) that is smaller than the size of the set, usually by orders of magnitude. This allows efficient reconciliation of sets by just exchanging bloom filters instead of the entire data sets. Bloom filters are used in many applications including the SQUID cache proxy servers in order to efficiently determine what information is cached on each server. In this talk I will be briefly going over Bloom Filter theory. Later, I will speak about the use of bloom filters in Data Synchronization and explain a real life implementation of these principles in a PC-PDA synchronization system. I will also compare this approach to CPISync and explain the various pros and cons of one against the other.

Relevant reading: Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol Li Fan, Pei Cao, Jussara Almeida, Andrei Broder http://citeseer.nj.nec.com/cache/papers/cs/23436/http:zSzzSznetlab18.cis.nctu.edu.twzSzhtmlzSzInternetProtocolzSzpaperzSzSummaryCacheSharingProtocol.pdf/fan00summary.pdf