  Set queries are fundamental operations in computer systems and
applications.This paper addresses the fundamental problem of designing a
probabilistic data structure that can quickly process set queries using a small
amount of memory. We propose a Shifting Bloom Filter (ShBF) framework for
representing and querying sets. We demonstrate the effectiveness of ShBF using
three types of popular set queries: membership, association, and multiplicity
queries. The key novelty of ShBF is on encoding the auxiliary information of a
set element in a location offset. In contrast, prior BF based set data
structures allocate additional memory to store auxiliary information. To
evaluate ShBF in comparison with prior art, we conducted experiments using
real-world network traces. Results show that ShBF significantly advances the
state-of-the-art on all three types of set queries.
