Feed-forward Bloom filters
C C++ Ruby Python
Latest commit 8dc08e9 Jun 7, 2011 Iulian Moraru Changed build system to use autotools. It does not include the gpgpu
code yet.

README

This is the implementation of a feed-forward Bloom filter.  It provides
extremely fast fixed-pattern matching for up to millions of patterns
(similar to the functionality of 'fgrep').

AUTHORS: Iulian Moraru and David Andersen
        School of Computer Science,
        Carnegie Mellon University

For details about the algorithm and citations please use the article
"Exact Pattern Matching with Feed-Forward Bloom filters" by Iulian Moraru and David G. Andersen
URL: http://www.siam.org/proceedings/alenex/2011/alx11_01_morarui.pdf

We have used an older version of the algorithm for malware scanning. Details in:
"SplitScreen: Enabling Efficient, Distributed Malware Detection"
URL: http://www.usenix.org/events/nsdi10/tech/full_papers/cha.pdf

==================

Repository structure:

/src/rabin-karp

    The implementation of a feed-forward Bloom filter for the x86 architecture.

/src/gpgpu

    The implementation of a feed-forward Bloom filter for CUDA.

/src/hashes

    A compilation of hash functions that we've tested for the feed-forward Bloom filter.