GitHub - efficient/ffbf: Feed-forward Bloom filters (original) (raw)

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.