Reading Group - Network Applications of Bloom Filters: A Survey

Add to your list(s) Download to your calendar using vCal

• Pedro Brandao (University of Cambridge)
• Tuesday 14 October 2008, 14:30-15:30
• Room FW26, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Pedro Brandao.

Note the unusual room

Slides available .

From the reading group list I’ll be ”reading” Network Applications of Bloom Filters: A Survey

Andrei Broder and Michael Mitzenmacher,Internet Math. Volume 1, Number 4 (2003), 485-509.

Abstract:

A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters allow false positives but the space savings often outweigh this drawback when the probability of an error is controlled. Bloom filters have been used in database applications since the 1970s, but only in recent years have they become popular in the networking literature. The aim of this paper is to survey the ways in which Bloom filters have been used and modified in a variety of network problems, with the aim of providing a unified mathematical and practical framework for understanding them and stimulating their use in future applications.

This talk is part of the Computer Laboratory Opera Group Seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Opera Group Seminars
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Room FW26, Computer Laboratory, William Gates Building
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.