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 [email protected]:NationalSecurityAgency/XORSATFilter.git
or
git clone [email protected]:NationalSecurityAgency/XORSATFilter.git cd XORSATFilter git submodule update --init --recursive
INSTALL
... continue reading