XOR-Satisfiability Set Membership Filters

摘要

Set membership filters are used as a primary test for whether large sets contain given elements. The most common such filter is the Bloom filter [6]. Most pertinent to this article is the recently introduced Satisfiability (SAT) filter [31]. This article proposes the XOR-Satisfiability filter, a variant of the SAT filter based on random k-XORSAT. Experimental results show that this new filter can be more than 99% efficient (i.e., achieve the information-theoretic limit) while also having a query speed comparable to the standard Bloom filter, making it practical for use with very large data sets.