NAME

Algorithm::BloomFilter - A simple bloom filter data structure

SYNOPSIS

  use Algorithm::BloomFilter;
  
  my $filter = Algorithm::BloomFilter->new($absolute_nbits, $n_hashes);
  
  $filter->add("foo", "bar", "baz");
  if ($filter->test("bar")) {
    print "Eureka! 'bar' is in!\n";
  }

DESCRIPTION

This module implements a simple bloom filter in C/XS.

METHODS

new

Constructor, takes two arguments: The absolute number of bits to use for the bloom filter storage (this will be rounded up to the nearest power of 2) and the number of hash functions to evaluate for each entry.

Algorithm::BloomFilter uses SipHash internally. The C part can also use other hash functions, but the XS wrapper currently only supports SipHash.

add

Given a list of values (that will be converted to byte strings), add those values to the bloom filter.

test

Given a value (which will be converted to a byte string for this operation), test whether that value is part of the set represented by the bloom filter.

merge

Given another bloom filter of exactly the same configuration (same hash function, same number of hash function variants, same number of bits), computes a union of the two filters and stores the result in the invocant bloom filter.

serialize

Serializes the bloom filter into a string and returns it.

deserialize

Class method. Given a previously serialized bloom filter as a string, reconstructs the bloom filter. Returns the newly created Algorithm::BloomFilter object.

Beware that serialize/deserialize haven't been tested across systems with differing endianess, etc. Please do your own testing (and possibly submit patches to this caveat).

CAVEATS

Requires a uint64_t type. Untested on endianness other than x86_64's (little endian).

SEE ALSO

Wikipedia: http://en.wikipedia.org/wiki/Bloom_filter

AUTHOR

Steffen Mueller, <smueller@cpan.org>

COPYRIGHT AND LICENSE

Copyright (C) 2014-2015 by Steffen Mueller

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.0 or, at your option, any later version of Perl 5 you may have available.