2015/10/11 by Tong Yang, Yang, Tong, Alex X. Liu +13 · 1 citation
Computer Science · Materials Science · #Caching and Content Delivery #Carbon and Quantum Dots Applications #Covalent Organic Framework Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1510.03019
openalex publication_date 2015/10/11 · arxiv created 2016/03/22 · arxiv updated 2016/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.