FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
XORSAT Set Membership Filters

Authors: Sean Weaver, Hannah Roberts and Michael Smith

Paper Information

Title:XORSAT Set Membership Filters
Authors:Sean Weaver, Hannah Roberts and Michael Smith
Proceedings:SAT Proceedings
Editors: Christoph M. Wintersteiger and Olaf Beyersdorff
Keywords:Set Membership, Filter, XORSAT
Abstract:

ABSTRACT. Set membership filters are used as a primary test for whether large sets contain a given element. The most common such filter is the Bloom filter. Most pertinent to this article is the recently introduced Satisfiability (SAT) filter. This article proposes the XOR-Satisfiability (XORSAT) 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., achieves 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.

Pages:18
Talk:Jul 12 12:00 (Session 75B: Tools & Applications I)
Paper: