Vectorized Bloom Filters for Advanced SIMD Processors - Columbia...

Vectorized Bloom Filters for Advanced SIMD ProcessorsOrestis Polychroniou! Kenneth A. RossBloom filters✤ Introduction! ✤ Original version [Bloom 1970]!✤ Represents a “set of items”!✤ Answers: “Does item X belong to the set ?”! !✤ Supports 2 operations!✤ Insert an item in the set!✤ Check if an item exists in the set! !✤ Probabilistic data structure!✤ Allows false positivesBloom filters✤ Description! ✤ The data structure!✤ A bitmap (an array of bits) of m bits!✤ A number of hash functions! !✤ In