What are Bloom Filters?

#1

Post by nikant » Sat, Jul 18, 2015, 1:28 AM UTC

What are Bloom Filters?
medium.com

Re: What are Bloom Filters?

#2

Post by akras14 » Sat, Jul 18, 2015, 6:25 AM UTC

Corsera has a course from Stanford on Algorithm Design. They explain it really well there.

Re: What are Bloom Filters?

#3

Post by pvaldes » Sat, Jul 18, 2015, 9:20 AM UTC

Is a data structure (based in probability) that can be used to do queries about if an item is in a set. If the item is not in the collection you obtain a "100% probability of not in the set", if your item is in the set you obtain instead a "maybe in the collection".

  (ql:quickload "cl-bloom")
  (in-package :cl-bloom) 

  (setf *mydiet* (make-filter  :CAPACITY 256 :false-drop-rate *FALSE-DROP-RATE*) 
      ;; default false-drop-rate = 1/1000
      ;; returns #
 
  (add  *mydiet* "hamburguer") ;; add lots of items, returns NIL
  (add  *mydiet* "salad")

  ;; ask if an element is yet in the collection

  (memberp *mydiet* "hamburguer") ;; T (I can be wrong)
  (memberp *mydiet* "orange");; NIL (definitely not)