Efficient set-membership filters and dictionaries based on SAT

Summary

INTRODUCTION This is a library for building and querying a compressed form of set-membership filters, named k-XORSAT filters. These filters can be used similar to how one would use a Bloom filter but with one restriction --- items cannot be added after the filter is built. So, this is an 'offline' or 'static' filter, whereas Bloom filters are considered 'online' or 'dynamic'. The advantage is that k-XORSAT filters achieve very near the optimal memory usage. That is, they use much less memory than Bloom filters, making them desirable for either large data sets (save space) or data sets that are provided to a large user base (save bandwidth). The advantage of k-XORSAT filters over other filters with small memory footprint is that the near-optimal compression of k-XORSAT filters is reliably achieved, and the query speed is comparable to Bloom filters for high false positive rates, and faster than Bloom filters for small false positive rates. DEPENDENCIES This package depends on pthreads and standard C math libraries. This project also relies on a few git submodules. To get these modules, clone the repository by doing either git clone --recursive git@github.com:NationalSecurityAgency/XORSATFilter.git or git clone git@github.com:NationalSecurityAgency/XORSATFilter.git cd XORSATFilter git submodule update --init --recursive INSTALL Run make in the project root directory. The library file libxorsatfilter.a will (assuming successful compilation) be created in this package's lib directory. USE k-XORSAT filters are built in two separate phases. The first step is to add elements to a builder object. The second phase is to create a querier object from a builder object. Once completed, the querier object may be queried ad infinitum. A builder is first allocated using XORSATFilterBuilderAlloc , like so: XORSATFilterBuilder *xsfb = XORSATFilterBuilderAlloc(0, 0); Here, the first argument 0 is the number of expected elements the filter will encode. It is safe to leave this number a...