Algorithms For Dummies

Filtering stream elements by heart

At  the  heart  of  many  streaming  algorithms  are  Bloom  filters.  Created  almost 

50 years ago by Burton H. Bloom, at a time when computer science was still quite 

young, the original intent of this algorithm’s creator was to trade space (memory) 

and/or time (complexity) against what he called allowable errors. His original 

paper is entitled Space/Time Trade-offs in Hash Coding with Allowable Errors  (see: 

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.2080& 

rank=2

 for details).

You may wonder about the space and time that Bloom considers motivators for his 

algorithm. Imagine that you need to determine whether an element has already 

appeared in a stream using some previously discussed data structure. Finding 

something in a stream implies recording and searching are fast, thus a hash table 

seems an ideal choice. Hash tables, as discussed in Chapter 7, simply require adding 

the elements that you want to record and storing them. Recovering an element 

---

240

 

   

  PART 4