A shifting bloom filter framework for set queries

Set queries are fundamental operations in computer systemsand applications. This paper addresses the fundamentalproblem of designing a probabilistic data structure that canquickly process set queries using a small amount of memory.We propose a Shifting Bloom Filter (ShBF) framework forrepresenting and querying sets. We demonstrate the effectivenessof ShBF using three types of popular set queries:membership, association, and multiplicity queries. The keynovelty of ShBF is on encoding the auxiliary informationof a set element in a location offset. In contrast, prior BFbased set data structures allocate additional memory to storeauxiliary information. We conducted experiments usingreal-world network traces, and results show that ShBF significantlyadvances the state-of-the-art on all three types ofset queries. ? 2016 VLDB Endowment 2150-8097/16/01.EI5408-419